3 ms·
This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some tri
by vidarh 11y ago
This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient.
The described approach doesn't seem bad, though it's a bit amusing to see this described as if it's not a very well trodden area of computer science.
[1] https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie
[2] https://en.wikipedia.org/wiki/Skip_list https://en.wikipedia.org/wiki/Skip_list
[3] https://en.wikipedia.org/wiki/Radix_tree https://en.wikipedia.org/wiki/Radix_tree
- fiatmoney 11y agoDepending on exactly how they're implemented, tries can give you unacceptable numbers of random disk seeks / uncached memory lookups per read.
- vidarh 11y agoThey can, but they certainly don't have to, especially not for a dataset like this which is small enough to re-generate offline with data suitably clustered. And certainly no reason why it'd be worse than the describe approach, which isn't really all that conceptually different. What the article described isn't necessarily bad, just unnecessarily ad-hoc when there's plenty of suitable algorithms with well understood tradeoffs and implementations.