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

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和高效（内存消耗，执行速度 - 当我有一个包含1000000个元素的字典时）的方法是什么？生成器、lambda函数还是其他方法？

附加内容1：它们是一些类似的问题：

在Python字典中找到5个最大值

从字典中获取前几个值

它们也可能包含解决方案，但它们没有询问在处理大型数据集时最高效、最pythonic的方法。

- lospejos

---

你可以选择这个从字典中获取前几个值的方法，也可以选择其他方式。 - Lafexlos

@Lafexlos 嗯，我更喜欢 https://dev59.com/NGct5IYBdhLWcg3wqvXL 这个。 - Remi Guan

Answer 1

heapq.nlargest 是处理从大量输入数据中获取少量最大值的正确方法。它使用堆(heap)数据结构，能够在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的内存节省将会获胜。

对于计算机科学理论极客来说，对于大小为n的输入，选择k个最大值的heapq.nlargest需要O(n log k)的计算和k的存储。而使用sorted排序后再进行切片则需要O(n log n)的计算和n的存储。因此，对于1024个输入和4个选定项，nlargest所需的工作量约为1024 * 2次计算，需要4个存储空间；而sorted + 切片则需要约1024 * 10次计算，需要1024个存储空间。实际上，在sorted中使用的TimSort具有比大O符号表达更低的开销，并且通常比大O符号表示的性能要好，这就是为什么例如从1024个项目中选择前200个项目时，sorted + 切片仍然可能获胜，但nlargest对于巨大的输入和输出缺乏病理退化；它可能会偶尔慢一些，但通常不会慢太多，而sorted可以更快，但也可能更慢。

- ShadowRanger

Answer 2

查看collections.Counter.most_common()方法的源代码。这是最佳解决方案。当然，最好的方法是使用Counter()而不是{}。

def most_common(self, n=None):
    '''List the n most common elements and their counts from the most
    common to the least.  If n is None, then list all element counts.

    >>> Counter('abcdeabcdabcaba').most_common(3)
    [('a', 5), ('b', 4), ('c', 3)]

    '''
    # Emulate Bag.sortedByCount from Smalltalk
    if n is None:
        return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
    return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))

- d2207197