Sortieren von 1 Million 8-stelliger Zahlen mit 1 MB RAM

Question

Ich habe einen Computer mit 1 MB RAM und keinen anderen lokalen Speicher. Ich muss damit 1 Million 8-stellige Dezimalzahlen über eine TCP-Verbindung empfangen, sortieren und die sortierte Liste dann über eine andere TCP-Verbindung versenden.

Die Liste der Nummern kann Duplikate enthalten, die ich nicht verwerfen darf. Der Code wird im ROM gespeichert, so dass ich die Größe meines Codes nicht von den 1 MB abziehen muss. Ich habe bereits einen Code, der den Ethernet-Port ansteuert und TCP/IP-Verbindungen verarbeitet, und dieser benötigt 2 KB für seine Zustandsdaten, einschließlich eines 1-KB-Puffers, über den der Code Daten lesen und schreiben wird. Gibt es eine Lösung für dieses Problem?

Quellen für Fragen und Antworten:

slashdot.org

cleaton.net

Answer 1

Es gibt einen ziemlich raffinierten Trick, der hier noch nicht erwähnt wurde. Wir gehen davon aus, dass Sie keine zusätzliche Möglichkeit haben, Daten zu speichern, aber das ist nicht unbedingt der Fall.

Eine Möglichkeit, Ihr Problem zu umgehen, besteht darin, die folgende schreckliche Sache zu tun, die unter keinen Umständen von jemandem versucht werden sollte: Verwenden Sie den Netzwerkverkehr zum Speichern von Daten. Und nein, ich meine nicht NAS.

Sie können die Zahlen mit nur wenigen Bytes RAM auf folgende Weise sortieren:

• Nehmen Sie zunächst 2 Variablen: COUNTER y VALUE .
• Setzen Sie zunächst alle Register auf 0 ;
• Jedes Mal, wenn Sie eine Ganzzahl erhalten I , Inkrement COUNTER und setzen VALUE a max(VALUE, I) ;
• Senden Sie dann ein ICMP-Echo-Request-Paket mit Daten, die auf I zum Router. löschen I und wiederholen.
• Jedes Mal, wenn Sie das ICMP-Paket zurückerhalten, extrahieren Sie einfach die ganze Zahl und senden sie in einer weiteren Echo-Anforderung zurück. Dies führt zu einer riesigen Anzahl von ICMP-Anfragen, die die Ganzzahlen enthalten und hin- und hergeschickt werden.

Sobald COUNTER erreicht 1000000 haben Sie alle Werte, die in dem unaufhörlichen Strom von ICMP-Anfragen gespeichert sind, und VALUE enthält nun die maximale ganze Zahl. Wählen Sie einige threshold T >> 1000000 . Einstellung COUNTER auf Null. Jedes Mal, wenn Sie ein ICMP-Paket empfangen, erhöhen Sie COUNTER und senden Sie die enthaltene ganze Zahl I in einer weiteren Echoanforderung zurück, es sei denn I=VALUE in diesem Fall an das Ziel für die sortierten ganzen Zahlen übertragen. Sobald COUNTER=T , Dekrement VALUE von 1 , zurücksetzen COUNTER auf Null setzen und wiederholen. Sobald VALUE Wenn Sie den Wert Null erreichen, sollten Sie alle ganzen Zahlen in der Reihenfolge vom größten zum kleinsten Wert an das Ziel übertragen haben und nur etwa 47 Bits des Arbeitsspeichers für die beiden persistenten Variablen (und die geringe Menge, die Sie für die temporären Werte benötigen) verwendet haben.

Ich weiß, das ist schrecklich, und ich weiß, dass es alle möglichen praktischen Probleme geben kann, aber ich dachte, es könnte einige von Ihnen zum Lachen bringen oder Sie zumindest erschrecken.

Answer 2

Hier ist ein funktionierender C++-Code wodurch das Problem gelöst wird.

Beweis, dass die Speicherbeschränkungen erfüllt sind:

Herausgeber: Es gibt keinen Beweis für den maximalen Speicherbedarf, den der Autor weder in diesem Beitrag noch in seinen Blogs angibt. Da die Anzahl der Bits, die zur Kodierung eines Wertes erforderlich sind, von den zuvor kodierten Werten abhängt, ist ein solcher Nachweis wahrscheinlich nicht trivial. Der Autor merkt an, dass die größte kodierte Größe, über die er empirisch stolpern konnte, war 1011732 und wählen Sie die Puffergröße 1013000 willkürlich.

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

Zusammen nehmen diese beiden Arrays 1045000 Byte Speicherplatz ein. Damit bleiben 1048576 - 1045000 - 2×1024 = 1528 Bytes für die verbleibenden Variablen und den Stapelplatz.

Es läuft in etwa 23 Sekunden auf meinem Xeon W3520. Sie können überprüfen, ob das Programm funktioniert, indem Sie das folgende Python-Skript verwenden, wobei der Programmname sort1mb.exe .

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

Eine ausführliche Erläuterung des Algorithmus finden Sie in der folgenden Beitragsreihe:

• 1MB Sortierung erklärt
• Arithmetische Kodierung und das 1MB-Sortierproblem
• Arithmetische Kodierung mit Festkomma-Mathematik

Answer 3

Eine Lösung ist nur aufgrund des Unterschieds zwischen 1 Megabyte und 1 Million Byte möglich. Es gibt etwa 2 hoch 8093729,5 verschiedene Möglichkeiten, 1 Million 8-stellige Zahlen auszuwählen, wobei Duplikate erlaubt sind und die Reihenfolge keine Rolle spielt, so dass eine Maschine mit nur 1 Million Byte Arbeitsspeicher nicht genug Zustände hat, um alle Möglichkeiten darzustellen. Aber 1M (abzüglich 2k für TCP/IP) sind 1022*1024*8 = 8372224 Bits, also ist eine Lösung möglich.

Teil 1, erste Lösung

Dieser Ansatz braucht etwas mehr als 1M, ich werde ihn später so verfeinern, dass er in 1M passt.

Ich speichere eine kompakte sortierte Liste von Zahlen im Bereich 0 bis 99999999 als eine Folge von Unterlisten von 7-Bit-Zahlen. Die erste Teilliste enthält Zahlen von 0 bis 127, die zweite Teilliste enthält Zahlen von 128 bis 255, usw. 100000000/128 ist genau 781250, also werden 781250 solcher Teillisten benötigt.

Jede Teilliste besteht aus einem 2-Bit-Teillistenkopf, gefolgt von einem Teillistenkörper. Der Teillistenkörper nimmt 7 Bits pro Teillisteneintrag in Anspruch. Die Teillisten sind alle miteinander verkettet, und das Format macht es möglich zu erkennen, wo eine Teilliste endet und die nächste beginnt. Der Gesamtspeicherbedarf für eine vollständig gefüllte Liste beträgt 2*781250 + 7*1000000 = 8562500 Bits, also etwa 1,021 M-Byte.

Die 4 möglichen Werte für den Kopf der Teilliste sind:

00 Leere Teilliste, es folgt nichts.

01 Singleton, es gibt nur einen Eintrag in der Unterliste und die nächsten 7 Bits enthalten ihn.

10 Die Unterliste enthält mindestens 2 verschiedene Zahlen. Die Einträge werden in nicht-absteigender Reihenfolge gespeichert, mit der Ausnahme, dass der letzte Eintrag kleiner oder gleich dem ersten ist. Dadurch kann das Ende der Teilliste identifiziert werden. Zum Beispiel würden die Zahlen 2,4,6 als (4,6,2) gespeichert werden. Die Zahlen 2,2,3,4,4 würden als (2,3,4,4,2) gespeichert.

11 Die Unterliste enthält 2 oder mehr Wiederholungen einer einzigen Zahl. Die nächsten 7 Bits geben die Zahl an. Danach folgen null oder mehr 7-Bit-Einträge mit dem Wert 1, gefolgt von einem 7-Bit-Eintrag mit dem Wert 0. Die Länge des Unterlistenkörpers bestimmt die Anzahl der Wiederholungen. Zum Beispiel würden die Zahlen 12,12 als (12,0) gespeichert, die Zahlen 12,12,12 als (12,1,0), 12,12,12,12 als (12,1,1,0) und so weiter.

Ich beginne mit einer leeren Liste, lese eine Reihe von Zahlen ein und speichere sie als 32-Bit-Ganzzahlen, sortiere die neuen Zahlen an Ort und Stelle (wahrscheinlich mit Heapsort) und führe sie dann in einer neuen kompakten sortierten Liste zusammen. Das wiederhole ich so lange, bis keine Zahlen mehr zu lesen sind, dann gehe ich die kompakte Liste noch einmal durch, um die Ausgabe zu erzeugen.

Die folgende Zeile stellt den Speicher kurz vor dem Beginn der Listenzusammenführung dar. Die "O "s sind die Bereiche, die die sortierten 32-Bit-Ganzzahlen enthalten. Die "X "s sind die Bereiche, die die alte kompakte Liste enthalten. Die "="-Zeichen sind der Erweiterungsraum für die kompakte Liste, 7 Bits für jede ganze Zahl in den "O "s. Die "Z "s sind anderer zufälliger Overhead.

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

Die Zusammenführungsroutine beginnt mit dem Lesen am äußersten linken "O" und am äußersten linken "X" und mit dem Schreiben am äußersten linken "=". Der Schreibzeiger holt den Lesezeiger für die kompakte Liste erst ein, wenn alle neuen ganzen Zahlen zusammengeführt sind, da beide Zeiger für jede Teilliste um 2 Bits und für jeden Eintrag in der alten kompakten Liste um 7 Bits vorrücken und für die 7-Bit-Einträge für die neuen Zahlen noch genügend Platz vorhanden ist.

Teil 2, die Unterbringung in 1M

Um die obige Lösung in 1M zu quetschen, muss ich

A

B

C

D

M

S

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

T

I

W

W

T

1

B

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

S

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

S

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

I

T

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

E

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

T

T

P

W

W

S

h

Answer 4

Die Antwort von Gilmanov ist in ihren Annahmen völlig falsch. Sie beginnt mit Spekulationen, die auf einer sinnlos Ein-Millionen-Maß fortlaufend ganze Zahlen. Das bedeutet keine Lücken. Diese zufälligen Lücken, auch wenn sie noch so klein sind, sind wirklich eine schlechte Idee.

Versuchen Sie es selbst. Nehmen Sie 1 Million zufällige 27-Bit-Ganzzahlen, sortieren Sie sie, komprimieren Sie sie mit 7-Zip , xz, jede beliebige LZMA-Datei, die Sie wünschen. Das Ergebnis ist über 1,5 MB. Die Voraussetzung dafür ist die Komprimierung der fortlaufenden Nummern. Auch Delta-Kodierung davon ist über 1,1 MB . Und egal, das verbraucht über 100 MB RAM für die Komprimierung. Selbst die komprimierten Ganzzahlen passen also nicht zu dem Problem und die RAM-Nutzung während der Laufzeit ist egal .

Es macht mich traurig, dass die Leute nur hübsche Grafiken und Rationalisierungen hoch bewerten.

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

Jetzt komprimieren ints.bin mit LZMA...

    $ xz -f --keep ints.bin       # 100 MB RAM
    $ 7z a ints.bin.7z ints.bin   # 130 MB RAM
    $ ls -lh ints.bin*
        3.8M ints.bin
        1.1M ints.bin.7z
        1.2M ints.bin.xz

Answer 5

Ich denke, eine Möglichkeit, darüber nachzudenken, ist aus der Sicht der Kombinatorik: Wie viele mögliche Kombinationen von sortierten Zahlenreihenfolgen gibt es? Wenn wir der Kombination 0,0,0,....,0 den Code 0 geben, und 0,0,0,...,1 den Code 1, und 99999999, 99999999, ... 99999999 der Code N, was ist N? Mit anderen Worten, wie groß ist der Ergebnisraum?

Nun, eine Möglichkeit, darüber nachzudenken, ist die Feststellung, dass es sich um eine Bijektion des Problems handelt, die Anzahl der monotonen Pfade in einem N x M-Gitter zu finden, wobei N = 1.000.000 und M = 100.000.000. Mit anderen Worten: Wie viele kürzeste Wege gibt es in einem Gitter, das 1.000.000 breit und 100.000.000 hoch ist, von unten links nach oben rechts? Kürzeste Wege setzen natürlich voraus, dass man sich immer nur entweder nach rechts oder nach oben bewegt (würde man sich nach unten oder nach links bewegen, würde man einen bereits erreichten Fortschritt wieder rückgängig machen). Um zu sehen, dass es sich hierbei um eine Bijektion unseres Zahlensortierproblems handelt, beachten Sie Folgendes:

Sie können sich jeden horizontalen Schenkel in unserem Pfad als eine Zahl in unserer Reihenfolge vorstellen, wobei die Y-Position des Schenkels den Wert darstellt.

Wenn sich der Pfad also einfach bis zum Ende nach rechts bewegt und dann ganz nach oben springt, entspricht das der Reihenfolge 0,0,0,...,0. Wenn er stattdessen mit einem Sprung ganz nach oben beginnt und sich dann 1.000.000 Mal nach rechts bewegt, entspricht das 99999999,99999999,..., 99999999. Ein Pfad, auf dem er sich einmal nach rechts, dann einmal nach oben, dann einmal nach rechts, dann einmal nach oben usw. bis zum Ende bewegt (und dann notwendigerweise den ganzen Weg nach oben springt), entspricht 0,1,2,3,...,999999.

Zum Glück für uns ist dieses Problem bereits gelöst, ein solches Gitter hat (N + M) Wählen Sie (M) Pfade:

(1.000.000 + 100.000.000) Wählen Sie (100.000.000) ~= 2,27 * 10^2436455

N ist also gleich 2,27 * 10^2436455, und so steht der Code 0 für 0,0,0,...,0 und der Code 2,27 * 10^2436455 und einige Änderungen für 99999999,99999999,..., 99999999.

Um alle Zahlen von 0 bis 2,27 * 10^2436455 zu speichern, benötigt man lg2 (2,27 * 10^2436455) = 8,0937 * 10^6 Bits.

1 Megabyte = 8388608 Bits > 8093700 Bits

Es sieht also so aus, als ob wir zumindest genug Platz hätten, um das Ergebnis zu speichern! Das Interessante ist jetzt natürlich die Sortierung, während die Zahlen hereinströmen. Ich bin mir nicht sicher, wie ich das am besten anstellen soll, da wir noch 294908 Bits haben. Ich könnte mir vorstellen, dass eine interessante Technik darin besteht, an jedem Punkt davon auszugehen, dass dies die gesamte Reihenfolge ist, den Code für diese Reihenfolge zu finden und dann, wenn man eine neue Zahl erhält, zurückzugehen und den vorherigen Code zu aktualisieren. Hand winken Hand winken.