New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add Trie #161
Comments
So any updates with this Trie feature? This is gonna be really helpful. |
For sure, I have looked into the implementation and am familiarizing myself with the technical details. Usually a trie is implemented on top of a radix tree, so that's the piece I was wondering, if we should start with radix tree first and then on top of that build the trie? @sepehrs1378 |
Sorry but I won't be able to help. Thanks for mentioning me though. |
I have some thoughts, coming from C# land where generics are rather pathetic and non-performing (been with Go 5 years now). In my search, I looked at 20+ different implementations and every single one was meh or had essential features missing. A common choice is to have a hashtable at each node -- which is wasteful if you have a large sparse trie with many nodes (common) which also doesn't support ordinal iteration. Meanwhile, a pure radix implementation is easily wasteful (or slow) on one rune per node approach for long and/or sparse keys (common in file systems). So after finding nothing and frustrated, I bit the bullet and made a trie impl that screams, is lightweight, scales well, supports case insensitive keys at no cost, and supports forward or reverse iteration. Happy to share more and invest in this if the interest is there. Core characteristics:
|
I implemented a simple version of the trie data structure and I guess it can be a part of your project. Hope this will be helpful.
The text was updated successfully, but these errors were encountered: