la recherche de premiers k plus grandes touches dans un dictionnaire python

Permet de dire que j'ai un dictionnaire:

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

Donc disons que je veux écrire une fonction

def return_top_k(dictionary, k):

    return list_of_keys_sorted

Quel est le moyen le plus efficace (en termes de big O) pour obtenir les clés qui ont le haut les valeurs de k (maintien de l'ordre que j'ai.e la valeur la plus élevée est présente dans le début.. et ainsi de suite.)

  • Lorsque l'on parle de dictionnaires à l'aide de k pour un nombre est source de confusion car il se trouve souvent pour la "clef". Utilisation n à la place.
InformationsquelleAutor Mohit | 2012-09-04
  1. 17

    O(n log k):

    import heapq

k_keys_sorted = heapq.nlargest(k, dictionary)

    Vous pouvez utiliser key mot-clé paramètre pour spécifier ce qui doit être utilisé comme une clé de tri par exemple:

    k_keys_sorted_by_values = heapq.nlargest(k, dictionary, key=dictionary.get)
    • Je pense que l'OP est en train de demander quelque chose comme heapq.nlargest(k, dictionary, key=dictionary.__getitem__): les clés de dictionnaire commandés par leurs valeurs.
    • Remarque, que c'est une suite de clés de tri
    • suggère le contraire
    • Hmm, c'est vrai. Le mot "valeur" est source de confusion; soit on peut être de droite. 🙂
    • safaribooksonline.com/library/view/python-cookbook-3rd/...
    InformationsquelleAutor jfs
  2. 6
    return sorted(dictionary, key=dictionary.get, reverse=True)[:10]

    Devrait être au pire O(NlogN) (bien que heapq proposées par d'autres est probablement mieux) ...

    Il pourrait également préférable d'utiliser un Counter au lieu de régulièrement un dictionnaire. Dans ce cas, le most_common méthode permettra de le faire (à peu près) ce que vous voulez (dictionary.most_common(10)), mais seulement si il est logique d'utiliser un Counter dans votre API.

    • C'est parfait. Je vais ajouter que si le dictionnaire arrive à un dictionnaire de compte, collections.Counter serait la bonne structure de données. Alors la solution serait [k for k, v in counts.most_common(10)].
    InformationsquelleAutor mgilson
  3. 3
    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'])
    InformationsquelleAutor Bala
  4. 1

    Pour le top-3, étape par étape: 

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

    Ou à l'aide de heapq module

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

    Dans le code

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

    Si vous aussi vous avez besoin de valeurs:

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

    Ou si vous souhaitez utiliser OrderedDict:

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