encontrar las mejores k claves más grandes en un diccionario de python

Digamos que tengo un diccionario:

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

Así que digamos que quiero escribir una función

 def return_top_k(dictionary, k): return list_of_keys_sorted 

¿Cuál es la forma más eficiente (en términos de gran O) para obtener las claves que tienen los valores k superiores (mantener el orden, es decir, la clave del valor más alto está presente al principio … y así sucesivamente)?

O(n log k) :

 import heapq k_keys_sorted = heapq.nlargest(k, dictionary) 

Puede usar el parámetro de palabra key clave para especificar qué se debe usar como clave de clasificación, por ejemplo:

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

En el peor de los casos, debería ser O(NlogN) (aunque el heapq propuesto por otros es probablemente mejor) …

También podría tener sentido usar un Counter lugar de un diccionario regular. En ese caso, el método most_common hará (aproximadamente) lo que desea ( dictionary.most_common(10) ), pero solo si tiene sentido usar un Counter en su API.

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

Para top-3 paso a paso:

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

O usando el módulo heapq

 >>> import heapq >>> heapq.nlargest(3, dct.items(), key=itemgetter(1)) [('e', 5), ('d', 4), ('c', 3)] >>> map(itemgetter(0), _) ['e', 'd', 'c'] 

En codigo

 dct = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5} k = 3 print sorted(dct.keys(), reverse=True)[:k] 

Si también necesitas valores:

 print sorted(dct.items(), reverse=True)[:k] 

O si quieres usar OrderedDict :

 from collections import OrderedDict d = OrderedDict(sorted(dct.items(), reverse=True)) print d.keys()[:k]