3 ms·
Ilan Schnells AOT generator for perfect hash functions[0] has served me well. It takes a code template so you can generate code for any language. It also uses t
by nly 11y ago
Ilan Schnells AOT generator for perfect hash functions[0] has served me well. It takes a code template so you can generate code for any language. It also uses the much more elegant CHM algorithm[1] (Which is also implemented by the venerable CMPH library[2] if you want to compute these things dynamically.)
If I was doing dynamically in C++, like the author of this post, and didn't want to add a runtime dependency, I might be tempted to implement CHM using Boost Graph.
[0] http://ilan.schnell-web.net/prog/perfect-hash/ http://ilan.schnell-web.net/prog/perfect-hash/
[1] http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html
[2] http://cmph.sourceforge.net/ http://cmph.sourceforge.net/
- deleted 11y ago[deleted]
- mtdewcmu 11y agoI'm thinking about how I'd implement CHM. I think I'd use a union-find data structure to generate the acyclic graph, as in Kruskal's algorithm. This would fit into an N-element integer vector. After finding the acyclic graph (forest), I'd represent the forest implicitly in another N-element integer vector, for finding the vertex weights. You can take advantage of the graph being just a forest of trees and use simpler data structures.
- gct 11y agoWhy would you use boost for that? The only two graph things there are determining if it's acyclic and depth-first traversal, both of which are pretty easy to just write.