My favourite data structure: The trie | Hacker News Reader

My favourite data structure: The trie

jamesg.blog

40 pointsthunderbong11 comments

Worth 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.

> 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

Clojure’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-...

One 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.

Heard about this from someone talking about finding hash collisons fast. Most interesting.

https://cp-algorithms.com/string/aho_corasick.html

my 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?)

My 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.

One 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?

My 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>, {})

```

I 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.

I "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

Reply on news.ycombinator.com