python - 在字典python中查找前k个最大的键

Question

假设我有一本字典：

{key1:value1........... keyn:valuen}

所以可以说我想写一个函数

def return_top_k(dictionary, k):

    return list_of_keys_sorted   

什么是最有效的方法（就大 O 而言）来获取具有最高 k 值的键（保持顺序，即最高值的键出现在开头......等等。）

Answer 1

O(n log k)：

import heapq

k_keys_sorted = heapq.nlargest(k, dictionary)

您可以使用key关键字参数来指定应该用作排序键的内容，例如：

k_keys_sorted_by_values = heapq.nlargest(k, dictionary, key=dictionary.get)

Answer 2

return sorted(dictionary, key=dictionary.get, reverse=True)[:10]

应该是最坏的O(NlogN)（虽然heapq别人提出的可能更好）......

使用 a而不是常规字典也可能有意义。Counter在这种情况下，该most_common方法将（大约）执行您想要的操作（ ），但前提是在您的 APIdictionary.most_common(10)中使用 a 是有意义的。Counter

Answer 3

portfolio = [
   {'name': 'IBM', 'shares': 100, 'price': 91.1},
   {'name': 'AAPL', 'shares': 50, 'price': 543.22},
   {'name': 'FB', 'shares': 200, 'price': 21.09},
   {'name': 'HPQ', 'shares': 35, 'price': 31.75},
   {'name': 'YHOO', 'shares': 45, 'price': 16.35},
   {'name': 'ACME', 'shares': 75, 'price': 115.65}
]

cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

Answer 4

前 3 名：

>>> from operator import itemgetter
>>> dct = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}
>>> sorted(dct.items(), key=itemgetter(1), reverse=True)
[('e', 5), ('d', 4), ('c', 3), ('b', 2), ('a', 1)]
>>> map(itemgetter(0), sorted(dct.items(), key=itemgetter(1), reverse=True))
['e', 'd', 'c', 'b', 'a']
>>> map(itemgetter(0), sorted(dct.items(), key=itemgetter(1), reverse=True))[:3]
['e', 'd', 'c']

或使用heapq模块

>>> import heapq
>>> from operator import itemgetter
>>> heapq.nlargest(3, dct.items(), key=itemgetter(1))
[('e', 5), ('d', 4), ('c', 3)]
>>> map(itemgetter(0), _)
['e', 'd', 'c']

Answer 5

在代码中

dct = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5}
k = 3
print sorted(dct.keys(), reverse=True)[:k]

如果您还需要值：

print sorted(dct.items(), reverse=True)[:k]

或者，如果您想使用OrderedDict：

from collections import OrderedDict
d = OrderedDict(sorted(dct.items(), reverse=True))
print d.keys()[:k]

Answer 6

所以如果你想从字典中打印前 K 个频繁元素；你必须使用 heapq.nlargest 函数。

这是相同的示例：

return heapq.nlargest(k,count.keys(), key = count.get)

这里，k 是帮助我们找出在字典中重复 k 次或超过 k 次的元素的数字。

count.keys()：这为您提供了使用创建的堆中的键或元素collections.counter

key = count.get()：这用于打印堆的键。如果我们跳过这个；它将打印字典的值，即元素在字典中出现的次数。