|
Title: "To sort a dictionary"
Submitter: Alex Martelli
(other recipes)
Last Updated: 2001/04/08
Version no: 1.1
Category:
Searching
|
|
 7 vote(s)
|
|
|
|
Description:
Dictionaries can't be sorted -- a mapping has no ordering! -- so, when you feel the need to sort one, you no doubt want to sort its *keys* (in a separate list). Sorting (key,value) pairs (items) is simplest, but not fastest.
Source: Text Source
def sortedDictValues1(adict):
items = adict.items()
items.sort()
return [value for key, value in items]
def sortedDictValues2(adict):
keys = adict.keys()
keys.sort()
return [dict[key] for key in keys]
def sortedDictValues3(adict):
keys = adict.keys()
keys.sort()
return map(adict.get, keys)
Discussion:
The concept of 'sort' applies only to a collection which has _order_ -- a sequence; a mapping (e.g. a dictionary) has NO order, thus it cannot be sorted. Still, its keys can be extracted as a list, which can then be sorted. The example functions return the *values in order of sorted key*, which just happens to be the single most frequent actual need corresponding to user questions such as "how do I sort a dictionary":-)
The implementation choices are interesting. Since we are sorting key-value pairs by the key field, then returning the list of value fields, it seems clearest (conceptually simplest) to architect the solution as in the first example: .items, .sort, then a list comprehension to pick the value fields.
However (at least on my machine) this turns out not to be fastest: extracting just the keys, sorting them, then accessing the dictionary for each key in the resulting list comprehension, as in the second example, appears to be speedier.
Furthermore, it is subject to a further, obvious optimization: from the dictionary we can extract just once the bound-method adict.get, which will map each key to the corresponding value, then use builtin function map to build the list obtained by applying this callable to each item in the sorted list of keys. This does indeed provide a further speed-up (again, on my machine).
Simplicity is a great virtue, but the second and third examples aren't really more complicated (or complex) than the first -- just, perhaps, a little bit subtler. They're probably worth using to 'sort' any dictionary, even though their performance advantages are really only measurable for large ones -- because uniformity of idiom is also an important programming virtue!
|
|
Add comment
|
|
Number of comments: 12
re: dictionary 'sort', Not specified Not specified, 2002/03/26
hello,
How would you sort a dictionary if the keys are not numbers or strings but tuples
e.g. {(0, 1): 2, (0, 2): 3, ...}
- JJH
Add comment
Sorting a list of tuples/lists..., FMHj ., 2002/07/12
Where Alist = [(3, 4), (2, 3), (1, 2)], Alist.sort() yields [(1, 2), (2, 3), (3, 4)]. I love this language!
Add comment
Sorting dictionary by values, Daniel Schult, 2004/01/23
Here's some code to sort the keys of a dictionary by
their associated values.
d={1:1,2:2,5:1,10:2,44:3,67:2}
items=d.items()
backitems=[ [v[1],v[0]] for v in items]
backitems.sort()
sortedlist=[ backitems[i][1] for i in range(0,len(backitems))]
Or as a function:
def sort_by_value(d):
""" Returns the keys of dictionary d sorted by their values """
items=d.items()
backitems=[ [v[1],v[0]] for v in items]
backitems.sort()
return [ backitems[i][1] for i in range(0,len(backitems))]
Add comment
newbie sort, Muhammad Ali, 2004/10/15
I just came here straight from diveintopython section on dictionaries...
Is this any different or simmilar to which solution?
def dictSort(d):
""" returns a dictionary sorted by keys """
our_list = d.items()
our_list.sort()
k = {}
for item in our_list:
k[item[0]] = item[1]
return k
Add comment
Oh my, Travis Cline, 2006/06/13
It's clear you just came over.
This will not produce expected results.
Read the top of this page.
Dictionaries do not hold ordering information!
Add comment
typo, Nikos Kouremenos, 2005/06/06
def sortedDictValues2(adict):
keys = adict.keys()
keys.sort()
return [*a*dict[key] for key in keys]
Add comment
List comprehensions and the 2.4 sorted() function, Frank P Mora, 2005/09/15
The 2.4 new sorted() function is grand, especially in list abstractions.
>>> di= dict(zip("e d c b a".split(),"egbdf dec cdr both any".split()))
>>> di.keys()
['a', 'c', 'b', 'e', 'd']
>>> di.items()
[('a', 'any'), ('c', 'cdr'), ('b', 'both'), ('e', 'egbdf'), ('d', 'dec')]
## sort by key
>>> [ (k,di[k]) for k in sorted(di.keys())] ## (k,v) tuples in resulting list
[('a', 'any'), ('b', 'both'), ('c', 'cdr'), ('d', 'dec'), ('e', 'egbdf')]
>>> [ di[k] for k in sorted(di.keys())] ## values only in resulting list
['any', 'both', 'cdr', 'dec', 'egbdf']
## sort by value (there is no elegant way to get the key from the value)
>>> [ k for k in sorted(di.values())] ## values (sorted) only in result
['any', 'both', 'cdr', 'dec', 'egbdf']
Add comment
sort_dict, sasa sasa, 2005/11/15
This would sort the dictionary by the field (numeric column) you supply and return the result in form of a list.
def sort_dict(dictionary, field):
tmp_list = []
for key, value in dictionary.items():
tmp_list.append([key, value])
tmp_list.sort(key=lambda x:x[field])
return tmp_list
Add comment
why not pass in a function to sort ???????, pepe ke, 2006/05/24
strange people, making fast things slow, easy things hard
sorting by value ...
>>> def sortfunc(x,y):
... return cmp(x[1],y[1])
...
>>> lijst={'een':1,'drie':3,'vier':4,'twee':2}
>>> items=lijst.items()
>>> items
[('drie', 3), ('vier', 4), ('een', 1), ('twee', 2)]
>>> items.sort(sortfunc)
>>> items
[('een', 1), ('twee', 2), ('drie', 3), ('vier', 4)]
>>> items.sort()
>>> items
[('drie', 3), ('een', 1), ('twee', 2), ('vier', 4)]
>>>
of course reverse sorting would be
>>> def sortfunc(x,y):
... return cmp(y[1],x[1])
...
>>> items.sort(sortfunc)
>>> items
[('vier', 4), ('drie', 3), ('twee', 2), ('een', 1)]
>>>
or without the need for an extra list
>>> sorted(lijst.items(),sortfunc)
[('vier', 4), ('drie', 3), ('twee', 2), ('een', 1)]
>>>
Add comment
or use a lambda expression, Aylwyn Scally, 2006/05/25
sorting dictionary d by value:
> sorted(d.items(), lambda x, y: cmp(x[1], y[1]))
and reverse sorting:
> sorted(d.items(), lambda x, y: cmp(x[1], y[1]))
Add comment
oops I meant.., Aylwyn Scally, 2006/05/25
reverse sorting:
> sorted(d.items(), lambda x, y: cmp(x[1], y[1]), reverse=True)
Add comment
Using the new key= parameter, Alec Flett, 2006/08/25
With python 2.4 you have the key= parameter, so you can say:
sorted(d.items(), key=lambda (k,v): (v,k))
key returns the "sort key" that sort will do the comparison on.
Add comment
|
|
|
|
