Python 3.7+字典排序的最快方法

Question

Python 3.7+字典排序的最快方法

28

既然从Python 3.7开始（以及在CPython 3.6中），Python字典的插入顺序是有保证的，那么排序字典的最佳/最快方法是什么？无论是按值还是按键进行排序，最明显的方式可能是这样：

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__)}

有没有其他更快的方法来做这个？

（请注意，在3.7之前的答案基本上是，你不能；而是使用一个collections.OrderedDict代替）。

- Rick

这只是对同一代码的多个版本进行分析。例如，为什么要使用{k: dct[k] ...而不是{k: v并在keys()的位置使用items()。按值排序只需使用operator.itemgetter(1)作为键即可。 - g.d.d.c

@g.d.d.c 我认为你所说的可能是可能的（因此使这个问题变得无聊），但我还是想问一下，因为可能有一种我不知道的有趣的创新方式。由于这是非常新的，我认为适当的习语尚未确立。 - Rick

公平。在我看来，我会等待社区为底层字典类添加排序方法（现在它们是有序的），我敢打赌你会看到类似于def sort(byValues = False)的东西，所以默认情况下按键排序，但使用sort(True)这样的调用可以按值排序（或类似的方式）。 - g.d.d.c

1

@g.d.d.c 我认为你是对的。一个可变的有序对象，无法原地排序，感觉像是一种反模式。 - Rick

6

按键排序的最少代码是 dict(sorted(dct.items()))。 - kindall

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wim · Accepted Answer

TL;DR：在CPython 3.7中按键或值（分别）排序的最佳方法：

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

在MacBook上测试，使用sys.version：

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

使用包含1000个浮点数的字典进行一次设置：

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

按键排序数字（从最好到最差）：

>>> %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)

按数值排序（从高到低）：

>>> %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)

一次性使用包含大量字符串的字典进行设置：

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

按键对字符串字典进行排序：

>>> %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)

按值排序字符串字典：

>>> %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：现实世界的数据通常包含已排序序列的长串，这是Timsort算法可以利用的。如果字典排序在您的快速路径上，则建议使用自己平台上的典型数据进行基准测试，然后再得出任何有关最佳方法的结论。我在每个timeit结果前添加了一个注释字符（#），以便IPython用户可以复制/粘贴整个代码块以在自己的平台上重新运行所有测试。