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版本，因为它更简单。

Answer 2

使用堆是具有时间复杂度的最佳解决方案：O(nlogk)。其中n是堆的长度，k在这里是10。

现在键映射的技巧是我们可以创建另一个类来比较键并定义魔术方法__lt__() __gt__()。覆盖 < , > 运算符

import heapq
class CompareWord:
  def __init__(self , word , value):
    self.word = word
    self.value = value

  def __lt__(self, other):   #To override > operator
    return self.value < other.value

  def __gt__(self , other):  #To override < operator
    return self.value > other.value

  def getWord(self):
    return self.word

def findKGreaterValues(compare_dict , k):
  min_heap = []
  for word in compare_dict:
      heapq.heappush(min_heap , CompareWord(word ,compare_dict[word] ))
      if(len(min_heap) > k):
          heapq.heappop(min_heap)   
  answer = []
  for compare_word_obj in min_heap:
      answer.append(compare_word_obj.getWord())

  return answer

Answer 3

为了获取前 10 个元素，假设数字在第二位：

from operator import itemgetter

topten = sorted(mydict.items(), key=itemgetter(1), reverse = True)[0:10]

如果要按值排序，则 key 只需将其更改为key=itemgetter(1,0).

至于数据结构，堆听起来像你想要的。只需将它们保留为元组，然后比较数字项。

Answer 4

如果字典保持不变，那么您可以尝试使用值作为键以相反的顺序对字典项进行排序，然后从中获取前 10 个元素，而不是尝试直接或通过collections.Counter创建heapq 。您需要从元组重新创建字典

>>> some_dict = {string.ascii_lowercase[random.randint(0,23):][:3]:random.randint(100,300) for _ in range(100)}
>>> some_dict
{'cde': 262, 'vwx': 175, 'xyz': 163, 'uvw': 288, 'qrs': 121, 'mno': 192, 'ijk': 103, 'abc': 212, 'wxy': 206, 'efg': 256, 'opq': 255, 'tuv': 128, 'jkl': 158, 'pqr': 291, 'fgh': 191, 'lmn': 259, 'rst': 140, 'hij': 192, 'nop': 202, 'bcd': 258, 'klm': 145, 'stu': 293, 'ghi': 264, 'def': 260}
>>> sorted(some_dict.items(), key = operator.itemgetter(1), reverse = True)[:10]
[('stu', 293), ('pqr', 291), ('uvw', 288), ('ghi', 264), ('cde', 262), ('def', 260), ('lmn', 259), ('bcd', 258), ('efg', 256), ('opq', 255)]

如果您使用 heapq，要创建堆，则需要nlogn操作，如果您通过插入元素来构建堆，或者logn如果您堆化列表，则需要mlogn操作以获取顶部m元素

如果您正在对项目进行排序，则 Python 排序算法保证O(nlogn)在最坏的情况下（请参阅TIM Sort）并且获取前 10 个元素将是一个常量操作

Answer 5

您可以在您的类中实现lt函数，您可以在其中指定应该比较哪些属性。

def __lt__(self, other):
   return self.attribute if self.attribute < other else other

Answer 6

想象一个像这样的字典（a-za=1 和 z=26 的映射）：

>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d
{'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24}

现在你可以这样做：

>>> v=list(d.values())
>>> k=list(d.keys())
>>> [k[v.index(i)] for i in sorted(d.values(),reverse=True)[0:10]]
['z', 'y', 'x', 'w', 'v', 'u', 't', 's', 'r', 'q']

您还声明映射的某些值将相等。现在让我们更新d，使其具有A-Z映射 1-26 的字母：

>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(26)),range(1,27))})

现在两者都A-Z映射a-z到1-26：

>>> d
{'G': 7, 'F': 6, 'E': 5, 'D': 4, 'C': 3, 'B': 2, 'A': 1, 'O': 15, 'N': 14, 'M': 13, 'L': 12, 'K': 11, 'J': 10, 'I': 9, 'H': 8, 'W': 23, 'V': 22, 'U': 21, 'T': 20, 'S': 19, 'R': 18, 'Q': 17, 'P': 16, 'Z': 26, 'Y': 25, 'X': 24, 'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24} 

因此，对于重复映射，唯一合理的结果是返回具有值的键列表：

>>> [[k[x] for x,z in enumerate(v) if z==i ] for i in sorted(d.values(),reverse=True)[0:10]]
[['Z', 'z'], ['Z', 'z'], ['Y', 'y'], ['Y', 'y'], ['X', 'x'], ['X', 'x'], ['W', 'w'], ['W', 'w'], ['V', 'v'], ['V', 'v']]

你可以在这里使用 heapq：

[[k[x] for x,z in enumerate(v) if z==i ] for i in heapq.nlargest(10,v)]

您没有说明要对重复结果做什么，所以我假设您希望在结果列表保持 N 长的同时消除这些重复项。

这样做：

def topn(d,n):
    res=[]
    v=d.values()
    k=d.keys()
    sl=[[k[x] for x,z in enumerate(v) if z==i] for i in sorted(v)]
    while len(res)<n and sl:
        e=sl.pop()
        if e not in res:
            res.append(e)

    return res

>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(0,26,2)),range(1,27,2))})  
>>> topn(d,10)
[['z'], ['Y', 'y'], ['x'], ['W', 'w'], ['v'], ['U', 'u'], ['t'], ['S', 's'], ['r'], ['Q', 'q']]

Answer 7

Bakuriu 的回答是正确的（使用 heapq.nlargest）。

但是，如果您对使用正确的算法感兴趣，quickselect使用与快速排序类似的原理，并且是由同一个人发明的：CAR Hoare。

但是，它的不同之处在于没有对数组进行完全排序：完成后，如果您要求前 n 个元素，那么它们位于数组中的前 n 个位置，但不一定按排序顺序。

与快速排序一样，它首先选择一个枢轴元素并旋转数组，以使所有 a[:j] 小于或等于 a[j] 并且所有 a[j+1:] 都大于 a[j]。

接下来，如果 j == n，那么最大的元素是 a[:j]。如果 j > n，则仅在枢轴左侧的元素上递归调用快速选择。如果 j < n 则在枢轴右侧的元素上调用 quickselect 以从中提取 n - j - 1 个最大的元素。

因为 quickselect 只在数组的一侧被递归调用（不像 quicksort 在两边都被递归调用），它在线性时间内工作（如果输入是随机排序的，并且没有重复的键）。这也有助于将递归调用转换为 while 循环。

这是一些代码。为了帮助理解它，外部 while 循环中的不变量是元素 xs[:lo] 保证在 n 最大的列表中，并且元素 xs[hi:] 保证不在 n 最大的列表中。

import random

def largest_n(xs, n):
    lo, hi = 0, len(xs)
    while hi > n:
        i, j = lo, hi
        # Pivot the list on xs[lo]
        while True:
            while i < hi and xs[i] >= xs[lo]:
                i += 1
            j -= 1
            while j >= lo and xs[j] < xs[lo]:
                j -= 1
            if i > j:
                break
            xs[i], xs[j] = xs[j], xs[i]
        # Move the pivot to xs[j]
        if j > lo:
            xs[lo], xs[j] = xs[j], xs[lo]
        # Repeat on one side or the other based on the location of the pivot.
        if n <= j:
            hi = j
        else:
            lo = j + 1
    return xs[:n]


for k in xrange(100):
    xs = range(1000)
    random.shuffle(xs)
    xs = largest_n(xs, 10)
    assert sorted(xs) == range(990, 1000)
    print xs

Answer 8

下面怎么样，应该是O(len(xs))。

您只需将前 n 个元素与其余元素中最大的一个交换即可。

    def largest_n(xs, n):
        for i in range(n):
            for j in range(i+1,len(xs)):
                if xs[j] > xs [i]:
                    xs[i], xs[j] = xs[j], xs[i]
        return xs[:n]