Sortierung von 1 Billion ganzer Zahlen

Question

Finden Sie bei einer Menge von 1 Billion ganzen Zahlen auf der Festplatte die kleinste 1 Million davon. Sie können höchstens 1 Million ganze Zahlen gleichzeitig im Speicher unterbringen.

Ein Ansatz ist, die ersten 1 Million von 1 Billion zu nehmen und die 1 Million Ganzzahlen zu sortieren und auf der Festplatte zu speichern. Auf diese Weise setzen Sie die Sortierung für jede Gruppe von 1 Million ganzen Zahlen fort und speichern sie auf der Festplatte. Nun sind die Gruppen von 1 Million ganzen Zahlen bis zu 1 Billion sortiert. Vergleichen Sie nun das erste Element aller sortierten Gruppen, das Minimum von ihnen ist das Minimum der 1 Billion. Speichern Sie es als erstes Element im Speicher. Als nächstes wird das zweite Element aus der Gruppe genommen, aus der das kleinste Element stammt, und dann mit dem ersten Element aller anderen Gruppen verglichen. Auf diese Weise wiederholen Sie den Vorgang, bis die erste 1 Million sortiert und im Speicher abgelegt ist.

Gibt es einen optimaleren Ansatz, den ich übersehe?

Answer 1

Sie können dies effizient in O(n log m) tun, indem Sie eine Haufen . ( n = alle Zahlen, m = die Größe der Zahlenmenge, die man finden will ).

Gehen Sie die Billionen von Zahlen der Reihe nach durch. Führen Sie für jede neue Zahl einen der folgenden Schritte aus.

1. Wenn der Heap < 1 Million Knoten hat, wird die neue Zahl in den Heap eingefügt.
2. Wenn der Heap genau 1 Million Knoten hat und der oberste Knoten > als die neue Zahl ist, dann wird der oberste Knoten aus dem Heap entfernt und ein Knoten mit der neuen Zahl eingefügt.
3. Wenn weder 1 noch 2 zutrifft, wird die Zahl gewürfelt.

Nachdem Sie alle Billionen von Einträgen durchgegangen sind, enthält der resultierende Haufen die 1 Million kleinsten Zahlen.

Das Einfügen und Löschen auf dem Heap ist O(log m). Der einzelne Durchlauf durch den Heap ist n. Der Algorithmus ist also n*log (m)

Answer 2

Wie groß sind die ganzen Zahlen? Wenn es sich nur um 32-Bit-Werte handelt, würde ich einfach ein Array mit 4 Milliarden 64-Bit-Zählern auf der Festplatte erstellen und bei der Begegnung mit x in den Eingang, erhöhen Sie den Zähler an der Position x . Im Allgemeinen ist dieser Ansatz extrem platzaufwendig, aber im Verhältnis dazu sind die Kosten gering, wenn der Bereich der möglichen Elementwerte viel kleiner ist als die Anzahl der zu sortierenden Elemente, und vor allem ist es O(n) in der Zeit.

Answer 3

Eine Lösung in Scala, aber nicht für 1 Billion Elemente. Mit einem Zeiger in eine Datei anstelle der Liste, oder mehrere kleine Listen, könnte es auf diese Weise getan werden:

def top (n: Int, li: List [Int]) : List[Int] = {

  def updateSofar (sofar: List [Int], el: Int) : List [Int] = {
    // println (el + " - " + sofar)
    if (el < sofar.head) 
      (el :: sofar.tail).sortWith (_ > _) 
    else sofar
  }

  /* better readable:
    val sofar = li.take (n).sortWith (_ > _)
    val rest = li.drop (n)
    (sofar /: rest) (updateSofar (_, _)) */    
  (li.take (n). sortWith (_ > _) /: li.drop (n)) (updateSofar (_, _)) 
}

Nehmen Sie die erste Million Elemente. Sortiere sie. Vergleichen Sie nun jedes folgende Element mit dem größten der Million. Wenn es kleiner ist, sortiere es in die Liste ein und lasse das alte größte Element weg.

Answer 4

Mit einer Variante von QuickSort können Sie dies sogar noch effizienter in O(n)-Zeit erledigen, wobei 'n' die Größe der Liste auf der Festplatte ist. (in diesem Fall eine Billion)

Alles, was Sie tun müssen, ist:

1. Finde die einmillionste kleinste Zahl, indem du das Laufwerk mehrmals in immer kleinere Abschnitte unterteilst. Dies benötigt O(n) Zeit.

2. Nehmen Sie sie und die anderen 999.999 ganzen Zahlen, die die Partitionierung aussortiert hat, und legen Sie sie im RAM ab. Sie sind fertig.

Die kleinste Million ganzer Zahlen wird nicht sortiert, aber sie wird die kleinste Million sein.

Wenn man dann die kleinste Million sortieren will, braucht man O(m log m) Zeit, wobei "m" in diesem Fall eine Million ist.

Keine Kosten für den Raum, O(n)-Zeit, funktioniert mit nicht-ganzzahligen Werten. Viel Spaß! :)