3 ms·
My favourite data structure: The trie
- 082349872349872 3y agomy favourite thing about tries is that they sit between lists of strings (cf extension/intension; tries are possibly exponentially better!) and finite automata (which can be useful if one wishes to share tails, and become necessary if one wishes to encode infinite sets in finite space) (can one hit all of these CS concepts by examining only two data structures? or is this path via tries didactically minimal?)
- quirino 3y agoOne of my favorite data structures is the Aho-Corasick Automaton, which combines Tries and the KMP algorithm in order to search for multiple strings in a text simultaneously. It is very elegant.
- nonrandomstring 3y agoHeard about this from someone talking about finding hash collisons fast. Most interesting. https://cp-algorithms.com/string/aho_corasick.html https://cp-algorithms.com/string/aho_corasick.html
- deleted 3y ago[deleted]
- rictic 3y agoWorth being aware that deeply nested trees are quite inefficient on modern hardware, where CPUs can execute many instructions in the time it takes for a single cache miss. There are techniques to ameliorate this somewhat, e.g. B-trees, but from a quick skim of pygtree it looks like it doesn't use them. You may get a spaghetti of nodes and pointers spread unpredictably over the heap. It's easy to end up writing code that's got good algorithmic time complexity, but where the CPU spends its time sitting cold and waiting on RAM.
- nico 3y ago> It's easy to end up writing code that's got good algorithmic time complexity, but where the CPU spends its time sitting cold and waiting on RAM It’s been interesting preparing for coding interviews. Quite a few times, the “optimal” solution time-complexity wise, is slower than the brute force solution Many of those it’s because of the inputs. If you know what they are or what their order distribution is going to be, you can usually do quite a lot better than the naive “ideal” solution
- geon 3y agoI invented the Trie when I was 19 and in college. At the time, I didn't know it already had a name and was well documented. I was just happy with how fast it was for counting words in a text file.
- ithkuil 3y agoI "invented" a mechanism for compacting GC which needs 0 bytes of scratch space to keep track of pointers to update when moving objects. Only after I "invented" it I could actually find a paper written in 1978 that was exactly "my" idea. I couldn't find it first because the terminology that paper used was quite different from the modern terminology. Only when I had a glimpse in the solution I was able to find the paper because I happened to use terms related to the solution space and not those related to the problem space
- hughdbrown 3y agoMy favorite trie implementation defines the trie as: ``` from collections import defaultdict def trie(): return defaultdict(trie) ``` Yeah, a `trie` is a dictionary whose values are tries. And the values are automatically created by reference: ``` >>> t = trie() >>> t["e"]["a"]["r"]["t"]["h"] defaultdict(<function trie at 0x10d5ebc40>, {}) ```
- gmuslera 3y agoMy favourite use for tries is for storing IPv4/IPv6 subnets, but the idea is to use compressed tries (like the Radix/Patricia tree) and storing bits, not letters. As there are usually long subchains of common blocks, are pretty efficient in the amount of nodes you have to store/traverse, and finding to which subnet an IP address belongs is pretty fast.
- amgreg 3y agoClojure’s immutable data structures are implemented as hash-array mapped tries, inspired by Phil Bagwell’s paper [1]. Other languages followed suit. [1] https://os.unil.cloud.switch.ch/tind-customer-epfl/30e62590-09cb-41af-a464-d28037cc753d?response-content-disposition=attachment%3B%20filename%2A%3DUTF-8%27%27idealhashtrees.pdf&response-content-type=application%2Fpdf&AWSAccessKeyId=ded3589a13b4450889b2f728d54861a6&Expires=1709592172&Signature=3sNF73ceu3TI%2F5puSIXrQv0MZdk%3D https://os.unil.cloud.switch.ch/tind-customer-epfl/30e62590-...
- bicsi 3y agoOne of my favourite data structures is sorting the strings lexicographically. It allows prefix search via binary search, it is memory efficient like nothing else, and 100% of the times faster than a Trie in practice. Also, who wants to limit their APIs to searching through a dictionary only by prefix, anyways?