Releases: RobbieMcKinstry/sdtrie
Releases · RobbieMcKinstry/sdtrie
Initial Radix Trie Release
This release provides the first pass at a radix tree. The code has a sizable passing integration test, implying that it's likely correct.
Some observations about this release:
- Lookup performs in
O(n)
time, verified empirically (wheren
is the number of keys in the tree. - The radix trie can handle around 8000-9000 lookups per minute.
- The trie uses vastly more memory than the size of the strings it contains. Adding 1.7MB of data produces a trie of size 27 MB.
Future Plans:
- Add a fuzzer
- Add a DOT output so the trie can be visualized
- Improve lookup performance from
O(n)
toO(lg n)
- Extend this type to allow other values to be stored on the leaves beyond IDs.
- Improve memory usage
- Benchmark and graph both memory usage and runtime