4 ms·
Minimal Perfect Hash-Tables in Common Lisp
- kruhft 9y agoRelevant, alternate implementation for C and C++: https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/
- martincmartin 9y agogperf's time complexity is quite bad. It predates the modern, minimal perfect hashing by a few decades. But it's easy to download & run.
- kruhft 9y agoAs long as it still works. :)
- rurban 9y agoNope, not at all. gperf creates totally different and unoptimized perfect hashes, not minimal at all.
- kruhft 9y agoGood to know, thanks.
- resource0x 9y agoperfect map in dart: https://github.com/tatumizer/pigeon_map#how-it-works https://github.com/tatumizer/pigeon_map#how-it-works
- taeric 9y agoI love the reference to static structures. Indeed, I have a pet theory that most love of immutable lists is actually a love of static ones. Though, I typically expand that to measure statically visible in the code.
- justinhj 9y ago“(although, for many methods, it can still be bounded by amortized O(1) time)” I don’t follow this. Does it mean that you can build the perfect hash table in constant time? Surely you can’t beat linear.
- aidenn0 9y agoInserting into a non-static hash table is measured per-element so the blog is also saying O(1) per element, which is linear time.
- martincmartin 9y agotl;dr: Each insertion is O(n), but n insertions are also O(n). Saying "amortized time is O(1)" just means the time for n operations is O(n). To be pedantic: some individual insertions can take more the O(1), namely when you have to rehash it can take O(n) time. So the tight upper bound on each insertion is O(n). So doing n of them seems like it might take O(n^2). Except you can't rehash on every insertion. So even though the time to insert one is O(n), the time to insert n is also O(n). If you amortize that time over all n insertions, you get O(n) / n == O(1).
- martincmartin 9y ago"Amortized O(1) time" means the time for n operations is O(n), even though individual operations might be more than O(1). Building the hash table means adding n things. So they're saying its linear.
- zokier 9y agoThe algorithm used (EPH) seems bit curious. The paper says "The EPH algorithm was implemented in the C language and is available at http://cmph.sf.net" http://cmph.sf.net", but that page has no mention of EPH and I even checked archive.org. I wonder why they ended up never actually releasing a version of cmph with that algorithm. Two years later they seem to have come up with another algorithm, CHD, which was actually released in cmph. Interestingly enough the CHD paper has no comparisons to EPH either.
- rurban 9y agoYes, interesting. Never heard of EPH before. cmph contains only: BDZ, BDZ_PH, BMZ, BMZ8, BRZ, CHD, CHD_PH, CHM and FCH. EPH seems to be better than BDZ, CHM and FCH, but only for really huge tables, like >100.000 entries. For smaller hash tables a simple perfect hash or even an optimized memcmp switch table is still faster. https://github.com/rurban/Perfect-Hash#benchmarks https://github.com/rurban/Perfect-Hash#benchmarks cmph is usually 2-3x slower than a trivial PH, and much slower for small tables.