4 ms·
See also djb’s crit-bit trees, which are a tighter and simpler version of PATRICIA trees - https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html - and agl
by fanf2 9y ago
See also djb’s crit-bit trees, which are a tighter and simpler version of PATRICIA trees - https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html - and agl‘s nice literate code explanation of how they work - https://github.com/agl/critbit/ https://github.com/agl/critbit/
And my qp tries, which are smaller and faster than crit-bit trees https://dotat.at/prog/qp/ https://dotat.at/prog/qp/
- PeCaN 9y agoOh hey, I've used qp-tries in an interpreter for a Forth-like language. They're really elegant IMO. Thanks for publicizing and implementing your discovery!
- fanf2 9y agoAlways a pleasure to hear about people making good use of them!
- tonyg 9y agoBoth critbit and qp tries are wonderful. I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit/blob/master/critbit.ml https://github.com/tonyg/ml-critbit/blob/master/critbit.ml) and Typed Racket (https://github.com/tonyg/racket-critbit/blob/master/critbit.rkt https://github.com/tonyg/racket-critbit/blob/master/critbit....). I was surprised to find the OCaml implementation is competitive speedwise with the built-in Set implementation over strings.