Welcome, guest | Sign In | My Account | Store | Cart
7

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.

Python, 20 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# (IMHO) the simplest approach:
def sortedDictValues1(adict):
    items = adict.items()
    items.sort()
    return [value for key, value in items]

# an alternative implementation, which
# happens to run a bit faster for large
# dictionaries on my machine:
def sortedDictValues2(adict):
    keys = adict.keys()
    keys.sort()
    return [dict[key] for key in keys]

# a further slight speed-up on my box
# is to map a bound-method:
def sortedDictValues3(adict):
    keys = adict.keys()
    keys.sort()
    return map(adict.get, keys)

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!

13 comments

jjhegde 12 years, 8 months ago  # | flag

re: dictionary 'sort' 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
FMHj . 12 years, 4 months ago  # | flag

Sorting a list of tuples/lists... Where Alist = [(3, 4), (2, 3), (1, 2)], Alist.sort() yields [(1, 2), (2, 3), (3, 4)]. I love this language!

Daniel Schult 10 years, 10 months ago  # | flag

Sorting dictionary by values. 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))]
Muhammad Ali 10 years, 1 month ago  # | flag

newbie sort. 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
Nikos Kouremenos 9 years, 5 months ago  # | flag

typo. def sortedDictValues2(adict): keys = adict.keys() keys.sort() return [adict[key] for key in keys]

Frank P Mora 9 years, 2 months ago  # | flag

List comprehensions and the 2.4 sorted() function.

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']
sasa sasa 9 years ago  # | flag

sort_dict. 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

pepe ke 8 years, 6 months ago  # | flag

why not pass in a function to sort ??????? 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)]

>

Aylwyn Scally 8 years, 6 months ago  # | flag

or use a lambda expression. 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]))

Aylwyn Scally 8 years, 6 months ago  # | flag

oops I meant.. reverse sorting:

sorted(d.items(), lambda x, y: cmp(x[1], y[1]), reverse=True)

Travis Cline 8 years, 5 months ago  # | flag

Oh my. 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!

Alec Flett 8 years, 3 months ago  # | flag

Using the new key= parameter. 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.

Grant Jenks 8 months ago  # | flag

Deferring the sort to iteration is one technique but if you find yourself iterating often then it will kill performance. Python has a number of dictionary implementations that maintain the keys in sorted order. Consider the sortedcontainers module which is pure-Python and fast-as-C implementations. The SortedDict type is a drop-in replacement for Python's built-in dict type. There's also a performance comparison that benchmarks popular implementations against each other.

Add a comment

Sign in to comment