Wie man Wörterbuch in einem Heap in Python pflegen?

Question

Ich habe ein Wörterbuch wie folgt:

{'abc':100,'xyz':200,'def':250 .............} 

Es ist ein Wörterbuch mit Schlüssel als Name eines Unternehmens und der Wert Zählung dieser Einheit. Ich muss die Top 10 Elemente aus dem Wörterbuch zurückgeben.

Ich kann einen Heap schreiben, um es zu tun, aber ich bin nicht sicher, wie man Wert zum Schlüsselabbilden tut, da bestimmte Werte gleich sind.

Gibt es eine andere Datenstruktur, um dies zu tun?

Answer 1

Mit heapq Sie wollen wahrscheinlich etwas tun:

heap = [(-value, key) for key,value in the_dict.items()] 
largest = heapq.nsmallest(10, heap) 
largest = [(key, -value) for value, key in largest] 

Beachten Sie, dass seit heapq implementiert nur eine min Haufen es besser ist, die Werte zu invertieren, so dass größere Werte kleiner werden.

Diese Lösung wird für kleine Größen des Haufens langsamer sein, zum Beispiel:

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

mit 3000 Werten, es ist nur etwas schneller als die sorted Version, die O(nlogn) statt O(n + mlogn) ist. Wenn wir die Größe des dict bis 10000 die heapq Version erhöhen wird noch schneller:

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

Die Zeiten wahrscheinlich hängt auch von der Maschine, auf der Sie ausgeführt werden. Sie sollten sich wahrscheinlich überlegen, welche Lösung in Ihrem Fall am besten funktioniert. Wenn die Effizienz nicht kritisch ist, würde ich vorschlagen, die sorted Version zu verwenden, weil es einfacher ist.

Answer 2

Wenn das Wörterbuch konstant bleibt, dann anstatt zu versuchen, ein heapq direkt oder über collections.Counter zu erstellen, können Sie versuchen, die Wörterbuch Elemente sortieren den Wert als Schlüssel in umgekehrter Reihenfolge und anschließend die ersten 10 Elemente von ihm erhalten . Sie müssen das Wörterbuch aus den Tupeln

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

neu erstellen Wenn Sie heapq verwenden, den Haufen zu erstellen, geben Sie nlogn Operationen benötigen, wenn Sie einen Haufen bauen, indem die Elemente eingefügt oder logn wenn Sie eine Liste heapify, gefolgt von mlogn Operationen, die die Top-m Elemente

zu holen Wenn Sie die Einzelteile sortieren, wird Python Sortieralgorithmus garantiert O(nlogn) im schlimmsten Fall sein (siehe TIM Sort) und die ersten 10 Elemente zu holen wäre eine konstante Operationen

Answer 3

Für die Top 10 Elemente bekommen, unter der Annahme, dass die Anzahl an zweiter Stelle ist:

from operator import itemgetter 

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

wenn Sie mit dem Wert sortieren wollen, dann geben Sie sie nur zu key=itemgetter(1,0) ändern.

Wie für eine Datenstruktur klingt ein Heap wie, was Sie wollen. Behalte sie einfach als Tupel und vergleiche den Zahlenbegriff.

Answer 4

wie ein dict Stellen Sie sich vor, so (Abbildung von a-z mit a = 1 und z = 26):

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

Jetzt können Sie dies tun:

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

Sie erklärte auch, dass einige Werte von Das Mapping wird gleich sein. Nun ist d lassen aktualisieren, damit es die Buchstaben A-Z mit dem Mapping hat 1-26:

>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(26)),range(1,27))}) 

jetzt beide A-Z und a-z Karte zu 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} 

So mit doppelten Zuordnungen, die einzig sinnvolle Ergebnis ist eine Liste der Schlüssel zurückzugeben, die den Wert haben:

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

Und Sie heapq hier nutzen könnten:

[[k[x] for x,z in enumerate(v) if z==i ] for i in heapq.nlargest(10,v)] 

Du hast nicht sagen, was Sie mit den doppelten Ergebnissen tun möchte, so nehme ich an Sie, diese Duplikate eliminiert wollen würde, während die Ergebnisliste N lange bleiben.

Dies tut das:

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 Antwort korrekt ist (Verwendung heapq.nlargest) ist.

Wenn Sie jedoch an dem richtigen Algorithmus interessiert sind, verwendet quickselect ein ähnliches Prinzip wie Quicksort und wurde von der gleichen Person erfunden: C.A.R. Hoare.

Es unterscheidet sich jedoch dadurch, dass das Array nicht vollständig sortiert wird: Wenn Sie nach dem Beenden nach den obersten n Elementen gefragt haben, befinden sie sich an den ersten n Positionen im Array, aber nicht unbedingt in sortierter Reihenfolge.

Wie Quicksort beginnt es mit der Auswahl eines Pivot-Elements und dem Schwenken des Arrays, sodass alle a [: j] kleiner oder gleich a [j] und alle a [j + 1:] größer als a sind. j].

Als nächstes, wenn j == n, dann sind die größten Elemente a [: j]. Wenn j> n, dann wird Quickselect rekursiv nur für die Elemente aufgerufen, die vom Pivot übrig sind. Und wenn j < n dann wird QuickSelect für die Elemente rechts vom Pivot aufgerufen, um daraus die n - j - 1 größten Elemente zu extrahieren.

Da Quickselect rekursiv auf nur einer Seite des Arrays aufgerufen wird (im Gegensatz zu Quicksort, das rekursiv auf beiden Seiten aufgerufen wird), funktioniert es in linearer Zeit (wenn die Eingabe zufällig angeordnet ist und keine wiederholten Schlüssel vorhanden sind). Dies hilft auch, den rekursiven Aufruf in eine while-Schleife umzuwandeln.

Hier ist ein Code. Um es zu verstehen, sind die Invarianten in der äußeren while-Schleife, dass die Elemente xs [: lo] garantiert in der Liste von n large sind, und dass die Elemente xs [hi:] garantiert nicht in der n größten sind.

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

Wie wäre es mit dem folgenden, sollte es O (len (xs)) sein.

Sie tauschen einfach die ersten n Elemente mit dem größten der verbleibenden Elemente aus.

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]