On Friday, 3 April 2015 at 16:12:00 UTC, w0rp wrote:
On Wednesday, 1 April 2015 at 06:31:28 UTC, thedeemon wrote:
On Tuesday, 31 March 2015 at 21:17:04 UTC, Martin Nowak wrote:
Robin Hood sounds like a good idea, but it really isn't. Keep
your load factor reasonable and distribute values evenly,
then you don't need a LRU lookup.
Is there a D version of a hash table with open addressing and
quadratic probing? It would be interesting to compare speeds.
I like Robin Hood for cache-friendliness, and it works quite
well for many combinations of key-value types.
Now there is. I just changed the hashmap in my container
library to use open addressing and quadratic probing. There's a
benchmark program in the library for testing it in comparison
to the standard associative array. I tested using 2.066 with
optimisations on, and it seems to be about the same.
https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d
Now, I am not the most fantastic Computer Science guy in the
world, and I probably got a few things wrong. If anyone would
like to look at my code and point out mistakes, please do. I
will add any improvements suggested.
Also, I changed the API slightly.
1. I removed setDefault for the standard associative array type.
Now it's only there for my type. The module now only deals with
the added library type.
2. I changed my range functions to match the names for range
functions in 2.067, so they are now named byKey, byValue, and
byKeyValue. I left out 'keys' and 'values', which I think are
mistakes, when you can do byKey.array yourself, etc.
3. I renamed ItemRange to KeyValueRange. (My ranges for the
hashmaps are all named, which is supposed to make it easier to
build higher order ranges from them.)
4. I added a constructor for the hashmaps which lets you maybe
avoid some allocations by providing a minimum size, where the
hashmap will probably use a size larger than the one you provide.
5. I started using prime sizes for the hashmaps, because
quadratic probing doesn't seem to work without primes.
I think that's the bigger changes at least.
