hello Stefan,
the felix programming language uses Judy arrays (extensively?), and seem
to have a good understanding of them.
maybe you can check out what he came up with.
It's a nice language, too, with some interesting features.
bye, Kobi
On 4/9/2012 2:20 PM, Stefan Plantikow wrote:
Thanks for the pointer, that is definitely an algorithm to keep in mind!
I read the hopscotch paper today and among other things they evaluate hopscotch
against a highly optimized linear probing algorithm. Hopscotch outperforms that
linear probing approach by a noticeable margin, likely due to better cache
alignment (hopscotch on average requires< 1 cache miss!). Though it is not
completely clear how much that carries over to another linear probing algorithm, I
still tend towards implementing single core hopscotch with key displacement for
now. Actually, it may be possible to combine robin hood probe counts with
hopscotch hashing to get the reduced variance effect and I probably will try that.
While digging through papers, I also notices that there are new results that
limit the memory requirements of near perfect hash functions (fixed key sets),
and stumbled upon judy arrays (which I didn't know before and may be
interesting to try, too, even though they are badly described by the authors).
May rust get more and faster data structures,
Cheers,
Stefan
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
