n größte Elemente in einer Sequenz (Duplikate müssen beibehalten werden)

8

Ich muss die n größten Elemente in einer Liste von Tupeln finden. Hier ist ein Beispiel für die Top 3 Elemente.

%Vor%

Ich habe versucht, heapq.nlargest zu verwenden. Es gibt jedoch nur die ersten drei größten Elemente zurück und gibt keine Duplikate zurück. Zum Beispiel

%Vor%

Ich kann nur an einen Brute-Force-Ansatz denken. Das ist was ich habe und es funktioniert.

%Vor%

Irgendwelche anderen Ideen, wie ich das umsetzen kann? Danke!

EDIT: timeit Ergebnisse für eine Liste von 1 Million Elementen zeigen, dass mhyfritz's Lösung läuft in 1/3 der Zeit der Brute-Force. Ich wollte die Frage nicht zu lange stellen. Also fügte weitere Details in meine Antwort .

    
Praveen Gollakota 12.07.2011, 19:06
quelle

6 Antworten

7

Ich nehme es aus Ihrem Code-Snippet, dass lot in w.r.t gruppiert ist. Kategorie-1 . Folgendes sollte dann funktionieren:

%Vor%     
mhyfritz 12.07.2011, 19:48
quelle
2

Wenn Sie die Eingabedaten bereits so sortiert haben, ist es sehr wahrscheinlich, dass Ihre Lösung ein wenig besser ist als die Heap-basierte.

Ihre Algorithmuskomplexität ist O (n), während die heapq-basierte Eins konzeptionell O (n * log (3)) ist und wahrscheinlich mehr Durchläufe über die Daten benötigt, um sie richtig anzuordnen.

    
Mihai Toader 12.07.2011 19:23
quelle
1

Einige zusätzliche Details ... Ich habe beide mhyfritz's ausgezeichnete Lösung , die itertools und und meinen Code (brute-force) verwendet.

Hier sind die timeit Ergebnisse für n = 10 und für eine Liste mit 1 Million Elementen.

%Vor%

Falls jemand neugierig ist, hier ist eine Spur davon, wie sein Code funktioniert.

%Vor%     
Praveen Gollakota 12.07.2011 21:27
quelle
0

Wie ist es damit? Es gibt nicht genau das gewünschte Ergebnis zurück, da es in y umgekehrt sortiert.

%Vor%     
Fred Foo 12.07.2011 19:32
quelle
0
___ qstnhdr ___ n größte Elemente in einer Sequenz (Duplikate müssen beibehalten werden) ___ answer6669869 ___

Wenn Sie die Eingabedaten bereits so sortiert haben, ist es sehr wahrscheinlich, dass Ihre Lösung ein wenig besser ist als die Heap-basierte.

Ihre Algorithmuskomplexität ist O (n), während die heapq-basierte Eins konzeptionell O (n * log (3)) ist und wahrscheinlich mehr Durchläufe über die Daten benötigt, um sie richtig anzuordnen.

    
___ answer6671383 ___

Einige zusätzliche Details ... Ich habe beide mhyfritz's ausgezeichnete Lösung , die onlyTopThreeKeys und und meinen Code (brute-force) verwendet.

Hier sind die itertools.groupby Ergebnisse für %code% und für eine Liste mit 1 Million Elementen.

%Vor%

Falls jemand neugierig ist, hier ist eine Spur davon, wie sein Code funktioniert.

%Vor%     
___ qstntxt ___

Ich muss die n größten Elemente in einer Liste von Tupeln finden. Hier ist ein Beispiel für die Top 3 Elemente.

%Vor%

Ich habe versucht, %code% zu verwenden. Es gibt jedoch nur die ersten drei größten Elemente zurück und gibt keine Duplikate zurück. Zum Beispiel

%Vor%

Ich kann nur an einen Brute-Force-Ansatz denken. Das ist was ich habe und es funktioniert.

%Vor%

Irgendwelche anderen Ideen, wie ich das umsetzen kann? Danke!

EDIT: %code% Ergebnisse für eine Liste von 1 Million Elementen zeigen, dass mhyfritz's Lösung läuft in 1/3 der Zeit der Brute-Force. Ich wollte die Frage nicht zu lange stellen. Also fügte weitere Details in meine Antwort .

    
___ tag123python ___ Python ist eine dynamische und stark typisierte Programmiersprache, die die Usability betont. Zwei ähnliche, aber größtenteils inkompatible Versionen von Python sind weit verbreitet (2 und 3). Wenn Sie eine versionsspezifische Python-Frage haben, sollten Sie die Tags [python-2.7] oder [python-3.x] zusätzlich zum Tag [python] verwenden. Wenn Sie eine Python-Variante wie jython, pypy, iron-python usw. verwenden, kennzeichnen Sie diese bitte entsprechend. ___ answer6670141 ___

Ich nehme es aus Ihrem Code-Snippet, dass %code% in w.r.t gruppiert ist. Kategorie-1 . Folgendes sollte dann funktionieren:

%Vor%     
___ answer6669977 ___

Wie ist es damit? Es gibt nicht genau das gewünschte Ergebnis zurück, da es in %code% umgekehrt sortiert.

%Vor%     
___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ answer6669860 ___

Dies ist die Idee, ein dict mit dem Wert, nach dem sortiert werden soll, als Schlüssel und einer Liste der Tupel, die diesen Wert als Werte haben, zu erstellen.

Dann sortieren Sie die Elemente des Diktats mit den Schlüsseln, holen Sie die Elemente von oben, extrahieren Sie ihre Werte und verbinden Sie sie.

Schneller, hässlicher Code:

%Vor%

Nur um Ihnen ein paar Ideen zu geben, hoffe es hilft. Wenn Sie etwas Klärung benötigen, fragen Sie in den Kommentaren

    
___ tag123heap ___ Ein Heap (Datenstruktur) ist ein Baum, der in Bezug auf die Tiefe geordnet ist. Heap kann sich auch auf den Prozessspeicher beziehen, der für die dynamische Zuweisung reserviert ist. ___ tag123sequenz ___ Eine Sequenz ist eine geordnete Liste von Objekten (oder Ereignissen). Wie eine Menge enthält sie Elemente (auch Elemente oder Terme genannt) und die Anzahl der Terme (möglicherweise unendlich) wird als Länge der Sequenz bezeichnet. Im Gegensatz zu einer Menge ist die Reihenfolge wichtig, und genau dieselben Elemente können mehrmals an verschiedenen Positionen in der Sequenz erscheinen. In einer relationalen Datenbank ist eine Sequenz ein Objekt, das zum Generieren eindeutiger Zahlen für einen Primärschlüssel verwendet wird. ___ tag123sorting ___ Das Sortieren ist der Vorgang, bei dem eine Reihenfolge auf eine Objektgruppe angewendet wird. ___ answer66000071 ___
%Vor%

Ergebnis:

%Vor%

flache Liste : Ich habe die obige Methode durchgeführt, weil Sie dadurch mehr Informationen erhalten. Um nur eine flache Liste zu erhalten, verwenden Sie closures, um Ergebnisse mit %code% :

auszugeben %Vor%

Ergebnis:

%Vor%

Sie können %code% auch verwenden, wenn Ihre Eingabe garantiert wie in Ihrer Beispieleingabe sortiert ist. Dies führt jedoch dazu, dass Ihr Code bei Änderungen der Sortierung bricht.

    
___
ninjagecko 12.07.2011 19:41
quelle
0

Dies ist die Idee, ein dict mit dem Wert, nach dem sortiert werden soll, als Schlüssel und einer Liste der Tupel, die diesen Wert als Werte haben, zu erstellen.

Dann sortieren Sie die Elemente des Diktats mit den Schlüsseln, holen Sie die Elemente von oben, extrahieren Sie ihre Werte und verbinden Sie sie.

Schneller, hässlicher Code:

%Vor%

Nur um Ihnen ein paar Ideen zu geben, hoffe es hilft. Wenn Sie etwas Klärung benötigen, fragen Sie in den Kommentaren

    
Facundo Casco 12.07.2011 19:23
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Style einen Bereich von Zellen mit phpexcel