[Tutor] Dictionary, sorting -> list

Tim Peters tim_one@email.msn.com
Sat, 4 Dec 1999 17:12:13 -0500

[Neil Conway]
> ...
> My problem today is that I have a dictionary, like so:
> >>> results = {}
> >>> results['page1'] = 2
> >>> results['page2'] = 4
> >>> results['page3'] = 7
> Given input like the above, I would like to return input like so:
> ['page3','page2',page1']
> #ranked from highest corresponding dict value to lowest


for a helpful tutorial about sorting in Python.

> I need to do this for a large dictionary, which could be 1000 or more
> items long.

1000 items is small to a computer!  1000000 would be pretty big, though.

> ...
> I've been thinking about this for a while, and haven't been able
> to come up with a good solution.

This is faster than you might expect:

def keys_by_increasing_values(d):
    "d -> return list of dict d's keys k in increasing order of d[kj."

    result = []
    for key, value in d.items():
        result.append((value, key))
    # Strip out the values.
    for i in xrange(len(result)):
        result[i] = result[i][1]
    return result

def keys_by_decreasing_values(d):
    "d -> return list of dict d's keys k in decreasing order of d[kj."

    result = keys_by_increasing_values(d)
    return result

print keys_by_decreasing_values(
    {'page1': 2,
     'page2': 4,
     'page3': 7})

For large dicts, the single line


dominates the runtime, and since sort() is implemented in C via a
near-optimal sorting algorithm, you're not going to find anything
essentially faster than this.  Faster methods are possible if you can put
severe restrictions on the possible set of values (e.g., if you know in
advance that 2, 4 and 7 are the only possible values -- stuff like that).

orderedly y'rs  - tim