Wie die größten Zahlen aus riesiger Menge von Zahlen zu bekommen?

Question

Ich mag die 100 größten Elemente aus einer Liste von mindestens 100.000.000 Zahlen bekommen.

ich die gesamte Liste sortieren konnte, und nehmen Sie nur die letzten 100 Elemente aus der sortierten Liste, aber das würde sowohl in Bezug auf Speicher und Zeit sehr teuer werden.

Gibt es einen bestehenden einfachen, pythonic Weg, dies zu tun?

Was ich will, ist anstelle einer reinen Art folgende Funktion. Eigentlich habe ich nicht Zeit verschwenden wollen, um die Elemente zu sortieren, ist mir egal.

Zum Beispiel ist dies die Funktion Ich möchte haben:

getSortedElements(100, lambda x,y:cmp(x,y))

Beachten Sie diese Anforderung ist nur für Leistungsperspektive.

Answer 1

Das heapq Modul in der Standardbibliothek bietet die nlargest () Funktion, dies zu tun:

top100 = heapq.nlargest(100, iterable [,key])

Es wird nicht die gesamte Liste sortieren, so werden Sie keine Zeit auf die Elemente verschwenden Sie nicht benötigen.

Answer 2

Auswahlalgorithmen hier helfen sollte.

Eine sehr einfache Lösung ist das 100. größte Element zu finden, die dann durch die Liste laufen Elemente Abgreifen, die größer als dieses Element sind. Das gibt Ihnen die 100 größten Elemente. Dies ist linear in der Länge der Liste; Dies ist am besten möglich.

Es gibt kompliziertere Algorithmen. Ein Haufen zum Beispiel für dieses Problem ist sehr zugänglich. Der Heap-basierten Algorithmus ist n log k wo n ist die Länge der Liste und k ist die Anzahl der größten Elemente, die Sie auswählen möchten.

Es gibt eine Diskussion dieses Problem auf der Wikipedia-Seite für die Auswahl-Algorithmen.

Edit: Ein anderes Plakat hat darauf hingewiesen, dass Python eine eingebaute Lösung für dieses Problem hat. Offensichtlich das ist viel einfacher, als Sie Ihre eigenen Rollen, aber ich werde dies im Falle post up halten möchten Sie darüber erfahren, wie solche Algorithmen arbeiten.

Answer 3

Sie können einen Heap-Datenstruktur verwenden. Ein Haufen wird nicht unbedingt bestellt werden, aber es ist eine ziemlich schnelle Art und Weise halbgeordnete Daten zu halten, und es hat den Vorteil, das kleinste Element immer das erste Element in dem Haufen zu sein.

Ein Haufen hat zwei grundlegende Operationen, die Ihnen helfen. Hinzufügen und Ersetzen

Im Grunde, was Sie tun, ist Elemente hinzufügen, bis Sie auf eine Stückzahl von 100 (Ihre Top-N-Nummer pro Frage) erhalten. Dann danach, ersetzen Sie das erste Element mit jedem neuen Artikel, solange das neue Element größer ist als der erste Punkt.

Wenn Sie das erste Element ersetzen mit etwas größer, der interne Code auf der Halde wird die Halde Inhalt anpassen, so dass, wenn das neue Element nicht der kleinste ist, wird es sprudeln in den Haufen, und das kleinste Element wird „Blase „down auf das erste Element, bereit, auf dem Weg ersetzt werden.

Answer 4

Der beste Weg, dies zu tun ist, eine Haufen sortierte Prioritätswarteschlange zu erhalten, die Sie weg von Pop, sobald es hat 100 Einträge drin.

Während Sie sich nicht, wenn die Ergebnisse es sortiert werden, ist intuitiv klar, werden Sie diese kostenlos. Um Ihnen die Top-100 müssen wissen, müssen Sie Ihre aktuelle Liste der Top-Zahlen um über einige effiziente Datenstruktur bestellen. Diese Struktur wird wissen, das Minimum, das Maximum und die relative Position jedes Elements in eine natürliche Art und Weise, dass Sie seine Position neben seinen Nachbarn behaupten kann.

Wie in Python erwähnt würden Sie heapq verwenden. In Java Priorityqueue: http://java.sun.com/javase/ 6 / docs / api / java / util / PriorityQueue.html

Answer 5

Hier ist eine Lösung, die ich verwendet habe, die unabhängig von Bibliotheken ist und dass wird in einer beliebigen Programmiersprache arbeiten, die Arrays hat:

Initialisierung:

Make an array of 100 elements and initialise all elements
with a low value (less than any value in your input list).

Initialise an integer variable to 0 (or any value in
[0;99]), say index_minvalue, that will point to the
current lowest value in the array.

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

Für jeden Wert, sagt aktueller_wert, in der Eingabeliste:

if current_value > minvalue

  Replace value in array pointed to by index_minvalue
  with current_value

  Find new lowest value in the array and set index_minvalue to
  its array index. (linear search for this will be OK as the array
  is quickly filled up with large values)

  Set minvalue to current_value

else
  <don't do anything!>

minvalue wird schnell einen hohen Wert erhalten und damit die meisten Werte in der Eingabeliste müssen nur minvalue verglichen werden (Das Ergebnis des Vergleichs wird meist falsch sein).

Answer 6

Für die Algorithmen weenies im Publikum: Sie können dies tun, mit einer einfachen Variante Tony Hoare Algorithmus Suchen :

find(topn, a, i, j)
   pick a random element x from a[i..j]
   partition the subarray a[i..j] (just as in Quicksort) 
     into subarrays of elements <x, ==x, >x
   let k be the position of element x
   if k == 0 you're finished
   if k > topn, call find(topn, a, i, k)
   if k < topn, call find(topn-k, k, j)

Dieser Algorithmus stellt die größte topn Elemente in die ersten topn Elemente der Matrix a, ohne Sortieren sie. wenn Sie natürlich wollen sie sortiert, oder für schiere Einfachheit, ein Haufen ist besser, und die Bibliotheksfunktion Aufruf ist noch besser. Aber es ist ein cooler Algorithmus.