Clever Geek Handbook

You are not that tough without your car. Fastest search list

I have a set of structures. Each structure has 2 keys. If I request with key # 1, I should get key # 2 back and forth.

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 limited subset of the framework. For example, as far as collections are concerned, I only have arrays and ArrayList objects.

So, for example, here is a list of structures:

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

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

I'm looking for the fastest and least cpu search using either Arrays or ArrayList. The device I'm coding in is a low-end ARM processor so I need to optimize early.

+2


source to share


8 answers


If the set is installed, view the perfect hash functions .



+2


source


Any reason you can't write your own hash file?



+1


source


It depends on the number of records and the access pattern.

Considering your access pattern is random access, if you don't have too many elements, you can have 2 arrays of pairs, then use

Array.BinarySearch()
+1


source


Well ... if you want the fastest and not too memory-conscious, just use two hash tables. One goes one way, one goes the other. Not sure if there is a more memory efficient way ...

Or use only one hash table, but there are entries for both directions.

0


source


Isn't it that simple:

  • find the key in the array you are requesting
  • return the key at the same index in the opposite array

I would put it as simple as possible and just loop over the array you are looking for. You will probably only see the benefits of implementing some hashing routines if your list (figurines out of thin air) exceeds 1k + items, with the added complexity of your own hashing routines that slows down some of the action.

0


source


Several solutions:

  • Keep 2 lists in sync, do linear search. Works well if your collections are not very large or if you search repeatedly.
  • Two hash tables. Writing your own is pretty straightforward - it's just a fixed array of buckets (each bucket can be an ArrayList). Match the item to the bucket by doing object.GetHashCode() % numBuckets

    .
  • Two arrays - the size of the range of values. If your numbers are in a fixed range, allocate an array with the size of the range, with the items being items from another group. Super fast and lightweight but uses a lot of memory.
0


source


If it's a fixed set, use switch

. See the answer to a similar question here.

0


source


I had this problem a few years ago while programming in C that we need to quickly find a barcode (numeric) in about 10 thousand lines (in that time using a file as a database since it was a handheld device)

I created my own search, which instead of iterating one by one, it always started in the middle ...

search 4050 in a stack of 10,000 items

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

start at 2500 (5000/2)
now, this number is higher or lower ... higher

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

start at 4375 (3750 + 1250/2)
now this number is higher or lower ... lower

start at 4063 (4375 - 625/2)
now this number is higher or lower ... lower

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

start at 3907 (3907 + 156/2)
now this number is higher or lower ... higher

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

...

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

about letters ... they all also represent a numeric number ...

Hope it helps

0


source






More articles:


All Articles