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

Die Liste der Zahlen 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 abziehen muss. Ich habe bereits Code zum Ansteuern des Ethernet-Ports und zum Behandeln 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

Es gibt einen ziemlich hinterhältigen Trick, der hier bisher 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, die folgenden schrecklichen Dinge zu tun, die unter keinen Umständen von irgendjemandem versucht werden sollten: Verwenden Sie den Netzwerkverkehr zum Speichern von Daten. Und nein, ich meine nicht NAS.

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

• Nehmen Sie zuerst 2 Variablen: COUNTERund VALUE.
• Stellen Sie zuerst alle Register auf 0;
• Jedes Mal, wenn Sie eine Ganzzahl erhalten I, erhöhen Sie diese COUNTERund setzen Sie sie VALUEauf max(VALUE, I);
• Senden Sie dann ein ICMP-Echoanforderungspaket mit Datensatz Ian den Router. Löschen Iund wiederholen.
• Jedes Mal, wenn Sie das zurückgegebene ICMP-Paket empfangen, extrahieren Sie einfach die Ganzzahl und senden sie in einer anderen Echoanforderung erneut aus. Dies erzeugt eine große Anzahl von ICMP-Anforderungen, die mit den ganzen Zahlen vorwärts und rückwärts laufen.

Sobald dies COUNTERerreicht ist 1000000, haben Sie alle Werte im unaufhörlichen Strom von ICMP-Anforderungen gespeichert und enthalten VALUEjetzt die maximale Ganzzahl. Wähle welche aus threshold T >> 1000000. Auf COUNTERNull setzen. Inkrementieren COUNTERund senden Sie die enthaltene Ganzzahl jedes Mal, wenn Sie ein ICMP-Paket empfangen I, in einer anderen Echoanforderung zurück, es sei denn I=VALUE, in diesem Fall senden Sie sie für die sortierten Ganzzahlen an das Ziel. Einmal COUNTER=T, Abnahme VALUEdurch 1, Reset COUNTERauf Null und wiederholen. Sobald VALUESie Null erreicht haben, sollten Sie alle Ganzzahlen in der Reihenfolge vom größten zum kleinsten zum Ziel übertragen und nur etwa 47 Bit RAM für die beiden persistenten Variablen verwendet haben (und welche kleine Menge Sie auch für die temporären Werte benötigen).

Ich weiß, dass dies schrecklich ist, 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 entsetzen.

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

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

Redaktion: 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, war 1011732, und wählte die Puffergröße 1013000willkürlich aus.

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 benötigen diese beiden Arrays 1045000 Byte Speicherplatz. Damit bleiben 1048576 - 1045000 - 2 × 1024 = 1528 Bytes für verbleibende Variablen und Stapelspeicher.

Auf meinem Xeon W3520 läuft es in ungefähr 23 Sekunden. Sie können überprüfen, ob das Programm mit dem folgenden Python-Skript unter der Annahme eines Programmnamens von funktioniert 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 Reihe von Beiträgen:

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

Bitte beachten Sie die erste richtige Antwort oder die spätere Antwort mit arithmetischer Codierung . Im Folgenden finden Sie vielleicht etwas Spaß, aber keine 100% kugelsichere Lösung.

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

Stufe 1: Anfängliche Datenstruktur, grober Komprimierungsansatz, grundlegende Ergebnisse

Lassen Sie uns ein paar einfache Berechnungen anstellen: Wir haben zunächst 1 MB (1048576 Byte) RAM zur Verfügung, um 10 ^ 6 8-stellige Dezimalzahlen zu speichern. [0; 99999999]. Zum Speichern einer Nummer werden also 27 Bits benötigt (unter der Annahme, dass vorzeichenlose Nummern verwendet werden). Zum Speichern eines Rohdatenstroms werden daher ~ 3,5 MB RAM benötigt. Jemand hat bereits gesagt, dass es 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 Komprimierungsfaktor von 0,29 oder höher zu komprimieren und ordnungsgemäß zu sortieren.

Lassen Sie uns zuerst das Komprimierungsproblem lösen. Es sind bereits einige relevante Tests verfügbar:

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

"Ich habe einen Test durchgeführt, um eine Million aufeinanderfolgende Ganzzahlen mit verschiedenen Komprimierungsformen zu komprimieren. Die Ergebnisse sind wie folgt:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Es sieht so aus, als ob LZMA ( Lempel-Ziv-Markov-Kettenalgorithmus ) eine gute Wahl ist, 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 Zahlen vorsortiert und komprimierte Buckets (dynamische Größe) als temporärer Speicher verwendet werden
2. Es ist einfacher, mit vorsortierten Daten einen besseren Komprimierungsfaktor zu erzielen, daher gibt es für jeden Bucket einen statischen Puffer (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 durchgeführt werden 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

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

Siehe den PoC-Code unten (bitte beachten Sie, dass es sich nur um eine Demo handelt, zum Kompilieren wird LZMA-Java 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 Sequenz (es wird ein Bucket verwendet) wird Folgendes erzeugt:

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

BEARBEITEN

Fazit:

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

Stufe 2: Verbesserte Komprimierung, endgültiger Abschluss

Wie bereits im vorherigen Abschnitt erwähnt, kann jede geeignete Kompressionstechnik verwendet werden. Lassen Sie uns also LZMA zugunsten eines einfacheren und besseren (wenn möglich) Ansatzes loswerden. Es gibt viele gute Lösungen, einschließlich arithmetischer Codierung , Radix-Baum usw.

Wie auch immer, ein einfaches, aber nützliches Codierungsschema ist anschaulicher als eine weitere externe Bibliothek und bietet einen raffinierten Algorithmus. Die eigentliche Lösung ist ziemlich einfach: Da es Buckets mit teilweise sortierten Daten gibt, können Deltas anstelle von Zahlen verwendet werden.

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 . Die Implementierungen von BinaryInput und BinaryOutput finden Sie hier

Schlußfolgerung

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

Es hat Spaß gemacht, einige Zeit mit dieser Aufgabe zu verbringen. Übrigens gibt es unten viele interessante Antworten. Vielen Dank für Ihre Aufmerksamkeit und viel Spaß beim Codieren.

Eine Lösung ist nur aufgrund des Unterschieds zwischen 1 Megabyte und 1 Million Bytes möglich. Es gibt ungefähr 2 Möglichkeiten 8093729.5 verschiedene Möglichkeiten, 1 Million 8-stellige Zahlen mit erlaubten Duplikaten auszuwählen und unwichtig zu bestellen, sodass eine Maschine mit nur 1 Million Bytes RAM nicht über genügend Zustände verfügt, um alle Möglichkeiten darzustellen. 1M (weniger 2k für TCP / IP) ist jedoch 1022 * 1024 * 8 = 8372224 Bit, sodass eine Lösung möglich ist.

Teil 1, erste Lösung

Dieser Ansatz benötigt etwas mehr als 1 Million, ich werde ihn verfeinern, um später in 1 Million zu passen.

Ich werde eine kompakte sortierte Liste von Zahlen im Bereich von 0 bis 99999999 als Folge von Unterlisten von 7-Bit-Zahlen speichern. 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-Unterlisten-Header, gefolgt von einem Unterlisten-Body. Der Unterlistenkörper nimmt 7 Bits pro Unterlisteneintrag auf. Die Unterlisten sind alle miteinander verkettet, und das Format ermöglicht es zu erkennen, wo eine Unterliste endet und die nächste beginnt. Der Gesamtspeicher, der für eine vollständig aufgefüllte Liste erforderlich ist, beträgt 2 * 781250 + 7 * 1000000 = 8562500 Bit, was ungefähr 1,021 MByte entspricht.

Die 4 möglichen Unterlisten-Header-Werte sind:

00 Leere Unterliste, nichts folgt.

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 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. Zum Beispiel 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 zwei oder mehr Wiederholungen einer einzelnen Zahl. 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 Zahlen mehr zu lesen sind, und gehen Sie dann die kompakte Liste erneut durch, um die Ausgabe zu generieren.

Die folgende Zeile zeigt den Speicher unmittelbar vor dem Start des Listenzusammenführungsvorgangs. Die "O" sind der Bereich, der die sortierten 32-Bit-Ganzzahlen enthält. Die "X" sind die Region, in der sich die alte Kompaktliste befindet. 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 am linken "O" und am linken "X" zu lesen und beginnt am linken "=" zu schreiben. Der Schreibzeiger fängt den Lesezeiger der kompakten Liste erst 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 zusätzlicher Platz für die vorhanden ist 7-Bit-Einträge für die neuen Nummern.

Teil 2, stopft es in 1M

Um die obige Lösung in 1M zusammenzufassen, muss ich das kompakte Listenformat etwas kompakter gestalten. Ich werde einen der Unterlistentypen loswerden, so dass es nur 3 verschiedene mögliche Unterlisten-Header-Werte gibt. Dann kann ich "00", "01" und "1" als Unterlisten-Header-Werte verwenden und einige 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. Zum Beispiel 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 Zahl.

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-Unterlisten-Header, gefolgt von 3 Einträgen, z. B. "C [17] [101] [58]". Dies kann nicht Teil einer gültigen Unterliste vom Typ C 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 Unterliste vom Typ C. 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 übrig, 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 als nicht 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 ausgeliehene Bits auf 2. Bei jedem Schreibvorgang, bei dem der Zähler für ausgeliehene Bits ungleich Null ist, wird er für jedes geschriebene Bit und dekrementiert "10" wird geschrieben, wenn der Zähler Null erreicht. Die nächsten 2 geschriebenen Bits werden also in die Steckplätze A und B geschrieben, und dann wird die "10" am Ende abgelegt.

Mit 3 Unterlisten-Header-Werten, die durch "00", "01" und "1" dargestellt werden, kann ich dem beliebtesten Unterlistentyp "1" zuweisen. Ich benötige eine kleine Tabelle, um die Werte der Unterlisten-Header den Unterlistentypen zuzuordnen, und ich benötige einen Vorkommenszähler für jeden Unterlistentyp, damit ich weiß, was die beste Zuordnung der Unterlisten-Header ist.

Die minimale Darstellung einer vollständig ausgefüllten kompakten Liste im schlimmsten Fall tritt auf, wenn alle Unterlistentypen gleich 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, dh 8302112 Bit oder 1037764 Byte.

1M minus 2k für TCP / IP-Status und Puffer beträgt 1022 * 1024 = 1046528 Bytes, sodass ich 8764 Bytes zum Spielen habe.

Aber was ist mit dem Prozess der Änderung der Zuordnung der Unterlisten-Header? In der Speicherkarte unten ist "Z" zufälliger Overhead, "=" ist freier Speicherplatz, "X" ist die kompakte Liste.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Dann muss ich es nach rechts rangieren:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Beim Ändern der Headerzuordnung ändern sich bis zu 1/3 der Header der Unterliste von 1-Bit auf 2-Bit. Im schlimmsten Fall stehen diese alle an der Spitze der Liste, sodass ich vor dem Start mindestens 781250/3 Bit freien Speicherplatz benötige, was mich zu den Speicheranforderungen der vorherigen Version der Kompaktliste zurückführt: (

Um dies zu umgehen, werde ich die 781250-Unterlisten in 10 Unterlistengruppen mit jeweils 78125-Unterlisten aufteilen. Jede Gruppe verfügt über eine eigene unabhängige Unterlisten-Headerzuordnung. Verwenden Sie die Buchstaben A bis J für die Gruppen:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Jede Unterlistengruppe wird während einer Änderung der Zuordnung der Unterlisten-Header verkleinert oder bleibt 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 temporäre Erweiterung einer Unterlistengruppe im schlimmsten Fall während einer Zuordnungsänderung beträgt 78125/3 = 26042 Bit unter 4 KB. Wenn ich 4 KB plus 1037764 Bytes für eine vollständig aufgefüllte kompakte Liste zulasse, bleiben mir 8764 - 4096 = 4668 Bytes für die "Z" in der Speicherzuordnung.

Das sollte für die 10 Unterlisten-Header-Zuordnungstabellen, 30 Unterlisten-Header-Auftrittszählungen und die anderen wenigen Zähler, Zeiger und kleinen Puffer, die ich benötige, und den Speicherplatz, den ich ohne es zu bemerken verwendet habe, wie Stapelspeicher für Rückrufadressen von Funktionsaufrufen und lokale Variablen.

Teil 3, wie lange würde es dauern, um zu laufen?

Bei einer leeren kompakten Liste wird der 1-Bit-Listenkopf für eine leere Unterliste verwendet, und die Startgröß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 benötigt werden, um oben im Listenpuffer platziert und dann sortiert und zusammengeführt zu werden. Im schlimmsten Fall führt das Ändern der Header-Zuordnung der Unterliste zu einer Speicherplatznutzung von 2 * 781250 + 7 * Einträgen - 781250/3 Bit.

Mit der Richtlinie, die Zuordnung von Unterlisten-Headern nach jeder fünften Zusammenführung zu ändern, sobald mindestens 800000 Nummern in der Liste enthalten sind, würde ein Worst-Case-Lauf insgesamt etwa 30 Millionen Lese- und Schreibaktivitäten für kompakte Listen umfassen.

Quelle:

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

Gilmanovs Antwort ist in seinen Annahmen sehr falsch. Es beginnt zu spekulieren, basierend auf einem sinnlosen Maß von einer Million aufeinanderfolgender Ganzzahlen. Das heißt keine Lücken. Diese zufälligen Lücken, so 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, komprimieren Sie sie mit 7-Zip , xz und beliebigem LZMA. Das Ergebnis ist über 1,5 MB. Die Prämisse oben ist die Komprimierung von fortlaufenden Zahlen. Selbst die Delta-Codierung beträgt mehr als 1,1 MB . Dabei spielt es mehr als 100 MB RAM für die Komprimierung. Selbst die komprimierten Ganzzahlen passen nicht zum Problem, und die RAM-Nutzung zur Laufzeit spielt keine Rolle .

Es macht mich traurig, wie die Leute nur hübsche Grafiken und Rationalisierungen unterstützen.

#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);

}

Komprimieren Sie jetzt 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

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

Eine Möglichkeit, darüber nachzudenken, besteht darin, zu bemerken, dass dies eine Bijektion des Problems ist, 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, wenn Sie ein Raster mit einer Breite von 1.000.000 und einer Höhe von 100.000.000 haben, wie viele kürzeste Pfade von links unten nach rechts oben gibt es? Für kürzeste Wege müssen Sie sich natürlich immer nur nach rechts oder oben bewegen (wenn Sie sich nach unten oder links bewegen, würden Sie den zuvor erreichten Fortschritt rückgängig machen). Beachten Sie Folgendes, um zu sehen, wie dies eine Bijektion unseres Problems der Nummernsortierung ist:

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

Wenn sich der Pfad also einfach bis zum Ende nach rechts bewegt, springt er 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 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 somit 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 stehen für 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 Bit> 8093700 Bit

Es scheint also, dass wir zumindest genug Platz haben, um das Ergebnis zu speichern! Jetzt ist das interessante Bit natürlich das Sortieren, während die Zahlen einströmen. Wir sind uns nicht sicher, ob der beste Ansatz dafür gegeben ist, da noch 294908 Bits übrig sind. Ich stelle mir eine interessante Technik vor, bei jedem Punkt anzunehmen, dass dies die gesamte Bestellung ist, den Code für diese Bestellung zu finden und dann, wenn Sie eine neue Nummer erhalten, zurück zu gehen und den vorherigen Code zu aktualisieren. Handwelle Handwelle.

Meine Vorschläge hier haben viel mit Dans Lösung zu tun

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

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

Bei allen gängigen Antworten wird davon ausgegangen, dass sie die Komprimierung so effektiv anwenden können, dass sie zusätzlichen Speicherplatz bietet. Tatsächlich ein Teil des zusätzlichen Speicherplatzes, der groß genug ist, um einen Teil ihrer teilweise ausgefüllten Liste in unkomprimierter Form aufzunehmen und ihnen die Durchführung ihrer Sortiervorgänge zu ermöglichen. Dies ist nur eine schlechte Annahme.

Für eine solche Lösung kann jeder, der weiß, wie er seine Komprimierung durchführt, einige Eingabedaten entwerfen, die für dieses Schema nicht gut komprimiert werden, und die "Lösung" wird höchstwahrscheinlich aufgrund von Platzmangel kaputt gehen.

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 unsere MAX 100.000.000.

Für beliebige LEN und MAX beträgt die Anzahl der Bits, die zum Codieren dieses Zustands benötigt werden:

Log2 (MAX Multichoose LEN)

Nach Abschluss des Empfangs und der Sortierung benötigen wir für unsere Zahlen 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 ~ = 988 kb . Wir haben also tatsächlich genug Platz, um unser Ergebnis zu halten. Aus dieser Sicht ist es möglich.

[Das sinnlose Wandern wurde gelöscht, da es bessere Beispiele gibt ...]

Die beste Antwort ist hier .

Eine andere gute Antwort ist hier und verwendet im Grunde die Einfügesortierung als Funktion, um die Liste um ein Element zu erweitern (puffert einige Elemente und Vorsortierungen, um das Einfügen von mehr als einem Element gleichzeitig zu ermöglichen, spart etwas Zeit). verwendet auch eine schöne kompakte Zustandscodierung, Buckets mit sieben Bit-Deltas

Angenommen, diese Aufgabe ist möglich. Kurz vor der Ausgabe wird eine speicherinterne Darstellung der Millionen sortierten Zahlen angezeigt. Wie viele verschiedene solcher Darstellungen gibt es? Da es möglicherweise wiederholte Zahlen gibt, können wir nCr (wählen) nicht verwenden, aber es gibt eine Operation namens Multichoose, die für Multisets funktioniert .

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

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

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

(Meine ursprüngliche Antwort war falsch, entschuldigen Sie die schlechte Mathematik, siehe unten die Pause.)

Wie wäre es damit?

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

Dies funktioniert, da mit dem Einfügen von mehr Zahlen die durchschnittliche Differenz zwischen Zahlen abnimmt, sodass Sie weniger Bits verwenden, um die Differenz 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 gleichmäßigem Abstand (um 100), z. B. 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 Bit), um zu speichern, welche Zahlen Sie gesehen haben (0. Bit an, wenn 0 gesehen wurde, 2300. Bit an, wenn 2300 gesehen wurde usw.).

Sie lesen die Zahlen, speichern sie im Bitfeld und verschieben die Bits, 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 zu diesem Schema inspiriert:

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 geben an, 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, verkürzt dies den Rest der Liste für Sie), dh Sie haben 50.000 mehr als einmal gesehen und 950.000 Elemente 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 bedeutet, dass Sie zählen

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

EDIT: Meine Mathematik am Sonntagmorgen war falsch.

Der schlimmste Fall ist, dass wir zweimal 500.000 Zahlen sehen, also wird die Mathematik:

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 M.

: (

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

1. Lesen Sie m-Werte über TCP, wobei m nahe dem Maximum 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 Nummernlisten, die er erhalten hat, zusammenführen, während er sie verarbeitet. (Es ist nicht viel langsamer als die Verwendung einer einzelnen Liste.)

Ich würde einen Radix-Baum ausprobieren . Wenn Sie die Daten in einem Baum speichern könnten, könnten Sie eine Durchlaufreihenfolge durchführen, um die Daten zu übertragen.

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

Welche Art von Computer verwenden Sie? Es hat möglicherweise keinen anderen "normalen" lokalen Speicher, aber hat es zum Beispiel Video-RAM? 1 Megapixel x 32 Bit pro Pixel (sagen wir) entspricht ziemlich genau Ihrer erforderlichen Dateneingabegröße.

(Ich frage weitgehend im Speicher des alten Acorn RISC-PCs , der VRAM "ausleihen" könnte, um den verfügbaren System-RAM zu erweitern, wenn Sie einen Bildschirmmodus mit niedriger Auflösung oder geringer Farbtiefe wählen!). Dies war auf einem Computer mit nur wenigen MB normalem RAM ziemlich nützlich.

Eine Radixbaumdarstellung würde diesem Problem nahe kommen, da der Radixbaum die "Präfixkomprimierung" ausnutzt. Es ist jedoch schwierig, sich eine Radix-Baumdarstellung vorzustellen, die einen einzelnen Knoten in einem Byte darstellen könnte - zwei sind wahrscheinlich ungefähr die Grenze.

Unabhängig davon, wie die Daten dargestellt werden, können sie nach dem Sortieren in präfixkomprimierter 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 dann 10101b ein Inkrement von 5 darstellen, 1101001b ein Inkrement von 9 usw.

Es gibt 10 ^ 6 Werte in einem Bereich von 10 ^ 8, also gibt es durchschnittlich 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 davon problemlos in unsere 8 Millionen Speicherbits passen.

Diese Sprünge müssen in einen Bitstrom codiert werden, beispielsweise durch Huffman-Codierung. Das Einfügen erfolgt durch Durchlaufen des Bitstroms und erneutes Schreiben nach dem neuen Wert. Ausgabe durch Durchlaufen und Ausschreiben der implizierten Werte. Aus praktischen Gründen möchte dies wahrscheinlich beispielsweise als 10 ^ 4-Listen mit 10 ^ 4 Codepunkten (und durchschnittlich 100 Werten) durchgeführt werden.

Ein guter Huffman-Baum für zufällige Daten kann a priori erstellt werden, indem eine Poisson-Verteilung (Mittelwert = Varianz = 100) über die Länge der Sprünge angenommen wird. Es können jedoch echte Statistiken über die Eingabe geführt und verwendet werden, um einen optimalen Baum für die Behandlung zu generieren pathologische Fälle.

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

Eine andere Möglichkeit zum Betrügen: Sie könnten stattdessen nicht lokalen (vernetzten) Speicher verwenden (Ihre Frage schließt dies nicht aus) und einen vernetzten Dienst aufrufen, der eine einfache festplattenbasierte Zusammenführung verwenden könnte (oder gerade genug RAM, um den Arbeitsspeicher zu sortieren, da Sie müssen nur 1M-Nummern akzeptieren), ohne die bereits zugegebenermaßen (zugegebenermaßen äußerst genialen) 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 Biegen 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).

Ich denke, die Lösung besteht darin, Techniken aus der Videokodierung zu kombinieren, nämlich die diskrete Kosinustransformation. Bei digitalen Videos wird das Ändern der Helligkeit oder Farbe von Videos als reguläre Werte wie 110 112 115 116 vom letzten subtrahiert (ähnlich wie bei der Lauflängencodierung). 110 112 115 116 wird zu 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, sobald sie am Socket ankommen. Wir speichern in jedem Element nicht den Wert, sondern den Versatz des vorherigen Elements. Wir sortieren, während wir gehen, also werden die Offsets nur positiv sein. Der Versatz kann jedoch 8 Dezimalstellen breit sein, was in 3 Bytes passt. Jedes Element kann nicht 3 Bytes lang sein, daher müssen wir diese packen. Wir könnten das oberste 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 gilt für Duplikate.

Wenn die Liste voll ist, sollten die Zahlen näher beieinander liegen, was bedeutet, dass im Durchschnitt nur 1 Byte verwendet wird, um den Abstand zum nächsten Wert zu bestimmen. 7 Bit Wert und 1 Bit Offset, wenn dies zweckmäßig ist, aber es kann einen Sweet Spot geben, der weniger als 8 Bit für einen "Weiter" -Wert erfordert.

Wie auch immer, ich habe ein Experiment gemacht. Ich benutze einen Zufallszahlengenerator und kann eine Million sortierter 8-stelliger Dezimalzahlen in ungefähr 1279000 Bytes einpassen. Der durchschnittliche Abstand zwischen jeder Zahl 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);
    }
}

Wir könnten mit dem Netzwerkstapel spielen, um die Nummern in sortierter Reihenfolge zu senden, bevor wir alle Nummern haben. Wenn Sie 1 Million Daten senden, zerlegt TCP / IP diese in 1500-Byte-Pakete und überträgt sie an das Ziel. Jedes Paket erhält eine Sequenznummer.

Wir können dies von Hand tun. Kurz bevor wir unseren 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 Sequenz lassen. Verarbeiten Sie dann die 2. Hälfte der Zahlen auf die gleiche Weise, indem Sie diese Löcher in der Sequenz verwenden.

Der Netzwerkstapel am anderen Ende stellt den resultierenden Datenstrom in der Reihenfolge seiner 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 wurde von dem anderen zuvor aufgeführten Networking-Hack inspiriert.

Googles (schlechter) Ansatz aus dem HN-Thread. Speichern Sie RLE-Zählungen.

Ihre anfängliche Datenstruktur ist '99999999: 0' (alle Nullen, haben keine Zahlen gesehen). Nehmen wir an, Sie sehen die Zahl 3.866.344, sodass Ihre Datenstruktur wie Sie zu '3866343: 0,1: 1,96133654: 0' wird Sie können sehen, dass die Zahlen immer zwischen der Anzahl der Nullbits 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 keine Duplikate abzudecken, aber nehmen wir an, sie verwenden "0: 1" für Duplikate.

Großes Problem Nr. 1: Einfügungen für 1 Million Ganzzahlen würden ewig dauern .

Großes Problem Nr. 2: Wie bei allen einfachen Delta-Codierungslösungen können einige Distributionen auf diese Weise nicht abgedeckt werden. Zum Beispiel 1m ganze Zahlen mit Abständen von 0:99 (zB jeweils +99). Denken Sie jetzt das gleiche, aber mit zufälliger Entfernung 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.

Um das sortierte Array darzustellen, kann man einfach das erste Element und die Differenz zwischen benachbarten Elementen speichern. Auf diese Weise geht es darum, 10 ^ 6 Elemente zu codieren, die höchstens 10 ^ 8 ergeben können. Lassen Sie uns dies nennen D . Um die Elemente von D zu codieren, kann man einen Huffman-Code verwenden . 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 das gesamte Array aktualisiert werden sollte, wenn sich das Wörterbuch aufgrund eines neuen Elements ändert, 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 wir , die 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

Summe (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 geschieht, wenn wir fortlaufende Zahlen für di haben, die bei 0 beginnen, oder wenn di = i -1 ist

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

dh

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

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

1. Lassen Sie die TCP-Komponente ein großes Empfangsfenster erstellen.
2. Empfangen Sie eine bestimmte Anzahl von Paketen, ohne eine ACK für sie zu senden.
   • Verarbeiten Sie diese in Durchgängen, um eine (Präfix-) komprimierte Datenstruktur zu erstellen
   • Senden Sie eine doppelte Bestätigung für das letzte Paket, das nicht mehr benötigt wird, und warten Sie auf das Zeitlimit für die erneute Übertragung
   • Gehe zu 2
3. Alle Pakete wurden akzeptiert

Dies setzt einen Vorteil von Eimern oder Mehrfachdurchläufen voraus.

Wahrscheinlich durch Sortieren der Chargen / Eimer und Zusammenführen. -> Radixbä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. Senden Sie dann die niedrigsten 20% -Nummern, entfernen Sie sie aus dem Speicher, akzeptieren Sie die verbleibenden 20% der neuen Nummern und führen Sie sie zusammen. **

Hier ist eine allgemeine Lösung für diese Art von Problem:

Allgemeines Verfahren

Der Ansatz ist wie folgt. Der Algorithmus arbeitet mit einem einzelnen Puffer von 32-Bit-Wörtern. Es führt die folgende Prozedur in einer Schleife aus:

• Wir beginnen mit einem Puffer, der mit komprimierten Daten aus der letzten Iteration gefüllt ist. Der Puffer sieht so aus

  |compressed sorted|empty|

• Berechnen Sie die maximale Anzahl von Zahlen, die in diesem Puffer gespeichert werden können, sowohl komprimiert als auch unkomprimiert. Teilen Sie den Puffer in diese beiden Abschnitte auf, beginnend mit dem Platz für komprimierte Daten und endend mit den nicht komprimierten Daten. Der Puffer sieht aus wie

  |compressed sorted|empty|empty|

• Füllen Sie den unkomprimierten Bereich mit zu sortierenden Zahlen. Der Puffer sieht aus wie

  |compressed sorted|empty|uncompressed unsorted|

• Sortieren Sie die neuen Nummern mit einer In-Place-Sortierung. Der Puffer sieht aus wie

  |compressed sorted|empty|uncompressed sorted|

• Richten Sie alle bereits komprimierten Daten aus der vorherigen Iteration im komprimierten Abschnitt nach rechts aus. Zu diesem Zeitpunkt wird der Puffer partitioniert

  |empty|compressed sorted|uncompressed sorted|

• Führen Sie eine Streaming-Dekomprimierung-Rekomprimierung für den komprimierten Abschnitt durch und fügen Sie die sortierten Daten im unkomprimierten Abschnitt zusammen. Der alte komprimierte Abschnitt wird verbraucht, wenn der neue komprimierte Abschnitt wächst. Der Puffer sieht aus wie

  |compressed sorted|empty|

Dieser Vorgang wird ausgeführt, bis alle Nummern sortiert wurden.

Kompression

Dieser Algorithmus funktioniert natürlich nur, wenn es möglich ist, die endgültige komprimierte Größe des neuen Sortierpuffers zu berechnen, bevor tatsächlich bekannt ist, was tatsächlich komprimiert wird. Daneben muss der Komprimierungsalgorithmus gut genug sein, um das eigentliche Problem zu lösen.

Der verwendete Ansatz verwendet drei Schritte. Erstens speichert der Algorithmus immer sortierte Sequenzen, daher können wir stattdessen nur die Unterschiede zwischen aufeinanderfolgenden Einträgen speichern. Jeder Unterschied liegt im Bereich [0, 99999999].

Diese Unterschiede werden dann als unärer Bitstrom codiert. Eine 1 in diesem Strom bedeutet "Addiere 1 zum Akkumulator, A 0 bedeutet" Gib den Akkumulator als Eintrag aus und setze ihn zurück ". Die Differenz N wird also durch N 1 und eine 0 dargestellt.

Die Summe aller Unterschiede nähert sich dem vom Algorithmus unterstützten Maximalwert, und die Anzahl aller Unterschiede nähert sich der Anzahl der in den Algorithmus eingefügten Werte. Dies bedeutet, dass wir erwarten, dass der Stream am Ende Maximalwerte 1 und Zählwerte 0 enthält. Dies ermöglicht es uns, die erwartete Wahrscheinlichkeit einer 0 und 1 im Stream zu berechnen. Die Wahrscheinlichkeit einer 0 ist nämlich count/(count+maxval)und die Wahrscheinlichkeit einer 1 ist maxval/(count+maxval).

Wir verwenden diese Wahrscheinlichkeiten, um ein arithmetisches Codierungsmodell über diesen Bitstrom zu definieren. Dieser arithmetische Code codiert genau diese Mengen von Einsen und Nullen im optimalen Raum. Wir können den von diesem Modell verwendeten Raum für jeden Zwischenbitstrom wie folgt berechnen : bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount). Um den insgesamt erforderlichen Speicherplatz für den Algorithmus zu berechnen, setzen Sie encodedden Betrag gleich.

Um keine lächerliche Anzahl von Iterationen zu erfordern, kann dem Puffer ein kleiner Overhead hinzugefügt werden. Dies stellt sicher, dass der Algorithmus mindestens mit der Anzahl von Zahlen arbeitet, die in diesen Overhead passen, da der mit Abstand größte Zeitaufwand des Algorithmus die arithmetische Codierungskomprimierung und -dekomprimierung in jedem Zyklus ist.

Darüber hinaus ist ein gewisser Aufwand erforderlich, um Buchhaltungsdaten zu speichern und geringfügige Ungenauigkeiten bei der Festkomma-Approximation des arithmetischen Codierungsalgorithmus zu verarbeiten. Insgesamt kann der Algorithmus jedoch auch mit einem zusätzlichen Puffer, der enthalten kann, in 1 MB Speicherplatz passen 8000 Nummern für insgesamt 1043916 Byte Speicherplatz.

Optimalität

Außerhalb der Reduzierung des (kleinen) Overheads des Algorithmus sollte es theoretisch unmöglich sein, ein kleineres Ergebnis zu erzielen. Um nur die Entropie des Endergebnisses zu enthalten, wären 1011717 Bytes erforderlich. Wenn wir den zusätzlichen Puffer subtrahieren, der aus Effizienzgründen hinzugefügt wurde, verwendete dieser Algorithmus 1011916 Bytes, um das Endergebnis + Overhead zu speichern.

Wenn der Eingabestream einige Male empfangen werden könnte, wäre dies viel einfacher (keine Informationen dazu, Idee und Zeitleistungsproblem).

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 Eingabestream befinden würde.

Wenn der Eingabestream einige Male empfangen werden könnte, wäre dies viel einfacher (keine Informationen dazu, Idee und Zeitleistungsproblem). 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 Eingabestream befinden würde.

Das Sortieren ist hier ein sekundäres Problem. Wie bereits erwähnt, ist das Speichern der Ganzzahlen schwierig und kann nicht für alle Eingaben verwendet werden , da 27 Bit pro Nummer erforderlich wären.

Ich gehe davon aus, dass nur die Unterschiede zwischen den aufeinanderfolgenden (sortierten) Ganzzahlen gespeichert werden, da diese höchstwahrscheinlich klein sind. Verwenden Sie dann ein Komprimierungsschema, z. B. mit 2 zusätzlichen Bits pro Eingangsnummer, um zu codieren, auf wie vielen Bits die Nummer gespeichert ist. 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 angegebenen Speicherbeschränkung zu speichern. Die Mathematik, wie das Komprimierungsschema ausgewählt wird, damit es mit der maximalen Anzahl von Eingaben funktioniert, ist mir ein Rätsel.

Ich hoffe, dass Sie in der Lage sein können, domänenspezifisches Wissen über Ihre Eingabe zu nutzen, um auf dieser Grundlage ein ausreichend gutes Ganzzahlkomprimierungsschema zu finden .

Oh und dann führen Sie eine Einfügesortierung in dieser sortierten Liste durch, während Sie Daten erhalten.

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

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

Ich arbeite daran, so viele wie möglich zu nehmen und (fast) an Ort und Stelle zu komprimieren. Die erste Charge von fast 250 KB würde bestenfalls jeweils etwa 9 Bit benötigen. Das Ergebnis würde also ungefähr 275 KB dauern. Wiederholen Sie dies einige Male mit dem verbleibenden freien Speicher. Dann dekomprimieren, zusammenführen, komprimieren und komprimieren. Das ist ziemlich schwer , aber möglich. Ich glaube.

Die zusammengeführten Listen würden dem 7-Bit-Ziel pro Ganzzahl immer näher kommen. Aber ich weiß nicht, wie viele Iterationen die Merge-Schleife 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?

Sie müssen nur die Unterschiede zwischen den Nummern nacheinander speichern und diese Sequenznummern mithilfe einer Codierung komprimieren. Wir haben 2 ^ 23 Bits. Wir werden es in 6-Bit-Blöcke unterteilen und das letzte Bit angeben lassen, ob sich die Zahl auf weitere 6 Bits erstreckt (5 Bit plus erweiterter Block).

Somit ist 000010 1 und 000100 ist 2. 000001100000 ist 128. Wir betrachten nun die schlechteste Besetzung bei der Darstellung von Unterschieden in der Reihenfolge 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.

Also addieren wir, 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 noch ein bisschen Speicher benötigen, um die Summe zu speichern, wo wir sind, wenn wir neue Zahlen einfügen. Wir gehen dann die Sequenz durch und finden heraus, wo wir unsere neue Nummer einfügen können, verringern gegebenenfalls den nächsten Unterschied und verschieben alles danach nach rechts.

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

• Wir müssen alle Zahlen laden, bevor wir sie sortieren können.
• Der Satz von Zahlen ist nicht komprimierbar.

Wenn diese Annahmen zutreffen, gibt es keine Möglichkeit, Ihre Aufgabe auszuführen, da Sie mindestens 26.575.425 Speicherbits (3.321.929 Byte) benötigen.

Was können Sie uns über Ihre Daten sagen?

Der Trick besteht darin, den Algorithmuszustand, der eine ganzzahlige Mehrfachmenge ist, als komprimierten Strom von "Inkrementzähler" = "+" und "Ausgangszähler" = "!" Darzustellen. Figuren. Zum Beispiel würde die Menge {0,3,3,4} als "! +++ !! +!" Dargestellt, gefolgt von einer beliebigen Anzahl von "+" Zeichen. Um den Multi-Set zu ändern, streamen Sie die Zeichen aus, wobei jeweils nur eine konstante Menge dekomprimiert wird, und nehmen Änderungen vor, bevor Sie sie in komprimierter Form zurückstreamen.

Einzelheiten

Wir wissen, dass der endgültige Satz genau 10 ^ 6 Zahlen enthält, also 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 "!" S unter 10 ^ 8 "+" s anordnen können, ist (10^8 + 10^6) choose 10^6, und daher erfordert die Angabe einer bestimmten Anordnung ~ 0,965 MiB `Daten. Das wird eng.

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 jedes Zeichen ein "+" ist, wenn wir vergessen, dass sie abhängig sind. Eine Quote von 100: 101 entspricht ~ 0,08 Bit pro Zeichen bei einer nahezu identischen Summe von ~ 0,965 MiB (das Ignorieren der Abhängigkeit kostet in diesem Fall nur ~ 12 Bit !).

Die einfachste Technik zum Speichern unabhängiger Zeichen mit bekannter vorheriger Wahrscheinlichkeit ist die Huffman-Codierung . Beachten Sie, dass wir einen unpraktisch großen Baum benötigen (Ein Huffman-Baum für Blöcke mit 10 Zeichen hat durchschnittliche Kosten pro Block von etwa 2,4 Bit für insgesamt ~ 2,9 Mib. Ein Huffman-Baum für Blöcke mit 20 Zeichen hat 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 hundert benötigen, was bedeutet, dass mehr Knoten in unserem Baum vorhanden sind, als alle jemals existierenden Computergeräte speichern können. ). ROM ist jedoch je nach Problem technisch "frei", und praktische Lösungen, die die Regelmäßigkeit im Baum nutzen, sehen im Wesentlichen gleich aus.

Pseudocode

• Lassen Sie einen ausreichend großen Huffman-Baum (oder ähnliche blockweise Komprimierungsdaten) im ROM speichern
• Beginnen Sie mit einer komprimierten Zeichenfolge von 10 ^ 8 "+" Zeichen.
• Um die Zahl N einzufügen, streamen Sie die komprimierte Zeichenfolge, bis N "+" Zeichen vergangen sind, und fügen Sie dann ein "!" Ein. Streamen Sie die erneut komprimierte Zeichenfolge währenddessen über die vorherige Zeichenfolge, wobei Sie eine konstante Anzahl gepufferter Blöcke beibehalten, um Über- / Unterläufe zu vermeiden.
• Wiederholen Sie eine Million Mal: ​​[Eingabe, Stream-Dekomprimierung> Einfügen> Komprimieren] und dann zur Ausgabe dekomprimieren

Wir haben 1 MB - 3 KB RAM = 2 ^ 23 - 3 * 2 ^ 13 Bit = 8388608 - 24576 = 8364032 Bit 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 ziemlich gleichmäßiger Zahlen, wenn alle Lücken <128 sind. Dies ist einfach. Speichern Sie einfach die erste Nummer und die 7-Bit-Lücken:

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

Beachten Sie, dass wiederholte Zahlen Lücken von 0 haben.

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

OK, nehmen wir an, eine Lückengröße <127 wird direkt dargestellt, aber auf eine Lückengröße von 127 folgt eine kontinuierliche 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.

Bei nur kleinen Lücken <127 sind noch 7000027 Bit erforderlich.

Es kann bis zu (10 ^ 8) / (2 ^ 7) = 781250 23-Bit-Lücken geben, was zusätzliche 16 * 781.250 = 12.500.000 Bits erfordert, was zu viel ist. Wir brauchen eine kompaktere und langsam zunehmende 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 meiner Meinung nach kurz genug halten, aber es muss mehr Analyse.

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

1. Stellen Sie eine vernünftige Blockgröße ein

Pseudo-Code-Idee:

1. Der erste Schritt wäre, alle Duplikate zu finden und sie mit ihrer Anzahl in ein Wörterbuch zu stecken und sie zu entfernen.
2. Der dritte Schritt wäre, eine Zahl zu platzieren, die in der Reihenfolge ihrer algorithmischen Schritte existiert, und sie in Zähler-Spezialwörterbücher mit der ersten Zahl und ihrem Schritt wie n, n + 1 ..., n + 2, 2n, 2n + 1, zu platzieren. 2n + 2 ...
3. Beginnen Sie, einige vernünftige Zahlenbereiche wie alle 1000 oder je 10000 in Stücken zu komprimieren, um die verbleibenden Zahlen zu wiederholen, die seltener zu wiederholen scheinen.
4. Dekomprimieren Sie diesen Bereich, wenn eine Zahl gefunden wird, und fügen Sie ihn dem Bereich hinzu. Lassen Sie ihn eine Weile länger unkomprimiert.
5. Andernfalls fügen Sie diese Nummer einfach einem Byte hinzu [chunkSize]

Fahren Sie mit den ersten 4 Schritten fort, während Sie den Stream empfangen. Der letzte Schritt besteht darin, entweder fehlzuschlagen, wenn Sie den Arbeitsspeicher überschritten haben, oder das Ergebnis auszugeben, sobald alle Daten erfasst wurden, indem Sie damit beginnen, die Bereiche zu sortieren und die Ergebnisse der Reihe nach auszuspucken und diejenigen zu dekomprimieren, die dekomprimiert werden müssen, und sie zu sortieren, wenn du kommst zu ihnen.