4 ms·
The performance gap between unordered_map<> and the custom implementations seems to be less than 2X. This will quickly evaporate if one uses an efficient hash s
by utopcell 10y ago
The performance gap between unordered_map<> and the custom implementations seems to be less than 2X. This will quickly evaporate if one uses an efficient hash such as dense_hash_map<>.
- rocqua 10y agoFor the trie, things would be a lot better if the words got longer. All the 'inefficiencies' of a trie lie in the pointer chasing. The great thing is that you can process a string 'on-line'. If things start getting really big, there are some tricks with LCP-arrays and constant time RMQ (range minimal query) that have great theoretical performance. I haven't seen that stuff in practice though.
- emmelaich 10y agoYou could even do better and use a perfect hash if you have known constant list of strings.