排序python 3.7+字典的最快方法 [英] Fastest way to sort a python 3.7+ dictionary
问题描述
现在，可以保证 Python字典的插入顺序从Python 3.7开始(以及在CPython 3.6中 )，字典排序的最佳/最快方法是什么-按值和按键排序?
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?
请注意，此问题不是重复的，因为先前有关如何对字典进行排序的问题已经过时了(答案基本上是您不能；请改用collections.OrderedDict ).
Note that this question is not a duplicate since previous questions about how to sort a dictionary are out of date (to which the answer was, basically, You can't; use a collections.OrderedDict instead).
推荐答案
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))}
在具有sys.version的macbook上进行了测试:
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)]
一次性设置为1000个浮点数的
One-time setup with a dict of 1000 floats:
>>> import random
>>> 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)
注意:真实世界的数据通常包含已排序序列的较长序列，Timsort算法可以利用这些序列.如果对字典进行排序是您的捷径，那么建议您在得出关于最佳方法的任何结论之前，使用自己的典型数据在自己的平台上进行基准测试.我在每个时间结果上都添加了一个注释字符(#)，以便IPython用户可以复制/粘贴整个代码块，以便在自己的平台上重新运行所有测试.
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.
这篇关于排序python 3.7+字典的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
