3 ms·
It is refreshing to see a data structure "explained" without a drawing of some boxes and arrows. +1 there for the creativity -- I'd be even more pleased to see
by no_protocol 10y ago
It is refreshing to see a data structure "explained" without a drawing of some boxes and arrows. +1 there for the creativity -- I'd be even more pleased to see a data structure explained with words without relying on images at all.
Also:
...to check if a word exists in the text file, it takes
at most, as many operations as the length of the word
itself. Much better than the 235,887 operations it
was going to take before.
But your source for the words (/usr/share/dict/words) is probably already sorted! I don't think that's a fair upper bound to quote.
- rocqua 10y agoStill, trie lookup time is independent from your dictionary size. Sadly, in practice they are hurt by the many pointer dereferences of traversing the tree. If you have a sorted list of strings, you can speed up the search by tracking how many starting characters on the left and right boundary of your interval already match the given word. In practice, this turns out to be almost as good as tries as most steps eliminate quite a few characters to check. If you like theory, you can add on Range Minimal Query to get the same theoretical performance as tries. In practice though, this isn't necessary.