trie-kmp provides two general use trie implementations for all KMP targets. Give it a try and let me...

# feed

[eygraber]

trie-kmp provides two general use trie implementations for all KMP targets. Give it a try and let me know what you think!

https://github.com/eygraber/trie-kmp

[darkmoon_uk]

Now that's the kind of library I like to see; based work EG 🤌 🌲

[Klitos Kyriacou]

This looks great! I wonder if it's worth creating a trie specialized for strings. Currently, you're using List<Char> where every element takes up typically 16 bytes (as it's a generic pointer) instead of 1 byte.

[eygraber]

It's something I considered, but I wanted to get an initial version with tests and benchmarks set up, so that if I introduce a specialized version I can validate that it works, and compare its performance.

[Anonymike]

Great work @eygraber 👍 I agree with @Klitos Kyriacou but honestly think you made the right decision to get it out and have a base for comparison. It's always good to find a good implementation that you can validate, then repeat on a less simple/convenient but more optimized data structure. That said, strings should be easy to work with since most of your list calls would have a direct corollary already.

[eygraber]

Next version (should be released in the next hour or so) will have specialized implementations for string tries with improved performance - https://github.com/eygraber/trie-kmp/pull/4

[Klitos Kyriacou]

Great, now you can showcase its advantages by publishing a comparative benchmark, for example, of getAllWithPrefix with SortedMap.submap (only available on the JVM).

[eygraber]

Yes, I have a few more performance improvements planned, and then I'm going to work on some comparative benchmarks.

[Anonymike]

If I get some time, I may try to checkout the library a bit more and perhaps I can whip up something. Things are a bit crazy right now, but it would be a good brain clearing thing if I can make it happen lol.

[eygraber]

A quick benchmark shows that TreeMap.submap outperformed getAllWithPrefix

0.015 ± 0.001 ms/op` > `0.090 ± 0.001 ms/op

0.015 ± 0.001 ms/op > 0.075 ± 0.001 ms/op

but the Trie outperformed the TreeMap in all other operations by varying margins.

I didn't get the exact memory usage, but the TreeMap was obviously much larger.

[eygraber]

I just released v0.5.0 of trie-kmp with 50% performance improvements over the previous release.

With performance addressed (aside from extra micro optimizations) I'm looking for some feedback on the API surface, and once that's in a good place, v1.0.0!