字典中的蟒蛇

找到前k大按鍵可以說我有一本字典：字典中的蟒蛇

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

所以，可以說，我想編寫一個函數

def return_top_k(dictionary, k): 

    return list_of_keys_sorted

什麼是最有效的方式（以大O的條款）來獲得具有最高k值的鍵（保持順序，即最高值鍵存在於開頭等等）。

來源

2012-09-04 Fraz

說起字典使用計數「k」令人困惑，因爲它通常代表「關鍵」。改用'n'。 –

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)

來源

2012-09-04 15:27:09 jfs

我認爲OP實際上是要求'heapq.nlargest（k，dictionary，key = dictionary .__ getitem __）'：按照它們的值排序的字典鍵。 – Dougal

請注意，這是排序鍵 –

@Dougal：'list_of_keys_sorted'的結果否則表示 – jfs

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

應該是在最壞的情況O(NlogN)（雖然被別人提出heapq可能是更好的）...

它威力也是有道理使用Counter，而不是一個普通的字典。在這種情況下，most_common方法將會（大約）做你想要的（dictionary.most_common(10)），但前提是在API中使用Counter是有意義的。

來源

2012-09-04 15:24:39 mgilson

這是完美的。我會補充說，如果字典發生在計數字典中，'collections.Counter'就是正確的數據結構。那麼解決方案就是'[k for k，v in counts.most_common（10）]'。 –

對於頂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 
>>> heapq.nlargest(3, dct.items(), key=itemgetter(1)) 
[('e', 5), ('d', 4), ('c', 3)] 
>>> map(itemgetter(0), _) 
['e', 'd', 'c']

來源

2012-09-04 15:28:33

在代碼

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]

來源

2015-04-14 01:02:59

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'])

來源

2016-05-27 08:33:47 Bala

字典中的蟒蛇

回答

相關問題