Solved

Fast search of guid tables

Posted on 2011-03-21
8
696 Views
Last Modified: 2012-05-11
We are increasingly using guids as keys for objects. Currently the guids are kept in sorted arrays in memory and lookup is done by binary search.

Since guids are widely used I guess the best organisation for fast lookup is thoroughly researched by now. I am looking for a pointer to a good description (on the web) of the best algoritms for this or advice from somebody who has firsthand experience with implementation of this.

My question is: Can we get significantly faster lookup on guids than binary sort for our use (se below)? In that case, what organisation/lookup algorithms would be faster?

Here are some details of our implementation:

It is programmed in C++ (We are not using a DB tool) .
The guid tables will typically be up to 1 million entries.
The guid tables will all be in memory.
The lookup speed is very critical and it is done many times in "inner loops".
The tables are not known at compiletime.
Some tables are fairly stable after first time load.
Some tables are dynamic (delete/insert). Most of the operations will however be add or insert.
The speed of the delete/insert/add administration is not as critical as the lookup speed.
We know in advance which tables are dynamic and which are stable.

-Rune
0
Comment
Question by:rj_dds_no
  • 5
  • 3
8 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 35180770
Binary search is O(lg(n)). Hash tables approximate O(1). You really need some kind of indexing/hash table.
Have you ever used a hash table? Are you using standard C++ or Visual C++?
0
 

Author Comment

by:rj_dds_no
ID: 35181099
We use Visual C++, but try avoid too much MS-extensions. Hashing can be implemented in many ways. For a hashing advice to be useful, it would have to point to specific hashing techniques that have proven useful for lookup in guid tables.
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 35182005
You could implement your own hash table I guess, but the Dictionary class is in there already so I would use that. It's been used for GUIDs before (and out performs other hash tables too). Se here for an example which was made using GUIDs.
http://www.phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 

Author Comment

by:rj_dds_no
ID: 35182523
Thanks! We will look into the Dictonay class and see if it is an option for us and how fast it performs. I'll come back on it when we have checked it out.
0
 

Author Comment

by:rj_dds_no
ID: 35188432
We use Boost. I discorvered that boost now have uuid with support for boost::hash

Any experience with lookup performance in uuid maps using boost anyone?
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 35201121
I haven't used Boost myself, but GUIDs has very nicely using any normal hashing algorithm, so I would say it should work quite well. You could just run some tests and see what you get out of it, but either method should approximate O(1), so they both would be feasible for your application.
0
 

Author Comment

by:rj_dds_no
ID: 35206067
We are not using managed code in C++ and using the Dictonary class will require access through COM which we belive is not optimal for such high performance needs.

We were looking for more specific experience with a solution like Boost. But after researching more on the guid/uuid I see that it should be well suited for hashing and I agree that any sensible implementation of this should give very good guid lookup performance.
0
 

Author Closing Comment

by:rj_dds_no
ID: 35206082
Had hoped for more specific experience and advice on the topic. But the general advice is correct and fair enough.
0

Featured Post

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question