3 ms·
Comparing a static data structure to two well-known dynamic structures is disingenuous, to say the least. And for a static structure you can do better than just
by senderista 7y ago
Comparing a static data structure to two well-known dynamic structures is disingenuous, to say the least. And for a static structure you can do better than just a minimal perfect hash table of fingerprints. You can use a succinct data structure to compress the fingerprints in a form that is still efficiently queryable (unlike say Golomb-compressed sequences):
https://www.antoniomallia.it/sorted-integers-compression-with-elias-fano-encoding.html https://www.antoniomallia.it/sorted-integers-compression-wit...
- powturbo 7y agoElias-fano are overestimated without any proof or comparison benchmarks. Like other integer compression methods, you still need offsets to small blocks for efficient random access. Getting a single value in a block is done with slow branchy bit ops like ctz and bit shifting. That's decoding The fastest elias-fano implementation is in https://github.com/powturbo/TurboPFor https://github.com/powturbo/TurboPFor and is partially using SIMD