Hacker News new | past | comments | ask | show | jobs | submit login

Imagine a trie implemented as a tree of dictionaries (ignore thinking about whether a tree of arrays may actually be better for now). Let’s say you want to implement an autocomplete algorithm based on a dictionary of words from a corpus. The autocomplete algorithm is naive: if a user types in “abc” you recommend whichever word starting in “abc” has the most occurrences in the corpus.

With ordered dicts you can use the trie to compute your autocomplete very quickly with no additional data structures. There are lots of other trie operations which are more efficient with ordered dicts too. I’m sure someone can come up with less complicated examples but this was the first one I thought of




This isn't a sorted dictionary, it's an insertion order dictionary.


Well, you can convert any sorted dictionary to an insertion order dictionary by copying it over, but that does the make the original example pretty clunky.

I guess a better use case is if you needed some sort of priority/FIFO logic along with indexing. Hard to think of something that doesn’t feel contrived, but I guess imagine having a queue where determining membership or updating fields of an element based on ID can be done in O(1) for any element?




Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: