Mindestraum erforderlich, um einen Strom von ganzen Zahlen zu sortieren

Question

Diese Frage hat viel Aufmerksamkeit auf SO erregt:
Sortieren von 1 Million 8-stelligen Zahlen in 1 MB RAM

Das Problem besteht darin, einen Stream von 1 Million 8-stelligen Zahlen (Ganzzahlen im Bereich $ [0, : 99 mathord {,} 999 mathord {,} 999] $) mit nur 1 MB Speicher ($ 2^ {20} $ bytes = $ 2^{23} $ bit) und kein externer Speicher. Das Programm muss Werte aus einem Eingabestream lesen und das sortierte Ergebnis in einen Ausgabestrom schreiben.

Offensichtlich kann die gesamte Eingabe nicht in den Speicher passen, aber das Ergebnis kann eindeutig in unter 1 MB dargestellt werden eine enge Passform).

Was ist also die minimale Menge an Platz, die erforderlich ist, um N -Ganzzahlen auf diese Streaming -Weise mit Duplikaten zu sortieren, und gibt es einen Algorithmus, um die angegebene Aufgabe zu erfüllen?

Answer 1

OK, es ist weit über meine Schlafenszeit hinaus, aber das lässt mich nicht gehen, also hier ist ein zweiter Versuch (meine erste gelöscht) ...

Bevor ich in die Einzelheiten der Sortierung der Zahlen gehe, werde ich sie zunächst nicht als Abfolge von Ganzzahlen $ i_1, i_2, dots, i_n $ darstellen, sondern als Abfolge ihrer Unterschiede, dh $ delta_k = i_k - i_ {k-1} $ wobei nach Konvention $ i_0 = 0 $.

Um diese Werte darzustellen, werde ich sie dann zuerst in Eimer gruppieren, abhängig von der Anzahl der für ihre Darstellung benötigten Bit 0. Da die Zahlen zwischen 0 und 99'999'999 liegen, brauche ich 27 Eimer.

Für jeden Eimer werde ich ein Präfix aus dem Satz auswählen 1, 01, 001, 0001, usw. bis zu 000000000000000000000000001. Offensichtlich werde ich das kürzeste Präfix für den größten Eimer, das zweitschiffste für das zweitgrößte usw. auswählen ...

Die Abfolge von $ delta_k $ kann dann als Präfixe und Wertepaare geschrieben werden, wobei für die Werte $> 1 $ das führende Bit weggelassen werden kann.

Wie viele Bits muss ich für einen zufälligen Satz von Zahlen die Abfolge von $ delta_k $ darstellen?

Für eine konstante Sequenz, z. 10, daher 2 Millionen Bit. Für jede andere Konstante wäre es 2 Millionen Bit plus die Anzahl der Bits dieses Wertes für die anfänglichen $ delta_1 $.

Die gleiche Berechnung gilt für eine zunehmende Sequenz, z. 11.

Was ist nun der schlimmste Fall, dh welche Sequenz von $ delta_k $ wird die längste Sequenz von Bits geben? Das Schlimmste, was wir tun können, ist sicherzustellen, dass jeder Eimer einen Eintrag weniger als der vorherige hat, wobei die kleinsten $ delta_k $ möglich wählt, wodurch die längsten Sequenzen das größte Präfix zugewiesen werden. Der Einfachheit halber werde ich davon ausgehen, dass $ K $ Eimer die gleiche Menge an Einträgen haben, wobei das kürzeste Präfix der kürzesten Sequenz zugeordnet ist. Dies bedeutet, dass wir $ n $ eins haben, $ n $ zwei, $ n $ viertes usw., um den $ j $ th Bucket zu vertreten $ 2 $ Bit.

Wenn wir also $ m $ $ delta_k $ s in jedes der $ k $ Buckets einfügen, brauchen wir $ m links (2 + sum_ {j = 2}^{k} 2j-1 rechts) = m (( K^2 + 1) $ Bits. Die Summe aller $ delta_k $ darf 99'99'999 nicht überschreiten. Diese Summe unter der Annahme, dass wir die $ delta_k $ so klein wie möglich gehalten haben, ist $ m sum_ {j = 2}^{k} 2^{j-1} = m (2^k-2) $.

Hier ist also die Frage: Gibt es eine Kombination von $ k $ und $ m $ so, dass

• $ m (2^k-2) <100'000'000 $, z. B. der größte Wert beträgt $ <100 000 000 $,
• $ Km <1'000'000 $, z. B. gibt es höchstens eine Million Werte und
• $ m (k^2+1)> 8'000'000 $, z. B. verwenden wir mehr als 8 000 000 $ Bit?

Leider passiert das. Hier ist ein Diagramm der Anzahl der Bits, die in Maple mit berechnet werden plot( min( 100000000/(2^K-2) , 1000000/K ) * (K^2 + 1) , K=2..27 ):

Wir können also jede Sequenz von bis zu einer Million Zahlen in $ [0,99 , 999 , 999] für ungefähr 10 Millionen Bit darstellen. Dies liegt leider immer noch über der Spezifikation.

Aber wie können wir solche Zahlen sortieren? Denken Sie daran, dass die Zahlen nacheinander eintreten. Wenn jede Nummer eingeht, aktualisieren wir die Bucket Count ($ Mathcal O (1) $) und berechnen die neuen optimalen Präfixe für jeden Eimer ($ mathcal o () log log (i_ mathsf {max})) $ Wenn die Eimer in einem Heap indiziert sind). Wir laufen dann durch unsere codierten $ delta_k $, lesen jeden Eintrag, berechnen die jeweiligen $ i_k $ aus der kumulativen Summe und vergleichen sie mit dem neuen Wert. Wenn der berechnete $ i_k $ den neuen Wert überschreitet, codieren wir den neuen Wert und schreiben ihn zusammen mit dem angepassten $ delta_k $ unter Verwendung der neuen Codierung zurück. Andernfalls schreiben wir einfach die $ delta_k $ mit der neuen Encodierung zurück.

Aber schreibe wo? Nun, wenn wir unsere acht Millionen Bit als einen großen Ringpuffer behandeln, können wir die neue, neu codierte Sequenz von $ delta_k $ an die alte Sequenz anhängen und die alten Werte im Laufe der Zeit neu geschrieben. Wir haben fast 1 Million zusätzliche Teile aus dem schlechteren Szenario, und ich denke nicht, dass die Wiederkodierung dazu führen kann, dass diese Menge an Dehnungen nicht funktioniert.

Insgesamt lässt uns eine $ Mathcal o (n) $ Kosten für die Einführung der $ n $ tH $ N $ Elemente. Das ist nicht wirklich gut, aber die Geschwindigkeit schien kein Kriterium zu sein.