Python 从字典中获取 N 个最大值

Question

假设我们有字典：

items = {'a': 7, 'b': 12, 'c': 9, 'd': 0, 'e': 24, 'f': 10, 'g': 24}

我想得到另一个字典，其中包含 4 个具有最大值的元素。例如，我希望得到：

subitems = {'e': 24, 'g': 24, 'b': 12, 'f': 10}

什么将是最 Pythonic 和最有效的（内存消耗，执行速度 - 当 fe 我将拥有 1000000 个元素的 dict）方法来做到这一点？生成器、lambda 表达式，还有别的东西吗？

Answer 1

heapq.nlargest当问题是“如何从大量输入中获得少量最大值？”时，它总是正确的答案。通过使用堆，它比您在 Python 中可以做的任何事情都更好地减少了内存使用和 CPU 使用。例子：

import heapq
from operator import itemgetter

n = 3

items = {'a': 7, 'b': 12, 'c': 9, 'd': 0, 'e': 24, 'f': 10, 'g': 24}

topitems = heapq.nlargest(n, items.items(), key=itemgetter(1))  # Use .iteritems() on Py2
topitemsasdict = dict(topitems)

sorted当请求的最大项目数占输入的很大比例时，切片结果可以获胜，但对于大量输入和少量最大项目，节省的内存heapq.nlargest将获胜。

对于 CS 理论极客，heapq.nlargest对于大小为 的输入n，选择k最大值，需要O(n log k)计算和k存储。sorted其次是切片需要O(n log n)计算和n存储。因此，对于 1024 个输入和 4 个选定项，工作为nlargest~1024 * 2计算，需要 4 个存储；sorted+ 切片将是 ~1024 * 10计算，存储为 1024。在实践中，Python 中使用的 TimSort 的sorted开销比 big-O 表示法可以正确传达的要低，并且通常比 big-O 表示法表现得更好，这就是为什么，比如说，从 1024 个项目中选择前 200 个项目，sorted+ 切片仍然可以获胜，但是nlargest对巨大的投入和产出缺乏病理性退化；可能有时慢，但它通常是慢不了多少，在这里整理可以更快，但它也可以是多慢。