You are not so tough without your car. Fastest lookup list

Question

I have a collection of structures. Each structure has 2 keys. If I query using key #1, I should get key #2 in return and vice versa.

It's easy to write code on the desktop when you have the power of the .NET Framework behind you. I am writing code in the .NET Micro Framework, which is a very very limited subset of framework. For instance, as far as collections, I only have arrays and ArrayList objects at my disposal.

So for example here is the list of structures:

Key #1        Key #2 
6             A
7             F
8             Z
9             B

So when I query for 8, I should get Z. When I query for Z, I should get 8.

I am looking to do the fastest and least processor intensive lookup using either arrays or ArrayList. The device I am coding against is a low-end ARM processor, thus I need to optimize early.

Answer 1

If the set is fixed, look into perfect hash functions.

Answer 2

Any reason you can't write your own hashmap?

Answer 3

It depends on the number of entries and your access pattern.

Given that your access pattern is random access if you don't have too many elements you could have 2 Arrays of Pairs and then use

Array.BinarySearch()

Answer 4

Well... if you want the fastest and aren't too concerned about memory, just use two hash tables. One going one way, one going to other. Not sure if there's a more memory efficient way...

Or use just one hash table but have the entries for both directions in there.

Answer 5

Is it not as simple as :

• find the key in the array you're querying
• return the key at the same index in the opposite array

I would keep it as simple as possible and just iterate through the array you're searching. You'll probably only see a benefit from implementing some hashing routines if your list is (plucks figure from air) over 1k+ elements, with the added complexity of your own hashing routines slowing things down somewhat.

Answer 6

Several solutions:

1. Keep 2 lists in sync, do a linear search. Works well unless your collections are very large, or you're searching repeatedly.
2. Two hashtables. Writing your own is fairly easy -- it is just a fixed array of buckets (each bucket can be an ArrayList). Map an item to a bucket by doing object.GetHashCode() % numBuckets.
3. Two arrays the size of the range of values. If your numbers are in a fixed range, allocate an array the size of the range, with elements being items from the other group. Super quick and easy, but uses a lot of memory.

Answer 7

If it's a fixed set, consider using switch. See the answer to a similar question here.

Answer 8

I had this problem several years ago when programming C, that we need to find a barcode (numeric) quickly in about 10 thousand rows (in that time, using a file as the Database - as it was a hand device)

I created my own search that instead of iterate one by one would start always in the middle...

searching for 4050 in 10000 item stack

start on 5000 ( 10 000 / 2 )
now, is the number higher or lower ... lower

start on 2500 ( 5000 / 2 )
now, is the number higher or lower ... higher

start on 3750 ( 2500 + 2500 / 2 )
now, is the number higher or lower ... higher

start on 4375 ( 3750 + 1250 / 2 )
now, is the number higher or lower ... lower

start on 4063 ( 4375 - 625 / 2 )
now, is the number higher or lower ... lower

start on 3907 ( 4063 - 312 / 2 )
now, is the number higher or lower ... higher

start on 3907 ( 3907 + 156 / 2 )
now, is the number higher or lower ... higher

start on 3946 ( 3907 + 78 / 2 )
now, is the number higher or lower ... higher

...

until you get the value... you will need to search about 14 times instead 4050 iterations

about the letters ... they all represent a numeric number as well...

Hope it helps