有沒有更清晰的方法來查找字典中最高的5個值？

現在，我遍歷整個詞典五次，並在每次迭代後保留最高值並刪除條目。但這似乎是一個非常討厭的方式來做我想做的事情。從本質上講，我想獲得字典的前5大價值，並返回密鑰，有沒有更好的方法來做到這一點，而不是迭代五次？有沒有更清晰的方法來查找字典中最高的5個值？

來源

2014-02-25 Stupid.Fat.Cat

是，通過使用heapq.nlargest() function：

from heapq import nlargest 

five_largest = nlargest(5, yourdict, key=yourdict.get)

這比任一重複循環或排序更有效。

heapq算法會對鍵進行一個循環，只保留其中的5個保持不變的堆，然後當循環完成時返回這5個元素的排序順序。循環是O（N），保持循環不變是O（logK）（其中K是堆大小），排序O（KlogK）。總複雜度：O（NlogK）

排序將需要排序完整字典，它是O（NlogN）。這意味着N越大，heapq.nlargest()贏得的成績就越多。

來源

2014-02-25 20:13:42

+1偉大的答案！我有一個問題 - 在上面的代碼中聲明堆的大小是5將是正確的嗎？如果是的話，則'O（N log K）'變爲'O（N log 5）'，即'O（N）'。或者相反，如果堆的大小是「N」，那麼我們又回到了'O（N log N）'。哪一種說法是正確的？ –

這裏K固定爲5，是的，但是對於所有Top K比較，您需要將K保留一個變量。是的，與N相比，注意K也很重要，因爲當K接近N時，「最大」方法變得不那麼吸引人。實際上，'nlargest（）'實現[在N> = K]時切換到使用'sorted（）'（http://hg.python.org/cpython/file/0926adcc335c/Lib/heapq.py#l452）。 –

爲了完整起見，在分析它之前和之後詢問了一個類似的問題[總結]（http://stackoverflow.com/a/350685/201359），使用帶有「k」長度列表的「bisect」的速度比使用'heapq'。 –

嘗試使用此方法獲得前5個值：

sorted(mydict.values())[-5:]

並獲得相應的鍵：

sorted(mydict, key=mydict.get)[-5:]

來源

2014-02-25 20:13:50

但他想要的是鑰匙，而不是價值。 –

@TimPietzcker我誤解了這個問題，現在已經修復 –

有沒有更清晰的方法來查找字典中最高的5個值？

回答

相關問題