• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 714
  • Last Modified:

Fast search of guid tables

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
rj_dds_no
Asked:
rj_dds_no
  • 5
  • 3
1 Solution
 
TommySzalapskiCommented:
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
 
rj_dds_noAuthor Commented:
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
 
TommySzalapskiCommented:
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
Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

 
rj_dds_noAuthor Commented:
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
 
rj_dds_noAuthor Commented:
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
 
TommySzalapskiCommented:
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
 
rj_dds_noAuthor Commented:
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
 
rj_dds_noAuthor Commented:
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: 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.

  • 5
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now