On 01-Mar-04 Chris Green wrote:
I have a little 68000 assembler project I'm doing for someone (paid!) and basically it consists of replacing a 'built on the fly' look-up table with a ready made one which is uploaded with the code. [...] A linear search of the table probably isn't a good idea as it would mean that there would be significant differences in look-up time for entries at the beginning and end of the table.
I'm leaning towards a binary-chop search but wondered if anyone had any other ideas. Binary-chop is easy in principle but it's often quite difficult to implement in practice because one has to deal with messy boundary conditions. It's also a bit more difficult to create the sorted table necessary automatically and relying on the creator of the table to sort it might be a bit dodgy.
The table looks up ATM addresses (16 bit values) given an IP address (32 bit values), maximum size is of the order of 400 entries.
As a general rule, btree indexing gives efficient look-up; but your description suggests this may be "messy" to set up.
I have another idea, which I need to look into the properties of before deciding whether it's a good idea or a bad one for your application.
Basically, it involves setting up a "tree of lists", and it makes your database "content-addressable".
Starting from a 4-byte IP address, the top level (0) consists of pointers to 256 different level-1 nodes; which node you are led to is determined by the value of the first byte in the IP address.
Each level-1 node contains a) either a null pointer, denoting that there was no IP address in the data whose first byte had the corresponding value; b) or a set of 256 pointers to level-2 nodes just like level-0.
And so on down the line until you get to level-4. Each level-4 node contains a pointer to a data structure contain the information to be looked up if you reach that node (in your case, the ATM address).
Searching such a tree would be very quick: given an IP address B1.B2.B3.B4, you go to node B1 in level-1, then node B2 in level-2, then node B3 in level-3, and finally node B4 in level-4 where you then find the information you are looking for. Lookup time is independent of the data.
The issue I need to look into is how much space would be required to store this tree (and also how efficient and/or messy it would be to implement it). Given that the number of actual entries you need to store is about 400, you should not need anything like the superficially apparent 2^32 nodes in total. Only the 400 would lead all the way down to level-4, and all the others would run into a dead end at a higher level. Probably you only need a thousand or two nodes in all to store the tree for 400 level-4 nodes.
As I say, I'll try to look into what this leads to for 400. But you may be interested in the idea.
Best wishes, Ted.
-------------------------------------------------------------------- E-Mail: (Ted Harding) Ted.Harding@nessie.mcc.ac.uk Fax-to-email: +44 (0)870 167 1972 Date: 01-Mar-04 Time: 12:14:41 ------------------------------ XFMail ------------------------------