Wie wäre es mit dem folgenden, es sollte O (len (xs)) sein.
Sie tauschen einfach die ersten n Elemente mit dem größten der verbleibenden Elemente aus.
%Vor%Ich habe ein Wörterbuch wie folgt:
%Vor%Es ist ein Wörterbuch mit Schlüsseln als Name einer Entität und der Wert ist die Zählung dieser Entität. Ich muss die Top 10 Elemente aus dem Wörterbuch zurückgeben.
Ich kann einen Heap schreiben, um es zu tun, aber ich bin mir nicht sicher, wie man einen Wert für das Key Mapping macht, da bestimmte Werte gleich sind.
Gibt es dafür eine andere Datenstruktur?
Mit heapq möchten Sie wahrscheinlich so etwas tun:
Beachten Sie, dass, da heapq nur einen Min-Heap implementiert, es besser ist, die Werte zu invertieren, so dass größere Werte kleiner werden.
Diese Lösung wird bei kleinen Heap-Größen langsamer sein, zum Beispiel:
%Vor% Bei 3000 Werten ist es nur etwas schneller als die sorted Version, die O(nlogn) anstelle von O(n + mlogn) ist. Wenn wir das dict auf 10000 erhöhen, wird die heapq version noch schneller:
Das Timing hängt wahrscheinlich auch von der Maschine ab, auf der Sie laufen. 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.
Um die ersten 10 Elemente zu erhalten, nehmen wir an, dass die Nummer an zweiter Stelle steht:
%Vor% Wenn Sie nach Wert sortieren möchten, dann ändern Sie einfach den Schlüssel in key=itemgetter(1,0) .
Wie bei einer Datenstruktur klingt ein Heap so, wie Sie es sich wünschen. Behalte sie einfach als Tupel und vergleiche den Zahlenbegriff.
Wenn das Wörterbuch constant bleibt, versuchen Sie nicht, heapq direkt oder über collections.Counter , können Sie versuchen, die Wörterbuchelemente mit zu sortieren der Wert als Schlüssel in umgekehrter Reihenfolge und dann die ersten 10 Elemente daraus erhalten. Sie müssen das Wörterbuch aus den Tupeln
neu erstellen %Vor% Wenn Sie heapq verwenden, um den Heap zu erstellen, benötigen Sie nlogn operations, wenn Sie einen Heap erstellen, indem Sie die Elemente einfügen, oder logn , wenn Sie eine Liste heapen, gefolgt von mlogn operations top m elements
Wenn Sie die Elemente sortieren, ist der Python-Sortieralgorithmus im schlimmsten Fall garantiert O(nlogn) (siehe TIM Sort ) und das Holen der ersten 10 Elemente wäre ein konstanter Vorgang
Bakurius Antwort ist korrekt (benutze heapq.nlargest).
Aber wenn Sie sich für den richtigen Algorithmus interessieren, verwendet quickselect ein ähnliches Prinzip wie Quicksort und wurde von derselben 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 damit, ein Pivot-Element auszuwählen und das Array so zu drehen, dass alle a [: j] kleiner oder gleich a [j] und alle a [j + 1:] größer als a [j sind ].
Als nächstes, wenn j == n, dann sind die größten Elemente a [: j]. Wenn j & gt; n, dann wird quickselect rekursiv nur für die Elemente aufgerufen, die vom Pivot übrig sind. Und wenn j & lt; Dann wird QuickSelect für die Elemente rechts vom Drehpunkt aufgerufen, um die größten n - j - 1 Elemente aus diesen zu extrahieren.
Da Quickselect rekursiv auf nur einer Seite des Arrays aufgerufen wird (im Gegensatz zu Quicksort, das bei beiden rekursiv aufgerufen wird), arbeitet es in linearer Zeit (wenn die Eingabe zufällig angeordnet ist und es keine wiederholten Schlüssel gibt). 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.
%Vor% Stellen Sie sich ein Diktat vor (Zuordnung von a-z mit a = 1 und z = 26):
Jetzt können Sie das tun:
%Vor% Sie haben auch angegeben, dass einige Werte des Mappings gleich sind. Jetzt aktualisieren wir d so, dass es die Buchstaben A-Z mit dem Mapping 1-26 hat:
Nun werden sowohl A-Z als auch a-z auf 1-26 :
Bei doppelten Zuordnungen ist das einzige sinnvolle Ergebnis das Zurückgeben einer Liste von Schlüsseln mit dem folgenden Wert:
%Vor%Und Sie könnten heapq hier verwenden:
%Vor%Sie haben nicht angegeben, was Sie mit den Duplikatergebnissen machen möchten, also nehme ich an, Sie möchten, dass diese Duplikate eliminiert werden, während die Ergebnisliste N lang bleiben soll.
Das macht das:
%Vor%Um die ersten 10 Elemente zu erhalten, nehmen wir an, dass die Nummer an zweiter Stelle steht:
%Vor%Wenn Sie nach Wert sortieren möchten, dann ändern Sie einfach den Schlüssel in %code% .
Wie bei einer Datenstruktur klingt ein Heap so, wie Sie es sich wünschen. Behalte sie einfach als Tupel und vergleiche den Zahlenbegriff.
Ich habe ein Wörterbuch wie folgt:
%Vor%Es ist ein Wörterbuch mit Schlüsseln als Name einer Entität und der Wert ist die Zählung dieser Entität. Ich muss die Top 10 Elemente aus dem Wörterbuch zurückgeben.
Ich kann einen Heap schreiben, um es zu tun, aber ich bin mir nicht sicher, wie man einen Wert für das Key Mapping macht, da bestimmte Werte gleich sind.
Gibt es dafür eine andere Datenstruktur?
Wenn das Wörterbuch constant bleibt, versuchen Sie nicht, heapq direkt oder über collections.Counter , können Sie versuchen, die Wörterbuchelemente mit zu sortieren der Wert als Schlüssel in umgekehrter Reihenfolge und dann die ersten 10 Elemente daraus erhalten. Sie müssen das Wörterbuch aus den Tupeln
neu erstellen %Vor%Wenn Sie heapq verwenden, um den Heap zu erstellen, benötigen Sie %code% operations, wenn Sie einen Heap erstellen, indem Sie die Elemente einfügen, oder %code% , wenn Sie eine Liste heapen, gefolgt von %code% operations top %code% elements
Wenn Sie die Elemente sortieren, ist der Python-Sortieralgorithmus im schlimmsten Fall garantiert %code% (siehe TIM Sort ) und das Holen der ersten 10 Elemente wäre ein konstanter Vorgang
Mit %code% möchten Sie wahrscheinlich so etwas tun:
%Vor%Beachten Sie, dass, da %code% nur einen Min-Heap implementiert, es besser ist, die Werte zu invertieren, so dass größere Werte kleiner werden.
Diese Lösung wird bei kleinen Heap-Größen langsamer sein, zum Beispiel:
%Vor%Bei 3000 Werten ist es nur etwas schneller als die %code% Version, die %code% anstelle von %code% ist. Wenn wir das dict auf 10000 erhöhen, wird die %code% version noch schneller:
%Vor%Das Timing hängt wahrscheinlich auch von der Maschine ab, auf der Sie laufen. 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 %code% Version zu verwenden, weil es einfacher ist.
Stellen Sie sich ein Diktat vor (Zuordnung von %code% mit a = 1 und z = 26):
%Vor%Jetzt können Sie das tun:
%Vor%Sie haben auch angegeben, dass einige Werte des Mappings gleich sind. Jetzt aktualisieren wir %code% so, dass es die Buchstaben %code% mit dem Mapping 1-26 hat:
%Vor%Nun werden sowohl %code% als auch %code% auf %code% :
abgebildet %Vor%Bei doppelten Zuordnungen ist das einzige sinnvolle Ergebnis das Zurückgeben einer Liste von Schlüsseln mit dem folgenden Wert:
%Vor%Und Sie könnten heapq hier verwenden:
%Vor%Sie haben nicht angegeben, was Sie mit den Duplikatergebnissen machen möchten, also nehme ich an, Sie möchten, dass diese Duplikate eliminiert werden, während die Ergebnisliste N lang bleiben soll.
Das macht das:
%Vor%Bakurius Antwort ist korrekt (benutze heapq.nlargest).
Aber wenn Sie sich für den richtigen Algorithmus interessieren, verwendet quickselect ein ähnliches Prinzip wie Quicksort und wurde von derselben 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 damit, ein Pivot-Element auszuwählen und das Array so zu drehen, dass alle a [: j] kleiner oder gleich a [j] und alle a [j + 1:] größer als a [j sind ].
Als nächstes, wenn j == n, dann sind die größten Elemente a [: j]. Wenn j & gt; n, dann wird quickselect rekursiv nur für die Elemente aufgerufen, die vom Pivot übrig sind. Und wenn j & lt; Dann wird QuickSelect für die Elemente rechts vom Drehpunkt aufgerufen, um die größten n - j - 1 Elemente aus diesen zu extrahieren.
Da Quickselect rekursiv auf nur einer Seite des Arrays aufgerufen wird (im Gegensatz zu Quicksort, das bei beiden rekursiv aufgerufen wird), arbeitet es in linearer Zeit (wenn die Eingabe zufällig angeordnet ist und es keine wiederholten Schlüssel gibt). 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.
%Vor%Wie wäre es mit dem folgenden, es sollte O (len (xs)) sein.
Sie tauschen einfach die ersten n Elemente mit dem größten der verbleibenden Elemente aus.
%Vor%Tags und Links python data-structures heap