python - 如何在 python 中的堆中维护字典？

Question

我有一个字典如下:

{'abc':100,'xyz':200,'def':250 .............}

它是一个字典，键作为实体的名称，值是该实体的计数。我需要从字典中返回前 10 个元素。

我可以写一个堆来做到这一点，但我不确定如何将值映射到键，因为某些值是相等的。

有没有其他数据结构可以做到这一点？

Answer 1

使用 heapq 你可能想做这样的事情:

heap = [(-value, key) for key,value in the_dict.items()]
largest = heapq.nsmallest(10, heap)
largest = [(key, -value) for value, key in largest]

请注意，由于 heapq 仅实现了一个最小堆，因此最好将值反转，以便更大的值变得更小。

对于小尺寸的堆，此解决方案会更慢，例如:

>>> import random
>>> import itertools as it
>>> def key_generator():
...     characters = [chr(random.randint(65, 90)) for x in range(100)]
...     for i in it.count():
...             yield ''.join(random.sample(characters, 3))
... 
>>> the_dict = dict((key, random.randint(-500, 500)) for key, _ in zip(key_generator(), range(3000)))
>>> def with_heapq(the_dict):
...     items = [(-value, key) for key, value in the_dict.items()]
...     smallest = heapq.nsmallest(10, items)
...     return [-value for value, key in smallest]
... 
>>> def with_sorted(the_dict):
...     return sorted(the_dict.items(), key=(lambda x: x[1]), reverse=True)[:10]
... 
>>> import timeit
>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
0.9220538139343262
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
1.2792410850524902

对于 3000 个值，它只比 sorted 版本快一点，后者是 O(nlogn) 而不是 O(n + mlogn) .如果我们将 dict 的大小增加到 10000，heapq 版本会变得更快:

>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
2.436316967010498
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
3.585728168487549

时间可能还取决于您运行的机器。您可能应该分析哪种解决方案最适合您的情况。如果效率不是很重要，我建议使用 sorted 版本，因为它更简单。