Solved

Fast search of guid tables

Posted on 2011-03-21
8
699 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 

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

Enroll in May's Course of the Month

May’s Course of the Month is now available! Experts Exchange’s Premium Members and Team Accounts have access to a complimentary course each month as part of their membership—an extra way to increase training and boost professional development.

Question has a verified solution.

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

This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
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…
This video shows how to use Hyena, from SystemTools Software, to update 100 user accounts from an external text file. View in 1080p for best video quality.

739 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