Credit: Alex Martelli, Raymond Hettinger
You want to sort a dictionary. Because sorting is a concept that only makes sense for sequences, this presumably means that you want a sequence of the values of the dictionary in the order obtained by sorting the keys.
The simplest approach is to sort the items (i.e., key/value pairs), then pick just the values:
def sortedDictValues1(adict): items = adict.items( ) items.sort( ) return [value for key, value in items]
However, an alternative implementation that sorts just the keys, then uses them to index into the dictionary to build the result, happens to run more than twice as fast (for a dictionary of a few thousand entries) on my system:
def sortedDictValues2(adict): keys = adict.keys( ) keys.sort( ) return [adict[key] for key in keys]
A further small speed-up (15% on my system) is to perform the last
step by mapping a bound method. map
is often
marginally faster than a list comprehension when no
lambda
is involved:
def sortedDictValues3(adict): keys = adict.keys( ) keys.sort( ) return map(adict.get, keys)
A really tiny extra speed-up (about 3% on my system) is available in
Python 2.2 by using adict._ _getitem_ _
rather
than adict.get
in this latest, bound-method
version.
The concept of sorting applies only to a collection that has order—in other words, a sequence. A mapping, such as a dictionary, has no order, so it cannot be sorted. And yet, “How do I sort a dictionary?” is a frequent question on the Python lists. More often than not, the question is about sorting some sequence of keys and/or values from the dictionary.
A dictionary’s keys can be extracted as a list, which can then be sorted. The functions in this recipe return the values in order of sorted keys, which corresponds to the most frequent actual need when it comes to sorting a dictionary. Another frequent need is sorting by the values in the dictionary, for which you should see Recipe 17.7.
The implementation choices are interesting. Because we are sorting key/value pairs by the key field and returning only the list of value fields, it seems conceptually simplest to use the first solution, which gets a list of the key/value pairs, sorts them, and then uses a list comprehension to pick the values. However, this is not the fastest solution. Instead, with Python 2.2, on dictionaries of a few thousand items, extracting just the keys, sorting them, and then accessing the dictionary for each key in the resulting list comprehension—the second solution—appears to be over twice as fast.
This faster approach can be further optimized by extracting the bound
method
adict.get
,
which turns each key into its corresponding value, and then using the
built-in function map
to build the list by
applying this callable to each item in the sorted list of keys. In
Python 2.2, using adict._ _getitem_ _
rather than
adict.get
is even a little bit better (probably
not enough to justify making your program version-dependent, but if
you’re already dependent on Python 2.2 for other
reasons, you may as well use this approach).
Simplicity is one the greatest virtues for any program, but the second and third solutions aren’t really more complicated than the first; they are just, perhaps, a little bit more subtle. Those solutions are probably worth using to sort any dictionary, even though their performance advantages are really measurable only for very large ones.
Recipe 17.7 for another application of sorting on dictionaries.