3 ms·
What's wrong with this? What would be the alternative? A preallocated array of 26 (or more if you account for special chars) for each node?
by nuggien 10y ago
What's wrong with this? What would be the alternative? A preallocated array of 26 (or more if you account for special chars) for each node?
- Jach 10y agoI recently wrote a basic trie in Nim for fun, I started with a preallocated array and then rewrote parts to hashtables, it's simpler since you don't need to care about the dictionary size and it can have space savings depending on how the table grows. It wouldn't surprise me if there was a fancy bitmapping approach though, or if you could be more efficient if you had n-gram statistics. (And as mentioned elsewhere for the purposes of storing/searching a dictionary you could just have a flat hashtable indexed by the words, or a bloom filter if you only care about certainly not existing...)