28

Now that the insertion order of Python dictionaries is guaranteed starting in Python 3.7 (and in CPython 3.6), what is the best/fastest way to sort a dictionary - both by value and by key?

The most obvious way to do it is probably this:

by_key = {k: dct[k] for k in sorted(dct.keys())}
by_value = {k: dct[k] for k in sorted(dct.keys(), key=dct.__getitem__)}

Are there alternative, faster ways to do this?

(Note that the answer prior to 3.7 was, basically, You can't; use a collections.OrderedDict instead).

Rick
  • 43,029
  • 15
  • 76
  • 119
  • This is just going to amount to profiling a bunch of versions of this same code. Like, why favor `{k: dct[k] ...` when you could do `{k: v` and use `items()` in place of `keys()`. The by value is just the same but with `operator.itemgetter(1)` as the key. – g.d.d.c May 23 '18 at 17:11
  • @g.d.d.c I thought it was possible what you are saying might be the case (thus making this a boring question) but thought I would ask anyway since there might be an interesting outside-the-box way I'm not aware of. Since this is *very new*, I assume the proper idiom is not yet established. – Rick May 23 '18 at 17:15
  • Fair. IMHO, I'd just wait for the community to add a sort method to the underlying dictionary class (now that they're ordered) and I'd bet you see something like `def sort(byValues = False)`, so by default it sorts by keys, but with a call like `sort(True)` you get sort by values (or something along those lines). – g.d.d.c May 23 '18 at 17:18
  • 1
    @g.d.d.c I expect you are right. A mutable ordered thing that can't be sorted-in-place feels like an anti-pattern. – Rick May 23 '18 at 17:19
  • 6
    The least code to sort by key is `dict(sorted(dct.items())` – kindall May 23 '18 at 17:21

1 Answers1

37

TL;DR: Best ways to sort by key or by value (respectively), in CPython 3.7:

{k: d[k] for k in sorted(d)}
{k: v for k,v in sorted(d.items(), key=itemgetter(1))}

Tested on a macbook with sys.version:

3.7.0b4 (v3.7.0b4:eb96c37699, May  2 2018, 04:13:13)
[Clang 6.0 (clang-600.0.57)]

One-time setup with a dict of 1000 floats:

>>> import random
>>> from operator import itemgetter
>>> random.seed(123)
>>> d = {random.random(): random.random() for i in range(1000)}

Sorting numbers by key (best to worst):

>>> %timeit {k: d[k] for k in sorted(d)}
# 296 µs ± 2.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: d[k] for k in sorted(d.keys())}
# 306 µs ± 9.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit dict(sorted(d.items(), key=itemgetter(0)))
# 345 µs ± 4.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=itemgetter(0))}
# 359 µs ± 2.42 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit dict(sorted(d.items(), key=lambda kv: kv[0]))
# 391 µs ± 8.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit dict(sorted(d.items()))
# 409 µs ± 9.33 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: v for k,v in sorted(d.items())}
# 420 µs ± 5.39 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=lambda kv: kv[0])}
# 432 µs ± 39.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Sorting numbers by value (best to worst):

>>> %timeit {k: v for k,v in sorted(d.items(), key=itemgetter(1))}
# 355 µs ± 2.24 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit dict(sorted(d.items(), key=itemgetter(1)))
# 375 µs ± 31.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=lambda kv: kv[1])}
# 393 µs ± 1.89 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit dict(sorted(d.items(), key=lambda kv: kv[1]))
# 402 µs ± 9.74 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: d[k] for k in sorted(d, key=d.get)}
# 404 µs ± 3.55 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: d[k] for k in sorted(d, key=d.__getitem__)}
# 404 µs ± 20.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit {k: d[k] for k in sorted(d, key=lambda k: d[k])}
# 480 µs ± 12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

One-time setup with a large dict of strings:

>>> import random
>>> from pathlib import Path
>>> from operator import itemgetter
>>> random.seed(456)
>>> words = Path('/usr/share/dict/words').read_text().splitlines()
>>> random.shuffle(words)
>>> keys = words.copy()
>>> random.shuffle(words)
>>> values = words.copy()
>>> d = dict(zip(keys, values))
>>> list(d.items())[:5]
[('ragman', 'polemoscope'),
 ('fenite', 'anaesthetically'),
 ('pycnidiophore', 'Colubridae'),
 ('propagate', 'premiss'),
 ('postponable', 'Eriglossa')]
>>> len(d)
235886

Sorting a dict of strings by key:

>>> %timeit {k: d[k] for k in sorted(d)}
# 387 ms ± 1.98 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: d[k] for k in sorted(d.keys())}
# 387 ms ± 2.87 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit dict(sorted(d.items(), key=itemgetter(0)))
# 461 ms ± 1.61 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit dict(sorted(d.items(), key=lambda kv: kv[0]))
# 466 ms ± 2.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=itemgetter(0))}
# 488 ms ± 10.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=lambda kv: kv[0])}
# 536 ms ± 16.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit dict(sorted(d.items()))
# 661 ms ± 9.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: v for k,v in sorted(d.items())}
# 687 ms ± 5.38 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Sorting a dict of strings by value:

>>> %timeit {k: v for k,v in sorted(d.items(), key=itemgetter(1))}
# 468 ms ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit dict(sorted(d.items(), key=itemgetter(1)))
# 473 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit dict(sorted(d.items(), key=lambda kv: kv[1]))
# 492 ms ± 9.06 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: v for k,v in sorted(d.items(), key=lambda kv: kv[1])}
# 496 ms ± 1.87 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: d[k] for k in sorted(d, key=d.__getitem__)}
# 533 ms ± 5.33 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: d[k] for k in sorted(d, key=d.get)}
# 544 ms ± 6.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit {k: d[k] for k in sorted(d, key=lambda k: d[k])}
# 566 ms ± 5.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Note: Real-world data often contains long runs of already-sorted sequences, which Timsort algorithm can exploit. If sorting a dict lies on your fast path, then it's recommended to benchmark on your own platform with your own typical data before drawing any conclusions about the best approach. I have prepended a comment character (#) on each timeit result so that IPython users can copy/paste the entire code block to re-run all the tests on their own platform.

wim
  • 338,267
  • 99
  • 616
  • 750
  • I consistently get similar results for sorting numbers by key, but different results for sorting numbers by value. – hilberts_drinking_problem May 28 '18 at 15:25
  • Really nice timing analysis. So some key observations seem to be: `dict` is faster then dict-comprehension, but tie-breaking on tuples is more costly then using a key-function for comparing just the key, and for that, using `itemgetter` is faster then lambda. – tobias_k May 28 '18 at 16:00
  • (That is, on closer look, particularly for sort-by-value, `dict` seems to be slower than dict-coprehension...) I think this would really benefit from some sort of visual/tabular overview. – tobias_k May 28 '18 at 16:06
  • The longer I look at it, the less sense it makes... using `itemgetter`, the difference between `dict` and dict-comp is 15µs, all else being the same, but using `lambda` it's 40µs. And sorting by value, `dict` is _slower_ than both the dict-comp equivalents. Getting similar results here, though. Do you know any explanation for that? – tobias_k May 28 '18 at 16:17
  • The timings seem fairly similar and will no doubt vary depending on the specifics of the data and the system used for testing, so is the TL;DR conclusion warranted? `dict(sorted(d.items()))` feels more idiomatic IMO – Chris_Rands Nov 13 '18 at 10:50