Hacker News Reader

Comment by 6gvONxR4sf7o | Hacker News Reader

I'd love to know more about where an ordered dict comes in handy. Anyone have use cases? Otherwise, guaranteeing this behavior just seems ‾\_(ツ)_/‾

If this is useful, I wonder if an ordered set is useful.

View on HN

> If this is useful, I wonder if an ordered set is useful.

An ordered set is a unique list. It's useful. However it's not present in Python, dicts and sets have separate implementations and sets were not moved over to the ordered implementation (because the ordering was initially a side-effect of a change in implementation which was not considered useful or advantageous for sets).

An ordered multiset is a list, not an ordered set.

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?

I use OrderedDict in code that generates JSON records so the key orders are preserved to help human readability. LRU caches are another use case.

I've used TreeMap in Java many times. I don't recall exactly why I used it, I think at least some of the cases were simply that it was convenient to be able to store an ordered list of two different types without having to go through the trouble of making a full blown class that holds those types.

Reply on news.ycombinator.com