如何維護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)。如果我們增加了字典的大小，以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

如果字典仍然不變，然後，而不是試圖直接或通過collections.Counter創建heapq，你可以嘗試使用該值作爲以相反的順序關鍵字典項目進行排序，然後從它那裏得到的前10種元素。您需要重新從元組

>>> 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操作，如果你是，如果你heapify列表插入元素或logn建立一個堆，接着mlogn操作以取出頂部m元件

如果要排序的項目，Python的排序算法保證在最壞的情況下O(nlogn)（參照TIM Sort）和取前10個元素將是一個恆定的操作

Answer 3

爲了得到前10個元素，假設數字是排在第二位：

from operator import itemgetter 

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

如果你想按值進行排序，然後鍵入只是將其更改爲 key=itemgetter(1,0)

。

對於數據結構，堆聽起來像你想要什麼。只要將它們保存爲元組，並比較數字項。

Answer 4

想象一下，一個字典，像這樣（有= 1和z = 26的a-z映射）：

>>> 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所以它具有與映射1-26字母A-Z：

>>> 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 5

Bakuriu的答案是正確的（使用heapq.nlargest）。

但是，如果你有興趣在正確的算法使用，quickselect採用了類似的原理來快速排序，並且由同一人發明：C.A.R.霍爾。

然而，它並不完全對數組進行排序：完成後，如果您要求排在前n個元素，則它們位於數組的前n個位置，但不一定按排序順序排列。

與快速排序一樣，它首先選擇一個元素並旋轉數組，使得所有a [：j]小於或等於[j]，並且所有[j + 1：]都大於a [ J]。

接下來，如果j == n，那麼最大的元素是[：j]。如果j> n，則快速選擇僅在樞軸左側的元素上遞歸調用。如果j < n那麼quickselect被調用到樞軸右側的元素上，以從這些元素中提取n-j-1個最大的元素。

由於quickselect被遞歸調用僅在陣列的一側（與快速排序，其被遞歸調用兩個），它工作在線性時間（如果輸入被隨機排序，並且沒有重複鍵）。這也有助於將遞歸調用轉換爲while循環。

這是一些代碼。爲了幫助理解它，outer 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 6

如何以下，應該是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]