CODEWITHSUNDEEP
performancealgorithmdata-structuresintegerbig-o
Palace Chan
Palace Chan

Reputation: 9203

What's the quickest way to lookup numbers?

I am storing numbers (in the range from 1 to less than 100,000) and then getting called with a number as an argument and having to use that as a key in a lookup. In the past, when getting short char* strings as keys to lookup I have used a trie implementation. I wonder if I should use one as well for numbers of if maybe there are some faster ways to look into/consider/investigate?

Upvotes: 0

Views: 164

Answers (2)

templatetypedef
templatetypedef

Reputation: 372992

This really depends on what you're trying to do.

If you have a lot of memory, you could just build an array with 100,000 elements and just use the number as an index when looking into the table. This is probably the fastest approach (lookups are all O(1) with extremely low constant factors), though it's not the most memory-efficient. If memory is scarce, a standard hash table would be a good compromise; you get expected O(1) runtime for all operations.

If you need to be able to do queries of the form "what number is closest to x?," then you might want to use a balanced binary search tree that holds the integers. This lets you do successor and predecessor searches and lookups in time O(log n). If you're interested in trying out a much more complex data structure, you can use a van Emde Boas tree, which can do insertions, deletions, lookups, predecessor, and successor searches in time O(log log U), where U is the maximum possible value.

Hope this helps!

Upvotes: 3

TGH
TGH

Reputation: 39268

I would suggest using a hashtable for this. Each value would be placed in a unique bucket that you can reference using your key. If your data can be organized in this manner this will be the fastest look up.

Upvotes: 0

Related Questions