A modern programming language that makes developers happier.

kotlinlang

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>

Now that's the kind of library I like to see; based work EG :pinched_fingers: :evergreen_tree:

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

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.

Great work <@U3K6VQZLJ> :+1:  I agree with <@U01MQG40ZNC> 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.

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>

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

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

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.

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.

I just released <https://github.com/eygraber/trie-kmp|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!