Experiment (Lookup vs Brute Force Calculate)

Anything and everything that's related to OGRE or the wider graphics field that doesn't fit into the other forums.
jjp
Silver Sponsor
Silver Sponsor
Posts: 597
Joined: Sun Jan 07, 2007 11:55 pm
Location: Cologne, Germany
Contact:

Re: Experiment (Lookup vs Brute Force Calculate)

Post by jjp » Mon Feb 08, 2010 9:33 am

jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
Within the STL? Well, until C1X all map-like data structure implementations in the STL use trees (although they probably could use something else if it gave the same complexities for operations as trees do). But that wasn't the point. The point was that it is not true to say map = tree. Repeating myself: a map (or associative array) is an abstract data structure that can be implemented in a number of ways. Hashing, search trees, skip lists.. and probably there are even more exotic ways to do it.
0 x
Enough is never enough.

User avatar
stealth977
Gnoll
Posts: 638
Joined: Mon Dec 15, 2008 6:14 pm
Location: Istanbul, Turkey

Re: Experiment (Lookup vs Brute Force Calculate)

Post by stealth977 » Mon Feb 08, 2010 9:38 am

Ok guys, you are right in theory its my mistake to confuse my own requirements with the general requirements.

I checked std's implementation again and it uses vector buckets with the hashmap and thats fine with small hashmaps, the confusion was that where i need hashmaps, those maps are huge in size compared to general use. So, using basic buckets was not an option, i guess that experience caused the confusion...

Anyway, hashmaps are only O(1) in ideal cases (am i wrong again?) since usually there are not one to one correspondence between hash value and the bucket, there can be far too less buckets compared to number of available hashes, in that case, each bucket hold a number of key/value pairs per a fixed number of hashes. Which means O(1) to find bucket and O(n) to find the correct pair in the bucket.

An example:
lets say there are 1024*1024 possible hashes and our hashmap uses 1024 buckets. And lets say you insert 4096 pairs into hashmap, which means an avarage 4 pairs per bucket, the search will have an avarage O(1) + O(4) = O(5) steps (the first one to find bucket, the others to find the correct pair in the bucket)

And of course thats if the pairs inserted are distributed equally by the hash, there can be 1024 items in one bucket and the rest distributed to other buckets...in which case lookup for a key can take 1025 iterations...

To avoid such cases (in crowded hashmaps), trees are used as buckets and thats how i use them due to my projects' requirement of crowded hashmaps...

Sorry about my confusion again...
0 x
Ismail TARIM
Ogitor - Ogre Scene Editor
WWW:http://www.ogitor.org
Repository: https://bitbucket.org/ogitor

User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
Contact:

Re: Experiment (Lookup vs Brute Force Calculate)

Post by jacmoe » Mon Feb 08, 2010 9:39 am

jjp wrote:
jacmoe wrote:Yes, but is hash_map not the only map not using a tree?
Within the STL? Well, until C1X all map-like data structure implementations in the STL use trees (although they probably could use something else if it gave the same complexities for operations as trees do). But that wasn't the point.
Yes, of course. I think I was mostly referring to the STL.
Looking forward to when they get the cork out and actually release C++1x :)
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

jjp
Silver Sponsor
Silver Sponsor
Posts: 597
Joined: Sun Jan 07, 2007 11:55 pm
Location: Cologne, Germany
Contact:

Re: Experiment (Lookup vs Brute Force Calculate)

Post by jjp » Mon Feb 08, 2010 9:54 am

stealth977 wrote:Anyway, hashmaps are only O(1) in ideal cases (am i wrong again?)
That is correct :) If the hash map gets too crowded it won't perform that good any more. In this case the hash map may resize itself, for example. Which obviously isn't for free either, but if you do amortized analysis you end up again with lookup/insert in O(1). In other words: while resizing the hash map is costy it only has to happen rarely, for example whenever the hash map is half full it could double it's size.. pretty much like a std::vector. In the end it really depends on the use case if a tree-based or a hashing-based map is the better choice.
0 x
Enough is never enough.

Post Reply