wake-up-neo.com

Sortieren von 1 Million 8-stelligen Zahlen in 1 MB RAM

Ich habe einen Computer mit 1 MB RAM und keinem anderen lokalen Speicher. Ich muss es verwenden, um 1 Million 8-stellige Dezimalzahlen über eine TCP -Verbindung zu akzeptieren, sie zu sortieren und die sortierte Liste dann über eine andere TCP -Verbindung auszusenden.

Die Liste der Nummern kann Duplikate enthalten, die ich nicht verwerfen darf. Der Code wird im ROM abgelegt, sodass ich die Größe meines Codes nicht von 1 MB subtrahieren muss. Ich habe bereits Code zum Ansteuern des Ethernet-Ports und zum Verarbeiten von TCP/IP-Verbindungen. Für die Statusdaten sind 2 KB erforderlich, einschließlich eines 1-KB-Puffers, über den der Code Daten liest und schreibt. Gibt es eine Lösung für dieses Problem?

Quellen für Fragen und Antworten:

slashdot.org

cleaton.net

636

Eine Lösung ist nur aufgrund der Differenz zwischen 1 Megabyte und 1 Million Bytes möglich. Es gibt ungefähr 2 bis 8093729.5 verschiedene Möglichkeiten, um 1 Million 8-stellige Zahlen mit Duplikaten auszuwählen und unwichtig zu bestellen. Eine Maschine mit nur 1 Million Bytes von RAM hat also nicht genug Zustände, um alle darzustellen die Möglichkeiten. 1 MB (weniger als 2 KB für TCP/IP) entspricht jedoch 1022 * 1024 * 8 = 8372224 Bit, sodass eine Lösung möglich ist.

Teil 1, Ausgangslösung

Dieser Ansatz benötigt etwas mehr als 1 Million, ich werde ihn verfeinern, damit er später in 1 Million passt.

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

Jede Unterliste besteht aus einem 2-Bit-Unterlistenkopf, gefolgt von einem Unterlistenkörper. Der Unterlistenhauptteil belegt 7 Bits pro Unterlisteneintrag. Die Unterlisten sind alle miteinander verknüpft, und anhand des Formats kann festgestellt werden, wo eine Unterliste endet und die nächste beginnt. Der für eine vollständig gefüllte Liste erforderliche Gesamtspeicher beträgt 2 * 781250 + 7 * 1000000 = 8562500 Bits, was ungefähr 1,021 MByte entspricht.

Die 4 möglichen Werte für den Unterlistenkopf sind:

00 Leere Unterliste, nichts folgt.

01 Singleton, es gibt nur einen Eintrag in der Unterliste und die nächsten 7 Bits halten 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 Unterliste identifiziert werden. Beispielsweise würden die Zahlen 2,4,6 als (4,6,2) gespeichert. 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 einzelnen Nummer. Die nächsten 7 Bits geben die Nummer an. Dann kommen 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 würden als (12,1,0) gespeichert, 12,12,12,12 wären (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üge sie dann zu einer neuen kompakten sortierten Liste zusammen. Wiederholen Sie diesen Vorgang, bis keine Nummern mehr zu lesen sind, und durchlaufen Sie die kompakte Liste erneut, um die Ausgabe zu generieren.

Die Zeile darunter steht für den Speicher unmittelbar vor dem Start des Zusammenführungsvorgangs. Die "O" sind der Bereich, der die sortierten 32-Bit-Ganzzahlen enthält. Die "X" sind der Bereich, der die alte kompakte Liste enthält. Die "=" Zeichen sind der Erweiterungsraum für die kompakte Liste, 7 Bits für jede Ganzzahl in den "O". Die "Z" sind andere zufällige Gemeinkosten.

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

Die Zusammenführungsroutine beginnt mit dem Lesen ganz links "O" und ganz links "X" und beginnt mit dem Schreiben ganz links "=". Der Schreibzeiger fängt den Lesezeiger für die kompakte Liste erst dann ab, wenn alle neuen Ganzzahlen zusammengeführt wurden, da beide Zeiger 2 Bit für jede Unterliste und 7 Bit für jeden Eintrag in der alten kompakten Liste vorrücken und genügend Platz für die vorhanden ist 7-Bit-Einträge für die neuen Nummern.

Teil 2, stopfe es in 1M

Um die obige Lösung in 1M zu zerlegen, muss das kompakte Listenformat etwas kompakter gestaltet werden. Ich werde einen der Unterlistentypen entfernen, so dass es nur 3 verschiedene mögliche Unterlistenkopfwerte gibt. Dann kann ich "00", "01" und "1" als Unterlisten-Header-Werte verwenden und ein paar Bits speichern. Die Unterlistentypen sind:

Eine leere Unterliste, nichts folgt.

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

C Die Unterliste enthält mindestens 2 verschiedene Nummern. 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 Unterliste identifiziert werden. Beispielsweise würden die Zahlen 2,4,6 als (4,6,2) gespeichert. Die Zahlen 2,2,3,4,4 würden als (2,3,4,4,2) gespeichert.

D Die Unterliste besteht aus 2 oder mehr Wiederholungen einer einzelnen Nummer.

Meine 3 Unterlisten-Header-Werte sind "A", "B" und "C", daher brauche ich eine Möglichkeit, Unterlisten vom Typ D darzustellen.

Angenommen, ich habe den C-Typ-Unterlistenkopf, gefolgt von 3 Einträgen, wie "C [17] [101] [58]". Dies kann nicht Teil einer gültigen C-Typ-Unterliste sein, wie oben beschrieben, da der dritte Eintrag kleiner als der zweite, aber größer als der erste ist. Ich kann diese Art von Konstrukt verwenden, um eine Unterliste vom Typ D darzustellen. In Bit-Begriffen ist überall, wo ich "C {00 ?????} {1 ??????} {01 ?????}" habe, eine unmögliche C-Typ-Unterliste. Ich werde dies verwenden, um eine Unterliste darzustellen, die aus 3 oder mehr Wiederholungen einer einzelnen Zahl besteht. Die ersten beiden 7-Bit-Wörter codieren die Zahl (die "N" Bits unten) und werden von null oder mehr {0100001} Wörtern gefolgt von einem {0100000} Wort gefolgt.

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

Das lässt nur Listen, die genau 2 Wiederholungen einer einzelnen Zahl enthalten. Ich werde diejenigen mit einem anderen unmöglichen C-Typ-Unterlistenmuster darstellen: "C {0 ??????} {11 ?????} {10 ?????}". Es gibt viel Platz für die 7 Bits der Zahl in den ersten 2 Wörtern, aber dieses Muster ist länger als die Unterliste, die es darstellt, was die Dinge etwas komplexer macht. Die fünf Fragezeichen am Ende können nicht als Teil des Musters betrachtet werden, daher habe ich: "C {0NNNNNN} {11N ????} 10" als mein Muster, wobei die zu wiederholende Nummer im "N" gespeichert ist "s. Das sind 2 Bits zu lang.

Ich muss 2 Bits ausleihen und sie von den 4 nicht verwendeten Bits in diesem Muster zurückzahlen. Wenn Sie beim Lesen auf "C {0NNNNNN} {11N00AB} 10" stoßen, geben Sie 2 Instanzen der Zahl in den "N" aus, überschreiben Sie die "10" am Ende mit den Bits A und B und spulen Sie den Lesezeiger um 2 zurück Bits. Destruktive Lesevorgänge sind für diesen Algorithmus in Ordnung, da jede kompakte Liste nur einmal durchlaufen wird.

Wenn Sie eine Unterliste mit 2 Wiederholungen einer einzelnen Zahl schreiben, schreiben Sie "C {0NNNNNN} 11N00" und setzen Sie den Zähler für geliehene Bits auf 2. Bei jedem Schreiben, bei dem der Zähler für geliehene Bits ungleich Null ist, wird er für jedes geschriebene Bit und dekrementiert "10" wird geschrieben, wenn der Zähler Null erreicht. Also werden die nächsten 2 geschriebenen Bits in die Slots A und B geschrieben, und dann wird die "10" auf das Ende fallen gelassen.

Mit 3 Unterlistenkopfwerten, die durch "00", "01" und "1" dargestellt werden, kann ich dem beliebtesten Unterlistentyp "1" zuweisen. Ich benötige eine kleine Tabelle, um Unterlistenkopfwerte zu Unterlistentypen zuzuordnen, und ich benötige einen Vorkommenszähler für jeden Unterlistentyp, damit ich weiß, was die beste Unterlistenkopfzuordnung ist.

Die minimale Darstellung einer vollständig ausgefüllten kompakten Liste im schlimmsten Fall tritt auf, wenn alle Unterlistentypen gleichermaßen beliebt sind. In diesem Fall speichere ich 1 Bit für jeweils 3 Unterlisten-Header, sodass die Listengröße 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083,3 Bit beträgt. Aufrunden auf eine 32-Bit-Wortgrenze, also 8302112 Bit oder 1037764 Byte.

1 MB minus 2 KB für den TCP/IP-Status und die Puffer sind 1022 * 1024 = 1046528 Byte, sodass ich 8764 Byte zum Spielen habe.

Aber wie sieht es mit der Änderung der Zuordnung der Unterlisten-Header aus? In der folgenden Speicherzuordnung ist "Z" ein zufälliger Overhead, "=" ist freier Speicherplatz, "X" ist die kompakte Liste.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Beginnen Sie mit dem Lesen ganz links "X" und schreiben Sie ganz links "=" und arbeiten Sie nach rechts. Wenn dies erledigt ist, wird die kompakte Liste etwas kürzer und befindet sich am falschen Ende des Speichers:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Dann muss ich nach rechts rangieren:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Während des Änderungsprozesses der Header-Zuordnung wird bis zu 1/3 der Header der Unterliste von 1 Bit auf 2 Bit geändert. Im schlimmsten Fall stehen alle an der Spitze der Liste. Bevor ich anfange, benötige ich mindestens 781250/3 Bit freien Speicherplatz. Dies führt mich zu den Speicheranforderungen der vorherigen Version der kompakten Liste zurück: (

Um das zu umgehen, teile ich die 781250-Unterlisten in 10 Unterlistengruppen mit jeweils 78125 Unterlisten auf. Jede Gruppe verfügt über eine eigene, unabhängige Zuordnung von Unterlisten-Headern. Mit den Buchstaben A bis J für die Gruppen:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Jede Unterlistengruppe verkleinert sich oder bleibt während einer Änderung der Unterlisten-Header-Zuordnung gleich:

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

Die schlimmste vorübergehende Erweiterung einer Unterlistengruppe während einer Zuordnungsänderung ist 78125/3 = 26042 Bits unter 4k. Wenn ich 4 KB plus 1037764 Byte für eine vollständig ausgefüllte kompakte Liste zulasse, verbleiben 8764 - 4096 = 4668 Byte für die "Z" in der Speicherkarte.

Das sollte für die 10 Sublist-Header-Mapping-Tabellen, 30 Sublist-Header-Vorkommenszählungen und die anderen paar Zähler, Zeiger und kleinen Puffer, die ich benötige, und den Platz, den ich verwendet habe, ohne es zu bemerken, wie Stapelspeicherplatz für Rücksprungadressen und für Funktionsaufrufe, ausreichend sein lokale Variablen.

Teil 3, wie lange würde die Ausführung dauern?

Bei einer leeren kompakten Liste wird der 1-Bit-Listenkopf für eine leere Unterliste verwendet, und die Anfangsgröße der Liste beträgt 781250 Bit. Im schlimmsten Fall wächst die Liste um 8 Bits für jede hinzugefügte Nummer, sodass 32 + 8 = 40 Bits freier Speicherplatz für jede der 32-Bit-Nummern erforderlich sind, um sie oben im Listenpuffer abzulegen und dann zu sortieren und zusammenzuführen. Im schlimmsten Fall führt das Ändern der Unterlisten-Header-Zuordnung zu einer Speicherplatzbelegung von 2 * 781250 + 7 * Einträgen - 781250/3 Bits.

Mit der Richtlinie, die Zuordnung der Unterlisten-Header nach jeder fünften Zusammenführung zu ändern, sobald sich mindestens 800000 Nummern in der Liste befinden, würde ein Worst-Case-Lauf insgesamt etwa 30 Millionen Lese- und Schreibvorgänge für kompakte Listen umfassen.

Quelle:

http://nick.cleaton.net/ramsortsol.html

169

Es gibt einen ziemlich hinterhältigen Trick, der hier noch nicht erwähnt wurde. Wir gehen davon aus, dass Sie keine zusätzliche Möglichkeit zum Speichern von Daten haben, dies ist jedoch nicht unbedingt der Fall.

Eine Möglichkeit, Ihr Problem zu umgehen, besteht darin, Folgendes zu tun: Verwenden Sie den Netzwerkverkehr, um Daten zu speichern. Und nein, ich meine nicht NAS.

Sie können die Zahlen mit nur wenigen Bytes RAM folgendermaßen sortieren:

  • Nehmen Sie zuerst 2 Variablen: COUNTER und VALUE.
  • Stellen Sie zuerst alle Register auf 0;
  • Jedes Mal, wenn Sie eine Ganzzahl I erhalten, erhöhen Sie COUNTER und setzen VALUE auf max(VALUE, I);
  • Senden Sie dann ein ICMP-Echoanforderungspaket mit dem Datensatz I an den Router. Ich lösche und wiederhole.
  • Jedes Mal, wenn Sie das zurückgegebene ICMP-Paket empfangen, extrahieren Sie einfach die Ganzzahl und senden sie in einer weiteren Echoanforderung erneut aus. Dies erzeugt eine große Anzahl von ICMP-Anforderungen, die die ganzen Zahlen enthalten.

Sobald COUNTER1000000 erreicht, sind alle Werte im ununterbrochenen Stream der ICMP-Anforderungen gespeichert, und VALUE enthält jetzt die maximale Ganzzahl. Wähle einen threshold T >> 1000000. Setzen Sie COUNTER auf Null. Jedes Mal, wenn Sie ein ICMP-Paket empfangen, erhöhen Sie COUNTER und senden Sie die enthaltene Ganzzahl I in einer weiteren Echoanforderung zurück, es sei denn, I=VALUE, und senden Sie sie in diesem Fall an das Ziel für die sortierten Ganzzahlen. Sobald COUNTER=T dekrementiert VALUE um 1, setzt COUNTER auf Null zurück und wiederholt. Sobald VALUE Null erreicht, sollten Sie alle Ganzzahlen in der Reihenfolge vom größten zum kleinsten zum Ziel übertragen und nur ungefähr 47 Bits RAM für die zwei beständigen Variablen (und für welchen kleinen Betrag Sie auch immer) verwendet haben Notwendigkeit für die temporären Werte).

Ich weiß, dass dies schrecklich ist, und ich weiß, dass es viele praktische Probleme geben kann, aber ich dachte, es könnte einige von Ihnen zum Lachen bringen oder Sie zumindest entsetzen.

427
Joe Fitzsimons

Hier ist ein funktionierender C++ - Code , der das Problem löst.

Beweis, dass die Speicherbedingungen erfüllt sind:

Editor: Es gibt weder in diesem Beitrag noch in seinen Blogs einen Beweis für den maximalen Speicherbedarf des Autors. Da die Anzahl der zum Codieren eines Werts erforderlichen Bits von den zuvor codierten Werten abhängt, ist ein solcher Beweis wahrscheinlich nicht trivial. Der Autor stellt fest, dass die größte codierte Größe, auf die er empirisch stoßen konnte, 1011732 war und wählte 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 belegen diese beiden Arrays 1045000 Byte Speicherplatz. Damit verbleiben 1048576 - 1045000 - 2 × 1024 = 1528 Byte für die verbleibenden Variablen und den Stapelspeicher.

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

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 Reihe von Beiträgen:

409
preshing

Bitte beachten Sie die erste richtige Antwort oder die spätere Antwort mit arithmetischer Codierung . Nachfolgend finden Sie möglicherweise Ein bisschen Spaß, aber keine 100% ige kugelsichere Lösung.

Dies ist eine interessante Aufgabe und hier ist eine andere Lösung. Ich hoffe, jemand würde das Ergebnis nützlich (oder zumindest interessant) finden.

Stufe 1: Anfangsdatenstruktur, grobe Komprimierungsmethode, grundlegende Ergebnisse

Lassen Sie uns ein paar einfache Berechnungen anstellen: Wir haben 1M (1048576 Bytes) RAM, um anfangs 10 ^ 6 8-stellige Dezimalzahlen zu speichern. [0; 99999999]. Um eine Zahl zu speichern, werden 27 Bits benötigt (unter der Annahme, dass vorzeichenlose Zahlen verwendet werden). Um einen Rohdatenstrom zu speichern, werden also ~ 3,5 M RAM benötigt. Jemand hat bereits gesagt, dass dies nicht machbar zu sein scheint, aber ich würde sagen, dass die Aufgabe gelöst werden kann, wenn die Eingabe "gut genug" ist. Grundsätzlich besteht die Idee darin, die Eingabedaten mit einem Kompressionsfaktor von 0,29 oder höher zu komprimieren und ordnungsgemäß zu sortieren.

Lösen wir zuerst das Komprimierungsproblem. Es gibt bereits einige relevante Tests:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

Ich habe einen Test durchgeführt, um eine Million aufeinanderfolgender Ganzzahlen unter Verwendung verschiedener Komprimierungsformen zu komprimieren. Die Ergebnisse sind wie folgt:

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Offenbar ist LZMA ( Lempel-Ziv-Markov-Kettenalgorithmus ) eine gute Wahl, um fortzufahren. Ich habe einen einfachen PoC vorbereitet, aber es gibt noch einige Details, die hervorgehoben werden müssen:

  1. Der Speicher ist begrenzt, daher sollten Nummern vorsortiert und komprimierte Eimer (dynamische Größe) als temporärer Speicher verwendet werden
  2. Es ist einfacher, mit vorsortierten Daten einen besseren Komprimierungsfaktor zu erzielen, sodass für jeden Bucket ein statischer Puffer vorhanden ist (Zahlen aus dem Puffer müssen vor LZMA sortiert werden).
  3. Jeder Eimer enthält einen bestimmten Bereich, sodass die endgültige Sortierung für jeden Eimer separat erfolgen kann
  4. Die Größe des Buckets kann richtig eingestellt werden, sodass genügend Speicher vorhanden ist, um gespeicherte Daten zu dekomprimieren und die endgültige Sortierung für jeden Bucket separat durchzuführen

In-memory sorting

Bitte beachten Sie, dass der angehängte Code ein POC ist. Er kann nicht als endgültige Lösung verwendet werden. Er demonstriert lediglich die Idee, mehrere kleinere Puffer zum Speichern zu verwenden vorsortierte Nummern in optimaler Weise (möglicherweise komprimiert). LZMA wird nicht als endgültige Lösung vorgeschlagen. Es wird als schnellstmöglicher Weg verwendet, um eine Komprimierung für diesen PoC einzuführen.

Siehe den PoC-Code unten (bitte beachten Sie, dass es sich nur um eine Demo handelt, um sie zu kompilieren LZMA-Java wird benötigt):

public class MemorySortDemo {

static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;

static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;

static class Producer {
    private Random random = new Random();
    public int produce() { return random.nextInt(NUM_MAX); }
}

static class Bucket {
    public int size, pointer;
    public int[] buffer = new int[BUFFER_SIZE];

    public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
    public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
    public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();

    public void submitBuffer() throws IOException {
        Arrays.sort(buffer, 0, pointer);

        for (int j = 0; j < pointer; j++) {
            tempDataOut.writeInt(buffer[j]);
            size++;
        }            
        pointer = 0;
    }

    public void write(int value) throws IOException {
        if (isBufferFull()) {
            submitBuffer();
        }
        buffer[pointer++] = value;
    }

    public boolean isBufferFull() {
        return pointer == BUFFER_SIZE;
    }

    public byte[] compressData() throws IOException {
        tempDataOut.close();
        return compress(tempOut.toByteArray());
    }        

    private byte[] compress(byte[] input) throws IOException {
        final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
        final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));

        final Encoder encoder = new Encoder();
        encoder.setEndMarkerMode(true);
        encoder.setNumFastBytes(0x20);
        encoder.setDictionarySize(DICT_SIZE);
        encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);

        ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
        encoder.writeCoderProperties(encoderPrperties);
        encoderPrperties.flush();
        encoderPrperties.close();

        encoder.code(in, out, -1, -1, null);
        out.flush();
        out.close();
        in.close();

        return encoderPrperties.toByteArray();
    }

    public int[] decompress(byte[] properties) throws IOException {
        InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
        ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
        BufferedOutputStream out = new BufferedOutputStream(data);

        Decoder decoder = new Decoder();
        decoder.setDecoderProperties(properties);
        decoder.code(in, out, 4 * size);

        out.flush();
        out.close();
        in.close();

        DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
        int[] array = new int[size];
        for (int k = 0; k < size; k++) {
            array[k] = input.readInt();
        }

        return array;
    }
}

static class Sorter {
    private Bucket[] bucket = new Bucket[BUCKETS];

    public void doSort(Producer p, Consumer c) throws IOException {

        for (int i = 0; i < bucket.length; i++) {  // allocate buckets
            bucket[i] = new Bucket();
        }

        for(int i=0; i< NUM_COUNT; i++) {         // produce some data
            int value = p.produce();
            int bucketId = value/BUCKET_RANGE;
            bucket[bucketId].write(value);
            c.register(value);
        }

        for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
            bucket[i].submitBuffer();
        }

        byte[] compressProperties = null;
        for (int i = 0; i < bucket.length; i++) { // compress the data
            compressProperties = bucket[i].compressData();
        }

        printStatistics();

        for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
            int[] array = bucket[i].decompress(compressProperties);
            Arrays.sort(array);

            for(int v : array) {
                c.consume(v);
            }
        }
        c.finalCheck();
    }

    public void printStatistics() {
        int size = 0;
        int sizeCompressed = 0;

        for (int i = 0; i < BUCKETS; i++) {
            int bucketSize = 4*bucket[i].size;
            size += bucketSize;
            sizeCompressed += bucket[i].compressedOut.size();

            System.out.println("  bucket[" + i
                    + "] contains: " + bucket[i].size
                    + " numbers, compressed size: " + bucket[i].compressedOut.size()
                    + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
        }

        System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
                + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
                + String.format(" compression factor %.2f",(double)sizeCompressed/size));
    }
}

static class Consumer {
    private Set<Integer> values = new HashSet<>();

    int v = -1;
    public void consume(int value) {
        if(v < 0) v = value;

        if(v > value) {
            throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
        }else{
            v = value;
            values.remove(value);
        }
    }

    public void register(int value) {
        values.add(value);
    }

    public void finalCheck() {
        System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
    }
}

public static void main(String[] args) throws IOException {
    Producer p = new Producer();
    Consumer c = new Consumer();
    Sorter sorter = new Sorter();

    sorter.doSort(p, c);
}
}

Mit Zufallszahlen ergibt sich folgendes:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

Für eine einfache aufsteigende Reihenfolge (ein Bucket wird verwendet) ergibt sich:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

EDIT

Fazit:

  1. Versuche nicht, das Natur zu täuschen
  2. Verwenden Sie einfachere Komprimierung mit geringerem Speicherbedarf
  3. Einige zusätzliche Hinweise sind wirklich erforderlich. Eine gemeinsame kugelsichere Lösung scheint nicht durchführbar zu sein.

Stufe 2: Verbesserte Komprimierung, endgültige Schlussfolgerung

Wie bereits im vorigen Abschnitt erwähnt, kann jede geeignete Komprimierungstechnik verwendet werden. Lassen Sie uns also LZMA loswerden, und zwar zugunsten eines einfacheren und (wenn möglich) besseren Ansatzes. Es gibt viele gute Lösungen, einschließlich arithmetische Codierung , Radixbaum usw.

Auf jeden Fall wird ein einfaches, aber nützliches Codierungsschema anschaulicher sein als eine andere externe Bibliothek, die einen raffinierten Algorithmus bereitstellt. Die eigentliche Lösung ist ziemlich einfach: Da es Buckets mit teilweise sortierten Daten gibt, können Deltas anstelle von Zahlen verwendet werden.

encoding scheme

Random Input Test zeigt etwas bessere Ergebnisse:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

Beispielcode

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

Bitte beachten Sie diesen Ansatz:

  1. verbraucht nicht viel Speicher
  2. arbeitet mit Streams
  3. liefert nicht so schlechte ergebnisse

Den vollständigen Code finden Sie hier , Implementierungen von BinaryInput und BinaryOutput hier

Endgültige Schlussfolgerung

Keine endgültige Schlussfolgerung :) Manchmal ist es eine gute Idee, eine Ebene nach oben zu gehen und die Aufgabe aus einer Meta-Ebene Sicht zu überprüfen.

Es hat Spaß gemacht, etwas Zeit mit dieser Aufgabe zu verbringen. Übrigens gibt es unten eine Menge interessanter Antworten. Vielen Dank für Ihre Aufmerksamkeit und viel Spaß beim Schreiben.

363
Renat Gilmanov

Gilmanovs Antwort ist in seinen Annahmen sehr falsch. Es beginnt zu spekulieren, basierend auf einer sinnlosen Zahl von einer Million aufeinanderfolgenden ganzen Zahlen. Das bedeutet keine Lücken. Diese zufälligen Lücken, wie klein sie auch sein mögen, machen es wirklich zu einer schlechten Idee.

Versuch es selber. Holen Sie sich 1 Million zufällige 27-Bit-Ganzzahlen, sortieren Sie sie und komprimieren Sie sie mit 7-Zip , xz, wie auch immer Sie LZMA wollen. Das Ergebnis ist über 1,5 MB. Die Prämisse ist die Komprimierung von fortlaufenden Zahlen. Gerade Delta-Codierung davon ist über 1,1 MB . Und egal, dies verwendet über 100 MB RAM für die Komprimierung. Sogar die komprimierten Ganzzahlen passen also nicht zum Problem und es spielt keine Rolle, wie viel Zeit RAM verwendet wird .

Es macht mich traurig, wie die Leute nur hübsche Grafiken und Rationalisierungen positiv 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 ints.bin mit LZMA komprimieren ...

$ 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
55
alecco

Ich denke, eine Möglichkeit, dies zu sehen, ist aus kombinatorischer Sicht: Wie viele mögliche Kombinationen sortierter Nummernreihenfolgen gibt es? Wenn wir die Kombination 0,0,0, ...., 0 den Code 0 und 0,0,0, ..., 1 den Code 1 und 99999999, 99999999, ... 99999999 den Code N angeben, was ist n Mit anderen Worten, wie groß ist der Ergebnisraum?

Nun, eine Möglichkeit, darüber nachzudenken, besteht darin, zu bemerken, dass dies ein Nebeneffekt des Problems ist, die Anzahl der monotonen Pfade in einem N × M-Gitter zu finden, wobei N = 1.000.000 und M = 100.000.000. Mit anderen Worten, wenn Sie ein Raster haben, das 1.000.000 breit und 100.000.000 hoch ist, wie viele kürzeste Wege von links unten nach rechts oben gibt es? Auf kürzesten Wegen müssen Sie sich natürlich immer nur nach rechts oder oben bewegen (wenn Sie sich nach unten oder links bewegen würden, würden Sie den zuvor erreichten Fortschritt rückgängig machen). Beachten Sie die folgenden Punkte, um zu sehen, wie dies ein Verstoß gegen unser Problem der Nummernsortierung ist:

Sie können sich jedes horizontale Bein in unserem Pfad als Zahl in unserer Bestellung vorstellen, wobei die Y-Position des Beins den Wert darstellt.

enter image description here

Bewegt sich der Pfad also einfach ganz nach rechts und springt dann ganz nach oben, was der Reihenfolge 0,0,0, ..., 0 entspricht. Wenn es stattdessen beginnt, indem es ganz nach oben springt und sich dann 1.000.000 Mal nach rechts bewegt, entspricht dies 99999999.99999999, ..., 99999999. Ein Pfad, auf dem es sich einmal nach rechts, dann einmal nach oben und dann nach rechts bewegt , dann einmal nach oben usw. bis zum Ende (springt dann notwendigerweise ganz nach oben), entspricht 0,1,2,3, ..., 999999.

Zum Glück ist dieses Problem für uns 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 repräsentiert der Code 0 0,0,0, ..., 0 und der Code 2,27 * 10 ^ 2436455 und einige Änderungen repräsentieren 99999999,99999999, ..., 99999999.

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

1 Megabyte = 8388608 Bits> 8093700 Bits

Es sieht also so aus, als hätten wir tatsächlich genug Platz, um das Ergebnis zu speichern! Jetzt ist das Interessante natürlich das Sortieren, während die Zahlen einströmen. Wir sind uns nicht sicher, ob der beste Ansatz dafür gegeben ist. Wir haben noch 294908 Bits übrig. Ich stelle mir eine interessante Technik vor, zu jedem Zeitpunkt davon auszugehen, dass dies die gesamte Bestellung ist, den Code für diese Bestellung zu finden und dann, wenn Sie eine neue Nummer erhalten, den vorherigen Code zu aktualisieren. Handwelle Handwelle.

Meine Vorschläge hier verdanken viel Dans Lösung

Zunächst gehe ich davon aus, dass die Lösung alle möglichen Eingabelisten verarbeiten muss. Ich denke, dass die populären Antworten diese Annahme nicht treffen (was IMO ein großer Fehler ist).

Es ist bekannt, dass keine Form der verlustfreien Komprimierung die Größe aller Eingaben verringert.

Bei allen gängigen Antworten wird davon ausgegangen, dass die Komprimierung so effektiv ist, dass sie zusätzlichen Speicherplatz bietet. In der Tat ein Teil zusätzlichen Speicherplatzes, der groß genug ist, um einen Teil der unvollständigen Liste in unkomprimierter Form zu speichern und die Sortiervorgänge auszuführen. Dies ist nur eine schlechte Annahme.

Für eine solche Lösung kann jeder, der weiß, wie seine Komprimierung erfolgt, einige Eingabedaten entwerfen, die für dieses Schema nicht gut komprimiert werden. Die "Lösung" bricht dann höchstwahrscheinlich ab, weil der Speicherplatz knapp wird.

Stattdessen gehe ich mathematisch vor. Unsere möglichen Ausgaben sind alle Listen der Länge LEN, die aus Elementen im Bereich 0..MAX bestehen. Hier beträgt die LEN 1.000.000 und unser MAX 100.000.000.

Für beliebige LEN- und MAX-Werte ist die Anzahl der zur Codierung dieses Zustands erforderlichen Bits wie folgt:

Log2 (MAX Multichoose LEN)

Wenn wir also alle Zahlen empfangen und sortiert haben, benötigen wir mindestens Log2-Bits (100.000.000 MC 1.000.000), um unser Ergebnis so zu speichern, dass alle möglichen Ausgaben eindeutig unterschieden werden können.

Dies ist ~ = 988kb . Wir haben also tatsächlich genug Platz, um unser Ergebnis zu halten. Aus dieser Sicht ist es möglich.

[Gelöschte sinnloses Streifzug jetzt, wo es bessere Beispiele gibt ...]

Beste Antwort ist hier .

Eine weitere gute Antwort ist ist hier und verwendet im Grunde die Einfügesortierung als Funktion, um die Liste um ein Element zu erweitern (puffert einige Elemente und sortiert sie vor, um das Einfügen von mehr als einem Element gleichzeitig zu ermöglichen, speichert a bisschen Zeit). Verwendet auch eine Nice-Compact-State-Codierung, Buckets mit sieben Bit-Deltas

20
davec

Angenommen, diese Aufgabe ist möglich. Unmittelbar vor der Ausgabe werden die Millionen sortierten Zahlen im Speicher angezeigt. Wie viele verschiedene Darstellungen gibt es? Da es wiederholte Zahlen geben kann, können wir nCr (select) nicht verwenden, aber es gibt eine Operation namens multichoose, die mit multisets funktioniert.

  • Es gibt 2.2e2436455 Möglichkeiten, eine Million Zahlen im Bereich von 0..99.999.999 auszuwählen.
  • Dies erfordert 8.093.7 Bits, um jede mögliche Kombination darzustellen, oder 1.011.717 Bytes.

Theoretisch ist es also möglich, eine vernünftige (ausreichende) Darstellung der sortierten Zahlenliste zu finden. Beispielsweise kann eine verrückte Darstellung eine 10-MB-Nachschlagetabelle oder Tausende von Codezeilen erfordern.

Wenn jedoch "1 MB RAM" eine Million Bytes bedeutet, ist nicht genügend Speicherplatz vorhanden. Die Tatsache, dass 5% mehr Speicher es theoretisch möglich macht, legt mir nahe, dass die Darstellung SEHR effizient und wahrscheinlich nicht vernünftig sein muss.

18
Dan

(Meine ursprüngliche Antwort war falsch. Entschuldigung für die schlechte Mathematik, siehe unten in der Pause.)

Wie wäre es damit?

Die ersten 27 Bits speichern die niedrigste Zahl, die Sie gesehen haben, dann die Differenz zur nächsten Zahl, die wie folgt codiert ist: 5 Bits zum Speichern der Anzahl der zum Speichern der Differenz verwendeten Bits, dann der Differenz. Verwenden Sie 00000, um anzuzeigen, dass Sie diese Nummer erneut gesehen haben.

Dies funktioniert, weil der durchschnittliche Unterschied zwischen den Zahlen mit dem Einfügen von mehr Zahlen abnimmt. Sie verwenden also weniger Bits, um den Unterschied zu speichern, wenn Sie mehr Zahlen hinzufügen. Ich glaube, das nennt man eine Delta-Liste.

Der schlimmste Fall, den ich mir vorstellen kann, sind alle Zahlen mit gleichem Abstand (um 100), z. Angenommen, 0 ist die erste Zahl:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit zur Rettung!

Wenn Sie sie nur sortieren müssten, wäre dieses Problem einfach. Es dauert 122k (1 Million Bits), um zu speichern, welche Zahlen Sie gesehen haben (0. Bit, wenn 0 gesehen wurde, 23. Bit, wenn 2300 gesehen wurde, usw.).

Sie lesen die Zahlen, speichern sie im Bitfeld und verschieben die Bits dann heraus, während Sie eine Zählung durchführen.

ABER du musst dich daran erinnern, wie viele du gesehen hast. Die obige Antwort auf die Unterliste hat mich dazu inspiriert, dieses Schema zu entwickeln:

Verwenden Sie statt eines Bits entweder 2 oder 27 Bits:

  • 00 bedeutet, dass Sie die Nummer nicht gesehen haben.
  • 01 bedeutet, dass Sie es einmal gesehen haben
  • 1 bedeutet, dass Sie es gesehen haben, und die nächsten 26 Bits zählen, wie oft.

Ich denke, das funktioniert: Wenn es keine Duplikate gibt, haben Sie eine 244k-Liste. Im schlimmsten Fall sehen Sie jede Zahl zweimal (wenn Sie eine Zahl dreimal sehen, wird der Rest der Liste für Sie gekürzt), dh Sie haben 50.000 mehr als einmal gesehen und 950.000 Artikel 0 oder 1 Mal gesehen.

50.000 * 27 + 950.000 * 2 = 396,7 Tsd.

Sie können weitere Verbesserungen vornehmen, wenn Sie die folgende Codierung verwenden:

0 bedeutet, dass Sie die Zahl nicht gesehen haben 10 bedeutet, dass Sie sie einmal gesehen haben 11 ist, wie Sie zählen

Dies führt im Durchschnitt zu 280,7 KB Speicherplatz.

EDIT: Mein Sonntagmorgen Mathe war falsch.

Der schlimmste Fall ist, dass wir zweimal 500.000 Zahlen sehen.

500.000 × 27 + 500.000 × 2 = 1,77 M

Die alternative Codierung führt zu einer durchschnittlichen Speicherung von

500.000 * 27 + 500.000 = 1,70 Mio.

: (

12
jfernand

Für dieses Problem gibt es eine Lösung für alle möglichen Eingaben. Betrügen.

  1. Lesen Sie m-Werte über TCP, wobei m in der Nähe des Maximums liegt, das im Speicher sortiert werden kann, möglicherweise n/4.
  2. Sortieren Sie die 250.000 (oder so) Zahlen und geben Sie sie aus.
  3. Wiederholen Sie dies für die anderen 3 Viertel.
  4. Lassen Sie den Empfänger die 4 Listen der empfangenen Nummern zusammenführen, während er sie verarbeitet. (Es ist nicht viel langsamer als die Verwendung einer einzelnen Liste.)
10
xpda

Welche Art von Computer verwenden Sie? Es hat vielleicht keinen anderen "normalen" lokalen Speicher, aber hat es zum Beispiel Video-RAM? 1 Megapixel x 32 Bit pro Pixel (beispielsweise) entspricht in etwa der erforderlichen Dateneingabegröße.

(Ich frage zum größten Teil in Erinnerung an den alten Acorn RISC PC , der VRAM 'ausleihen' könnte, um den verfügbaren System-RAM zu erweitern, wenn Sie einen Bildschirmmodus mit niedriger Auflösung oder niedriger Farbtiefe wählen!). Dies war auf einem Computer mit nur wenigen MB normalem RAM sehr nützlich.

7
DNA

Ich würde versuchen, ein Radix Tree . Wenn Sie die Daten in einem Baum speichern könnten, könnten Sie eine In-Order-Traverse durchführen, um die Daten zu übertragen.

Ich bin mir nicht sicher, ob Sie dies in 1 MB einpassen könnten, aber ich denke, es ist einen Versuch wert.

7

Eine Radix-Baum-Darstellung würde diesem Problem nahekommen, da der Radix-Baum die "Präfix-Komprimierung" ausnutzt. Es ist jedoch schwierig, sich eine Radix-Baumdarstellung vorzustellen, die einen einzelnen Knoten in einem Byte darstellen könnte - zwei liegen wahrscheinlich über der Grenze.

Unabhängig davon, wie die Daten dargestellt werden, können sie nach dem Sortieren in vorzeichenkomprimierter Form gespeichert werden, wobei die Zahlen 10, 11 und 12 beispielsweise durch 001b, 001b, 001b dargestellt werden, was ein Inkrement von 1 anzeigt von der vorherigen Nummer. Vielleicht würde 10101b dann ein Inkrement von 5 darstellen, 1101001b ein Inkrement von 9 usw.

6
Hot Licks

Es gibt 10 ^ 6 Werte in einem Bereich von 10 ^ 8, also gibt es im Durchschnitt einen Wert pro hundert Codepunkte. Speichern Sie den Abstand vom N-ten Punkt zum (N + 1) -ten. Doppelte Werte haben einen Sprung von 0. Dies bedeutet, dass der Sprung durchschnittlich knapp 7 Bit zum Speichern benötigt, sodass eine Million von ihnen problemlos in unsere 8 Millionen Bit Speicher passen.

Diese Sprünge müssen in einen Bitstrom codiert werden, beispielsweise durch Huffman-Codierung. Das Einfügen erfolgt durch Iterieren durch den Bitstrom und erneutes Schreiben nach dem neuen Wert. Ausgabe durch Durchlaufen und Ausschreiben der implizierten Werte. Aus praktischen Gründen wird es wahrscheinlich als 10 ^ 4-Listen ausgeführt, die jeweils 10 ^ 4 Codepunkte (und einen Durchschnitt von 100 Werten) abdecken.

Ein guter Huffman-Baum für zufällige Daten kann von vornherein erstellt werden, indem eine Poisson-Verteilung (Mittelwert = Varianz = 100) über die Länge der Auslassungen angenommen wird. Es können jedoch reale Statistiken über die Eingabe gespeichert und verwendet werden, um einen optimalen Baum für die Bearbeitung zu generieren pathologische Fälle.

6
Russ Williams

Ich habe einen Computer mit 1 MB RAM und keinem anderen lokalen Speicher

Eine andere Möglichkeit zu betrügen: Sie könnten stattdessen nicht-lokalen (Netzwerk-) Speicher verwenden (Ihre Frage schließt dies nicht aus) und einen Netzwerkdienst aufrufen, der einen einfachen festplattenbasierten Mergesort (oder gerade genug RAM zum Sortieren verwenden könnte In-Memory, da Sie nur 1M-Nummern akzeptieren müssen), ohne die (zugegebenermaßen äußerst genialen) bereits vorhandenen Lösungen zu benötigen.

Dies mag ein Betrug sein, aber es ist nicht klar, ob Sie nach einer Lösung für ein reales Problem suchen oder nach einem Rätsel, das zum Verbiegen der Regeln einlädt. Wenn letzteres der Fall ist, kann ein einfacher Betrug bessere Ergebnisse erzielen als ein komplexer aber "echte" Lösung (die, wie andere betont haben, nur für komprimierbare Eingaben funktionieren kann).

5
DNA

Ich denke, die Lösung besteht darin, Techniken aus der Videokodierung zu kombinieren, nämlich die diskrete Cosinustransformation. Bei digitalem Video wird jede Änderung der Helligkeit oder Farbe des Videos als reguläre Werte wie 110 112 115 116 aufgezeichnet und von der letzten abgezogen (ähnlich wie bei der Lauflängencodierung). 110 112 115 116 wird 110 2 3 1. Die Werte 2 3 1 erfordern weniger Bits als die Originale.

Nehmen wir also an, wir erstellen eine Liste der Eingabewerte, wenn sie am Socket ankommen. Wir speichern in jedem Element nicht den Wert, sondern den Offset des vorhergehenden Elements. Wir sortieren, während wir gehen, so dass die Offsets nur positiv sein werden. Der Versatz kann jedoch 8 Dezimalstellen breit sein, was 3 Bytes entspricht. Jedes Element kann nicht 3 Bytes lang sein, also müssen wir diese packen. Wir könnten das obere Bit jedes Bytes als "Fortsetzungsbit" verwenden, was anzeigt, dass das nächste Byte Teil der Zahl ist und die unteren 7 Bits jedes Bytes kombiniert werden müssen. Null ist gültig für Duplikate.

Wenn sich die Liste füllt, sollten die Zahlen näher beieinander liegen, dh es wird durchschnittlich nur 1 Byte verwendet, um den Abstand zum nächsten Wert zu bestimmen. 7 Bit Wert und 1 Bit Versatz, falls zweckmäßig, aber es kann einen Sweet Spot geben, der weniger als 8 Bit für einen "Fortsetzungs" -Wert benötigt.

Wie auch immer, ich habe experimentiert. Ich benutze einen Zufallsgenerator und kann eine Million sortierter 8-stelliger Dezimalzahlen in ungefähr 1279000 Bytes einpassen. Der durchschnittliche Abstand zwischen den einzelnen Nummern beträgt durchweg 99 ...

public class Test {
    public static void main(String[] args) throws IOException {
        // 1 million values
        int[] values = new int[1000000];

        // create random values up to 8 digits lrong
        Random random = new Random();
        for (int x=0;x<values.length;x++) {
            values[x] = random.nextInt(100000000);
        }
        Arrays.sort(values);

        ByteArrayOutputStream baos = new ByteArrayOutputStream();

        int av = 0;    
        writeCompact(baos, values[0]);     // first value
        for (int x=1;x<values.length;x++) {
            int v = values[x] - values[x-1];  // difference
            av += v;
            System.out.println(values[x] + " diff " + v);
            writeCompact(baos, v);
        }

        System.out.println("Average offset " + (av/values.length));
        System.out.println("Fits in " + baos.toByteArray().length);
    }

    public static void writeCompact(OutputStream os, long value) throws IOException {
        do {
            int b = (int) value & 0x7f;
            value = (value & 0x7fffffffffffffffl) >> 7;
            os.write(value == 0 ? b : (b | 0x80));
        } while (value != 0);
    }
}
5
slipperyseal

Google 's (schlechter) Ansatz, von HN-Thread. Speichern Sie RLE-artige Zählungen.

Ihre anfängliche Datenstruktur ist '99999999: 0' (alle Nullen, keine Zahlen gesehen) und dann können Sie sagen, dass Sie die Nummer 3.866.344 sehen, sodass Ihre Datenstruktur wie Sie '3866343: 0,1: 1,96133654: 0' wird Sie können sehen, dass die Zahlen immer zwischen der Anzahl der Null-Bits und der Anzahl der 1-Bits wechseln. Sie können also einfach davon ausgehen, dass die ungeraden Zahlen 0-Bits und die geraden Zahlen 1-Bits darstellen. Dies wird (3866343,1,96133654)

Ihr Problem scheint sich nicht auf Duplikate zu beziehen, aber nehmen wir an, sie verwenden "0: 1" für Duplikate.

Großes Problem Nr. 1: Das Einfügen von 1M ganzen Zahlen würde Ewigkeiten dauern .

Großes Problem Nr. 2: Wie bei allen einfachen Delta-Codierungslösungen können einige Distributionen nicht auf diese Weise abgedeckt werden. Zum Beispiel 1 m ganze Zahlen mit Abständen von 0: 99 (z. B. jeweils +99). Denken Sie jetzt dasselbe, aber mit zufälliger Abstand im Bereich von 0:99. (Hinweis: 99999999/1000000 = 99,99)

Der Ansatz von Google ist sowohl unwürdig (langsam) als auch falsch. Aber zu ihrer Verteidigung könnte ihr Problem etwas anders gewesen sein.

4
alecco

Wir könnten mit dem Netzwerkstapel spielen, um die Zahlen in sortierter Reihenfolge zu senden, bevor wir alle Zahlen haben. Wenn Sie 1 MB Daten senden, wird TCP/IP die Daten in 1500-Byte-Pakete aufteilen und diese streamen, um sie an das Ziel zu senden. Jedes Paket erhält eine laufende Nummer.

Das können wir von Hand machen. Kurz bevor wir unser RAM füllen, können wir sortieren, was wir haben, und die Liste an unser Ziel senden, aber um jede Zahl herum Löcher in unserer Reihenfolge lassen. Verarbeiten Sie dann die 2. Hälfte der Zahlen auf die gleiche Weise mit diesen Löchern in der Sequenz.

Der Netzwerkstapel am anderen Ende stellt den resultierenden Datenstrom in der angegebenen Reihenfolge zusammen, bevor er an die Anwendung übergeben wird.

Es verwendet das Netzwerk, um eine Zusammenführungssortierung durchzuführen. Dies ist ein totaler Hack, aber ich war inspiriert von dem anderen Networking-Hack, der zuvor aufgeführt wurde.

4
Kevin Marquette

Um das sortierte Array darzustellen, kann man einfach das erste Element und den Unterschied zwischen benachbarten Elementen speichern. Auf diese Weise haben wir es mit der Kodierung von 10 ^ 6 Elementen zu tun, die maximal 10 ^ 8 ergeben können. Nennen wir dies D. Um die Elemente von D zu codieren, kann ein Huffman-Code verwendet werden. Das Wörterbuch für den Huffman-Code kann unterwegs erstellt und das Array jedes Mal aktualisiert werden, wenn ein neues Element in das sortierte Array eingefügt wird (Einfügesortierung). Beachten Sie, dass beim Ändern des Wörterbuchs aufgrund eines neuen Elements das gesamte Array aktualisiert werden sollte, um der neuen Codierung zu entsprechen.

Die durchschnittliche Anzahl von Bits zum Codieren jedes Elements von D wird maximiert, wenn wir die gleiche Anzahl von jedem eindeutigen Element haben. Sagen Sie Elemente d1 , d2 , ..., dN in D erscheinen jeweils F mal. In diesem Fall (im schlimmsten Fall haben wir sowohl 0 als auch 10 ^ 8 in der Eingabesequenz) haben wir

sum (1 <= i <= N) F. di = 10 ^ 8

wo

sum (1 <= i <= N) F = 10 ^ 6 oder F = 10 ^ 6/N und die normalisierte Frequenz ist p = F/10 ^ = 1/N

Die durchschnittliche Anzahl von Bits ist -log2 (1/P) = log2 (N). Unter diesen Umständen sollten wir einen Fall finden, der N maximiert. Dies passiert, wenn wir fortlaufende Zahlen für di haben, beginnend mit 0, oder di = i - 1 also

10 ^ 8 = sum (1 <= i <= N) F. di = sum (1 <= i <= N) (10 ^ 6/N) (i-1) = (10 ^ 6/N) N (N - 1)/2

d.h.

N <= 201. In diesem Fall beträgt die durchschnittliche Anzahl der Bits log2 (201) = 7.6511, was bedeutet, dass zum Speichern des sortierten Arrays etwa 1 Byte pro Eingabeelement benötigt wird . Beachten Sie, dass dies nicht bedeutet, dass D im Allgemeinen nicht mehr als 201 Elemente enthalten kann. Es zeigt nur, dass wenn Elemente von D gleichmäßig verteilt sind, es nicht mehr als 201 eindeutige Werte haben kann.

3

Ich würde das Neuübertragungsverhalten von TCP ausnutzen.

  1. Erstellen Sie mit der Komponente TCP ein großes Empfangsfenster.
  2. Erhalten Sie eine bestimmte Anzahl von Paketen, ohne eine ACK für sie zu senden.
    • Verarbeiten Sie diese in Durchläufen und erstellen Sie eine (Präfix-) komprimierte Datenstruktur
    • Sende eine doppelte Bestätigung für das letzte nicht mehr benötigte Paket/warte auf das Timeout für die erneute Übertragung
    • Gehe zu 2
  3. Alle Pakete wurden angenommen

Dies setzt den Vorteil von Eimern oder mehreren Durchläufen voraus.

Wahrscheinlich durch Sortieren und Zusammenführen der Stapel/Eimer. -> Wurzelbäume

Verwenden Sie diese Technik, um die ersten 80% zu akzeptieren und zu sortieren, und lesen Sie dann die letzten 20%. Stellen Sie sicher, dass die letzten 20% keine Zahlen enthalten, die in den ersten 20% der niedrigsten Zahlen landen würden. Dann die 20% niedrigsten Nummern senden, aus dem Speicher entfernen, die restlichen 20% der neuen Nummern akzeptieren und zusammenführen. **

3
sleeplessnerd

Wenn der Eingabestream einige Male empfangen werden könnte, wäre dies viel einfacher (keine Informationen zu diesem Problem, der Idee und dem Zeit-Performance-Problem).

Dann könnten wir die Dezimalwerte zählen. Mit gezählten Werten wäre es einfach, den Ausgabestream zu erstellen. Komprimieren Sie durch Zählen der Werte. Es kommt darauf an, was sich im Eingabestrom befinden würde.

2
Baronth

Wenn der Eingabestream einige Male empfangen werden könnte, wäre dies viel einfacher (keine Informationen zu diesem Problem, zur Idee und zum Zeit-Leistungs-Problem). Dann könnten wir die Dezimalwerte zählen. Mit gezählten Werten wäre es einfach, den Ausgabestream zu erstellen. Komprimieren Sie durch Zählen der Werte. Es kommt darauf an, was sich im Eingabestrom befinden würde.

1
pbies

Sie müssen nur die Unterschiede zwischen den Zahlen in der Reihenfolge speichern und eine Codierung verwenden, um diese Folgenummern zu komprimieren. Wir haben 2 ^ 23 Bits. Wir werden es in 6-Bit-Blöcke aufteilen und das letzte Bit anzeigen lassen, ob sich die Zahl auf weitere 6 Bits erstreckt (5 Bit plus Erweiterungsblock).

Somit ist 000010 1 und 000100 2. 000001100000 ist 128. Wir betrachten nun die schlechteste Besetzung bei der Darstellung von Unterschieden in der Folge von Zahlen bis zu 10.000.000. Es kann 10.000.000/2 ^ 5 Unterschiede größer als 2 ^ 5, 10.000.000/2 ^ 10 Unterschiede größer als 2 ^ 10 und 10.000.000/2 ^ 15 Unterschiede größer als 2 ^ 15 usw. geben.

Wir addieren also, wie viele Bits benötigt werden, um unsere Sequenz darzustellen. Wir haben 1.000.000 * 6 + Aufrundung (10.000.000/2 ^ 5) * 6 + Aufrundung (10.000.000/2 ^ 10) * 6 + Aufrundung (10.000.000/2 ^ 15) * 6 + Aufrundung (10.000.000/2 ^ 20) * 4 = 7935479.

2 ^ 24 = 8388608. Da 8388608> 7935479, sollten wir leicht genug Speicher haben. Wir werden wahrscheinlich ein wenig mehr Speicher benötigen, um die Summe der Positionen zu speichern, wenn wir neue Zahlen einfügen. Wir gehen dann die Sequenz durch und suchen, wo wir unsere neue Nummer einfügen können, verringern den nächsten Unterschied, falls erforderlich, und verschieben alles danach nach rechts.

1
gersh

Wir haben 1 MB - 3 KB RAM = 2 ^ 23 - 3 * 2 ^ 13 Bits = 8388608 - 24576 = 8364032 Bits verfügbar.

Wir erhalten 10 ^ 6 Zahlen in einem Bereich von 10 ^ 8. Dies ergibt eine durchschnittliche Lücke von ~ 100 <2 ^ 7 = 128

Betrachten wir zunächst das einfachere Problem von ziemlich gleichmäßig verteilten Zahlen, wenn alle Lücken <128 sind. Dies ist einfach. Speichern Sie einfach die erste Zahl und die 7-Bit-Lücken:

(27 Bit) + 10 ^ 6 7-Bit-Lückenzahlen = 7000027 Bit erforderlich

Beachten Sie, dass wiederholte Nummern Lücken von 0 aufweisen.

Aber was ist, wenn die Lücken größer als 127 sind?

Angenommen, eine Lückengröße <127 wird direkt dargestellt, aber auf eine Lückengröße von 127 folgt eine fortlaufende 8-Bit-Codierung für die tatsächliche Lückenlänge:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

usw.

Beachten Sie, dass diese Zahlendarstellung ihre eigene Länge beschreibt, damit wir wissen, wann die nächste Lückennummer beginnt.

Mit nur kleinen Lücken <127 werden immer noch 7000027 Bits benötigt.

Es kann bis zu (10 ^ 8)/(2 ^ 7) = 781250 23-Bit-Lückenzahl geben, was zusätzliche 16 * 781,250 = 12,500,000 Bits erfordert, was zu viel ist. Wir brauchen eine kompaktere und langsam wachsende Darstellung von Lücken.

Die durchschnittliche Lückengröße beträgt 100, wenn wir sie also als [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] neu anordnen und indizieren Mit einer dichten binären Fibonacci-Basiscodierung ohne Nullenpaare (z. B. 11011 = 8 + 5 + 2 + 1 = 16) mit durch '00' begrenzten Zahlen können wir die Lückendarstellung meines Erachtens kurz genug halten, aber es ist erforderlich mehr Analyse.

1
Toby Kelsey

Das Sortieren ist hier ein sekundäres Problem. Wie bereits erwähnt, ist es schwierig, nur die ganzen Zahlen zu speichern, und kann nicht für alle Eingaben verwendet werden, da 27 Bit pro Zahl erforderlich wären.

Ich gehe davon aus, dass nur die Unterschiede zwischen den aufeinanderfolgenden (sortierten) Ganzzahlen gespeichert werden, da diese höchstwahrscheinlich klein sein werden. Verwenden Sie dann ein Komprimierungsschema, z. mit 2 zusätzlichen Bits pro Eingangsnummer, um zu codieren, in wie vielen Bits die Nummer gespeichert ist. So etwas wie:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

Es sollte möglich sein, eine angemessene Anzahl möglicher Eingabelisten innerhalb der gegebenen Speicherbeschränkung zu speichern. Die Mathematik, wie man das Komprimierungsschema auswählt, damit es mit der maximalen Anzahl von Eingaben funktioniert, ist mir ein Rätsel.

Ich hoffe, Sie können domänenspezifisches Wissen über Ihre Eingabe ausnutzen, um auf dieser Grundlage ein ausreichend gutes ganzzahliges Komprimierungsschema zu finden.

Und dann sortieren Sie diese sortierte Liste nach dem Einfügen, während Sie Daten empfangen.

1

Wenn wir nichts über diese Zahlen wissen, sind wir durch die folgenden Einschränkungen eingeschränkt:

  • wir müssen alle Zahlen laden, bevor wir sie sortieren können.
  • die Zahlenmenge ist nicht komprimierbar.

Wenn diese Annahmen zutreffen, können Sie Ihre Aufgabe nicht ausführen, da Sie mindestens 26.575.425 Speicherbits (3.321.929 Byte) benötigen.

Was können Sie uns über Ihre Daten erzählen?

1
Yves Daoust

Wir streben nun eine tatsächliche Lösung an, die alle möglichen Eingabefälle im 8-stelligen Bereich mit nur 1 MB RAM abdeckt. HINWEIS: In Arbeit, morgen geht es weiter. Unter Verwendung der arithmetischen Codierung der Deltas der sortierten Ints würde der schlechteste Fall für 1M sortierte Ints etwa 7 Bit pro Eintrag kosten (da 99999999/1000000 99 ist und log2 (99) fast 7 Bit ist).

Sie müssen jedoch die 1-m-Ganzzahlen sortieren, um 7 oder 8 Bits zu erhalten! Kürzere Reihen hätten größere Deltas, daher mehr Bits pro Element.

Ich arbeite daran, so viele wie möglich zu nehmen und (fast) vor Ort zu komprimieren. Für den ersten Stapel mit fast 250 KByte werden bestenfalls 9 Bit benötigt. Das Ergebnis würde also ungefähr 275 KB dauern. Wiederholen Sie dies einige Male mit dem verbleibenden freien Speicher. Dann dekomprimieren, zusammenführen und komprimieren Sie diese komprimierten Blöcke. Das ist ziemlich schwer, aber möglich. Ich denke.

Die zusammengeführten Listen näherten sich immer mehr dem Ziel von 7 Bit pro Ganzzahl. Aber ich weiß nicht, wie viele Iterationen die Zusammenführungsschleife benötigen würde. Vielleicht 3.

Die Ungenauigkeit der Implementierung der arithmetischen Codierung könnte dies jedoch unmöglich machen. Wenn dieses Problem überhaupt möglich ist, wäre es extrem eng.

Irgendwelche Freiwilligen?

1
alecco

Der Trick besteht darin, den Algorithmuszustand, der ein ganzzahliger Mehrfachsatz ist, als komprimierten Strom von "Inkrementzähler" = "+" und "Ausgangszähler" = "!" Figuren. Beispielsweise würde die Menge {0,3,3,4} als "! +++ !! +!" Dargestellt, gefolgt von einer beliebigen Anzahl von "+" - Zeichen. Um den Mehrfachsatz zu ändern, werden die Zeichen gestreamt, wobei jeweils nur eine konstante Menge dekomprimiert wird, und Änderungen werden vorgenommen, bevor sie in komprimierter Form zurückgestreamt werden.

Details

Wir wissen, dass es im letzten Satz genau 10 ^ 6 Zahlen gibt, also gibt es höchstens 10 ^ 6 "!" Figuren. Wir wissen auch, dass unser Bereich die Größe 10 ^ 8 hat, was bedeutet, dass es höchstens 10 ^ 8 "+" Zeichen gibt. Die Anzahl der Möglichkeiten, wie wir 10 ^ 6 "!" - Werte unter 10 ^ 8 "+" - Werten anordnen können, ist (10^8 + 10^6) choose 10^6, und daher erfordert die Angabe einer bestimmten Anordnung ~ 0,965 MiB `von Daten. Das passt gut zusammen.

Wir können jeden Charakter als unabhängig behandeln, ohne unsere Quote zu überschreiten. Es gibt genau 100 Mal mehr "+" Zeichen als "!" Zeichen, was sich auf 100: 1 vereinfacht, wenn wir vergessen, dass jedes Zeichen abhängig ist. Eine Wahrscheinlichkeit von 100: 101 entspricht ~ 0,08 Bits pro Zeichen , für eine nahezu identische Summe von ~ 0,965 MiB (das Ignorieren der Abhängigkeit verursacht nur Kosten von ~) 12 Bits in diesem Fall!).

Die einfachste Technik zum Speichern unabhängiger Zeichen mit bekannter vorheriger Wahrscheinlichkeit ist Huffman-Codierung . Beachten Sie, dass wir einen unpraktisch großen Baum benötigen (Ein Huffman-Baum für Blöcke mit 10 Zeichen verursacht durchschnittliche Kosten pro Block von ca. 2,4 Bit für insgesamt ~ 2,9 Mib. Ein Huffman-Baum für Blöcke mit 20 Zeichen verursacht durchschnittliche Kosten pro Block von ungefähr 3 Bits, was insgesamt ~ 1,8 MiB entspricht. Wir werden wahrscheinlich einen Block mit einer Größe in der Größenordnung von einhundert benötigen, was bedeutet, dass mehr Knoten in unserem Baum vorhanden sind, als die gesamte jemals existierende Computerausrüstung speichern kann. ). Allerdings ist ROM dem Problem entsprechend technisch "frei", und praktische Lösungen, die die Regelmäßigkeit im Baum ausnutzen, sehen im Wesentlichen gleich aus.

Pseudocode

  • Habe einen ausreichend großen Huffman-Baum (oder ähnliche blockweise Komprimierungsdaten) im ROM gespeichert
  • Beginnen Sie mit einer komprimierten Zeichenfolge von 10 ^ 8 "+" Zeichen.
  • Um die Zahl N einzufügen, streamen Sie die komprimierte Zeichenfolge aus, bis N "+" Zeichen verstrichen sind, und fügen Sie dann ein "!" Übertragen Sie die neu komprimierte Zeichenfolge währenddessen wieder auf die vorherige Zeichenfolge, und halten Sie dabei die Anzahl der gepufferten Blöcke konstant, um Über- und Unterläufe zu vermeiden.
  • Eine Million Mal wiederholen: [Eingabe, Stream dekomprimieren> Einfügen> Komprimieren], dann dekomprimieren, um auszugeben
1
Craig Gidney

Führen Sie diese Schritte aus, während Sie den Stream empfangen.

1. Stellen Sie eine angemessene Blockgröße ein

Pseudocode-Idee:

  1. Der erste Schritt wäre, alle Duplikate zu finden und sie mit ihrer Anzahl in ein Wörterbuch zu schreiben und sie zu entfernen.
  2. Der dritte Schritt wäre, eine Zahl, die in der Reihenfolge ihrer algorithmischen Schritte existiert, zu platzieren und sie in speziellen Wörterbüchern mit der ersten Zahl und ihrem Schritt wie n, n + 1 ..., n + 2, 2n, 2n + 1 zu platzieren. 2n + 2 ...
  3. Beginnen Sie, einige sinnvolle Zahlenbereiche wie etwa alle 1000 oder je 10000 zu komprimieren, damit sich die verbleibenden Zahlen, die scheinbar seltener vorkommen, wiederholen.
  4. Dekomprimieren Sie diesen Bereich, wenn eine Zahl gefunden wurde, und fügen Sie sie dem Bereich hinzu, und lassen Sie ihn noch eine Weile unkomprimiert.
  5. Andernfalls fügen Sie einfach diese Nummer zu einem Byte hinzu [chunkSize]

Führen Sie die ersten 4 Schritte aus, während Sie den Stream empfangen. Der letzte Schritt wäre, entweder einen Fehler zu machen, wenn Sie den Arbeitsspeicher überschritten haben, oder das Ergebnis auszugeben, sobald alle Daten gesammelt sind, indem Sie mit dem Sortieren der Bereiche beginnen und die Ergebnisse der Reihe nach ausspucken und diejenigen dekomprimieren, die dekomprimiert werden müssen, und sie dann zu sortieren du kommst zu ihnen.

0
RetroCoder