Solved

Fast search of guid tables

Posted on 2011-03-21
8
698 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: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
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…

685 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