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

Ich habe einen computer mit 1 MB RAM und keine anderen lokalen Speicher. Ich muss es verwenden, nehmen Sie 1 million 8-stelligen Dezimalzahlen, die über eine TCP-Verbindung, Sortieren Sie Sie, und senden Sie dann die sortierte Liste über eine weitere TCP-Verbindung.

Die Liste der zahlen kann Duplikate enthalten, das muss ich nicht verwerfen. Der code wird in ROM, so brauche ich Sie nicht subtrahieren Sie die Größe von meinem code aus dem 1 MB. Ich habe bereits code-Laufwerk Ethernet-port und Griff TCP/IP-verbindungen, und es erfordert 2 KB den Zustand der Daten, einschließlich eines 1 KB Puffer über, die den code Lesen und schreiben von Daten. Gibt es eine Lösung für dieses problem?

Quellen In Frage Und Antwort:
slashdot.org

cleaton.net

Kommentar zu dem Problem

Ehm, eine million mal 8-stelligen Dezimalzahl (min. 27-bit-Ganzzahl, Binär -) > 1MB ram Kommentarautor: Mr47

1M RAM bedeutet 2^20 bytes? Und wie viele bits werden in ein byte auf dieser Architektur? Und die "Millionen" in "1 million 8-stellige Dezimalzahlen" eine SI-Millionen (10^6)? Was ist eine 8-stellige Dezimalzahl, die einer natürlichen Zahl < 10^8, eine rationale Zahl, deren Dezimaldarstellung dauert 8-stellig, ohne den Dezimalpunkt, oder etwas anderes? Kommentarautor:

1 Mio 8 dezimale zahlen oder 1 million 8-bit-zahlen? Kommentarautor: Patrick White

es erinnert mich an einen Artikel in "Dr. Dobb ' s Journal" (irgendwo zwischen 1998-2001), wo der Autor verwendet eine insertion sort zum Sortieren von Telefonnummern, wie er war, Sie zu Lesen: das war das erste mal, dass ich erkannte, dass, manchmal, ein langsamer Algorithmus schneller... Kommentarautor: Adrien Plisson

Es gibt eine andere Lösung, niemand hat noch erwähnt: Kauf von hardware mit 2MB RAM. Es sollte nicht sehr viel teurer sein, und es wird das problem viel, viel einfacher zu lösen. Kommentarautor: Daniel Wagner

InformationsquelleAutor der Frage |

404

Hier einige C++ - code , die das problem löst.

~~der Beweis, dass der Speicher Einschränkungen erfüllt sind:~~

Herausgeber: Es gibt keinen Nachweis, dass der maximale Speicherbedarf angeboten, durch die der Autor entweder in diesem post oder in seinen blogs. Da die Anzahl von bits erforderlich zum codieren eines Wertes richtet sich nach den Werten, die zuvor codiert, solch ein Beweis ist wahrscheinlich nicht trivial. Der Autor stellt fest, dass der größte codierte Größe, er könnte stolpern empirisch wurde 1011732 an und wählen Sie die Größe des Puffers 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, diese beiden arrays nehmen 1045000 Byte Speicherplatz. Das lässt 1048576 - 1045000 - 2×1024 = 1528 bytes für die restlichen Variablen und stack-Speicher.

Läuft es in etwa 23 Sekunden auf meinem Xeon W3520. Sie können überprüfen, dass das Programm arbeitet mit dem folgenden Python-Skript, vorausgesetzt, ein Programm namens 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 detaillierte Erläuterung des Algorithmus finden Sie in der folgenden Serie von Beiträgen:
InformationsquelleAutor der Antwort
403

Es ist eine ziemlich hinterhältige trick, die hier nicht erwähnt bisher. Wir gehen davon aus, dass Sie keine zusätzliche Möglichkeit Daten zu speichern, aber das ist nicht ganz wahr.

Ein Weg, um Ihr problem zu tun, die folgende schreckliche Sache, die sollte nicht versucht werden, von niemandem, unter keinen Umständen: Verwenden Sie den Netzwerk-traffic-Daten zu speichern. Und Nein, ich meine nicht NAS.

Sortieren Sie die zahlen mit nur ein paar bytes an RAM in der folgenden Weise:
- Ersten 2 Variablen: COUNTER und VALUE.
- Ersten Satz alle Register, um 0;
- Jedes mal, wenn Sie erhalten eine Ganzzahl I erhöhen COUNTER - und set - VALUE zu max(VALUE, I);
- Dann senden einer ICMP-echo-request-Paket mit Daten, die ich an den router. Löschen ich, wiederholt werden.
- Jedes mal, wenn Sie erhalten die zurückgegebenen ICMP-Paket, die Sie einfach entpacken Sie die integer-und schicken ihn wieder in einem anderen echo-Anfrage. Diese produziert eine große Anzahl von ICMP-Anfragen Versenkung vorwärts und rückwärts mit den zahlen.
Einmal COUNTER erreicht 1000000 haben Sie alle gespeicherten Werte in den unaufhörlichen Strom von ICMP-Anfragen, und VALUE enthält nun die maximale ganze Zahl. Pick einige threshold T >> 1000000. Set COUNTER auf null. Jedes mal, wenn Sie erhalten ein ICMP-Paket, erhöhen COUNTER und senden Sie die enthaltene integer, die ich schon aus einem anderen echo-Anfrage, es sei denn I=VALUE, in dem Fall zu übertragen, um den Zielordner für die sortierten zahlen. Einmal COUNTER=T -, verringern VALUE durch 1 -, reset - COUNTER auf null und wiederholen Sie. Einmal VALUE null erreicht, sollten Sie übermittelt haben, alle ganzen zahlen in der Reihenfolge von der größten bis zur kleinsten bis zum Ziel, und nur etwa 47 bits der RAM für die beiden persistente Variablen (und was auch immer kleine Betrag, den Sie brauchen für die temporären Werte).

Ich weiß, das ist schrecklich, und ich weiß, es kann alle möglichen praktischen Fragen, aber ich dachte, es könnte einige geben, die Euch ein lachen oder zumindest erschrecken Sie.

InformationsquelleAutor der Antwort

359

Finden Sie die erste richtige Antwort oder die später Antwort mit der arithmetischen Kodierung. Unten finden Sie etwas Spaß, aber nicht eine 100% - bullet-proof-Lösung.

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

Stufe 1: Initial-Daten-Struktur rau-Komprimierung Ansatz, grundlegende Ergebnisse

Wollen wir einige einfache Mathematik: wir haben 1M (1048576 bytes) RAM zunächst zu speichern 10^6 8-stelligen Dezimalzahlen. [0;99999999]. So speichern Sie eine Nummer 27 bits benötigt werden (unter der Annahme, dass zahlen ohne Vorzeichen verwendet werden). So, zum speichern einer raw-stream ~3,5 M RAM benötigt werden. Jemand schon sagte, es scheint nicht machbar, aber ich würde sagen, die Aufgabe kann gelöst werden, wenn der Eingang "gut genug". Grundsätzlich ist die Idee zum komprimieren der Eingangsdaten mit Kompression Faktor 0.29 oder höher und tun Sortierung in einer geeigneten Weise.

Wir lösen Sie die Kompression, erste Ausgabe. Es gibt einige relevante tests, die bereits zur Verfügung:

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

"Ich lief einen test zu komprimieren, eine million aufeinander folgende Ganzzahlen, die Verwendung von
die verschiedenen Formen der Kompression. Die Ergebnisse sind wie folgt:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Sieht es aus wie LZMA (Lempel–Ziv–Markov chain algorithm) ist eine gute Wahl, weiterhin mit. Ich habe bereit eine einfache PoC, aber es gibt noch einige details hervorgehoben werden:

Speicher ist begrenzt, so ist die Idee, Vorsortieren zahlen und verwenden
komprimiert Eimer (dynamische Größe) als temporären Speicher
Es ist leichter zu erreichen eine bessere Kompression Faktor mit vorsortiert
Daten, so gibt es eine statische Puffer für jeden Eimer (zahlen aus dem Puffer sind, die sortiert werden, bevor LZMA)
Jede Gruppe hat einen bestimmten Bereich, so dass die endgültige Sortierung kann durchgeführt werden für
jede Gruppe separat
Eimer der Größe richtig eingestellt, es wird also genug Speicher, um
Dekomprimieren Sie gespeicherten Daten und die endgültige Sortierung für jede Gruppe separat

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

Bitte beachten Sie, dass angehängte code ist ein POC, kann es nicht verwendet werden als eine endgültige Lösung, es nur zeigt, dass die Idee, mehrere kleinere Puffer zu speichern, vorsortiert zahlen in einigen optimalen Weg (evtl. komprimiert). LZMA ist nicht vorgesehen, als eine endgültige Lösung. Es ist wie eine Schnellste Weg zur Einführung einer Kompression, um diese PoC.

Sehen den PoC-code weiter unten (bitte beachten Sie es ist nur eine demo, um es 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 erzeugt es die folgende:

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 aufsteigender Reihenfolge (ein Eimer verwendet wird) produziert:

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:

Versuchen Sie nicht zu täuschen Natur
Verwenden einfachere Komprimierung mit geringeren memory-footprint
Einige zusätzliche Hinweise, die wirklich benötigt werden. Gemeinsame bullet-proof-Lösung scheint nicht möglich.

Stufe 2: Verbesserte Komprimierung, endgültigen Abschluss

Wie bereits im vorherigen Abschnitt erwähnt, eine geeignete Kompression, die verwendet werden können. Also lassen Sie uns loszuwerden, LZMA zugunsten einfacher und besser (wenn möglich) - Ansatz. Es gibt viele gute Lösungen, einschließlich Die arithmetische Codierung, Radix Baum etc.

Sowieso, einfache, aber nützliche Codierungsschema wird umso anschaulicher, als noch eine weitere externe Bibliothek, die einige nette Algorithmus. Die eigentliche Lösung ist ziemlich einfach: da gibt es die Eimer mit teilweise sortiert Daten, deltas kann verwendet werden, anstelle von zahlen.

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

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, dass dieser Ansatz:

nicht verbrauchen eine Menge Speicher,
arbeitet mit streams
bietet nicht so schlechte Ergebnisse

Vollständigen code finden hier, BinaryInput und BinaryOutput-Implementierungen gefunden werden kann hier

Endgültigen Abschluss

Keine endgültige Schlussfolgerung 🙂 Manchmal ist es wirklich gute Idee zu verschieben, eine Ebene nach oben und überprüfen Sie die task aus einem meta-Ebene Sicht.

War es Spaß zu verbringen einige Zeit mit dieser Aufgabe. BTW, es gibt eine Menge interessanter Antworten. Ich danke Ihnen für Ihre Aufmerksamkeit und freut sich codding.

InformationsquelleAutor der Antwort

163

Eine Lösung ist nur möglich, weil der Unterschied zwischen 1 MB und 1 million bytes. Es gibt ungefähr 2, um die Leistungsfähigkeit 8093729.5 verschiedenen Möglichkeiten zu wählen 1 Mio 8-stellige zahlen mit Duplikaten erlaubt und die Reihenfolge unwichtig ist, so eine Maschine mit nur 1 million bytes RAM nicht genügend Zustände repräsentieren alle Möglichkeiten. Aber 1M (weniger 2k für TCP/IP) 1022*1024*8 = 8372224 bits, so dass eine Lösung möglich ist.

Teil 1, erste Lösung

Dieser Ansatz erfordert ein wenig mehr als 1M ist, werde ich es optimieren um fit in 1M später.

Ich werde store eine kompakte sortierte Liste von zahlen im Bereich von 0 bis 99999999 als eine Sequenz von Teillisten von 7-bit-zahlen. Die erste Unterliste enthält die zahlen von 0 bis 127, der zweite Unterliste enthält zahlen von 128 bis 255, etc. 100000000/128 ist genau 781250, so 781250 solche unterlisten benötigt werden.

Jede Unterliste besteht aus einem 2-bit-Teilliste header, gefolgt von einer Unterliste Körper. Die Unterliste Körper dauert bis zu 7 bits pro Teilliste Eintrag. Die Teillisten sind alle miteinander verkettet, und das format macht es möglich zu sagen, wo man Teilliste endet und die nächste beginnt. Der Gesamt-Speicherbedarf für eine voll bestückte Liste ist 2*781250 + 7*1000000 = 8562500 bits, was ungefähr 1.021 M-bytes.

4 möglichen Teilliste header-Werte sind:

00 Teilliste Leer, nichts folgt.

01 Singleton ist, es ist nur ein Eintrag in der Teilliste und und die nächsten 7 bits halten.

10 Die Unterliste hält mindestens 2 verschiedene zahlen. Die Einträge sind gespeichert in nicht-absteigender Reihenfolge, außer, dass der Letzte Eintrag ist weniger als oder gleich dem ersten. Dies ermöglicht dem Ende der Teilliste identifiziert werden. Zum Beispiel, die zahlen 2,4,6 würde gespeichert werden (4,6,2). Die zahlen 2,2,3,4,4 würde gespeichert werden (2,3,4,4,2).

11 Die Unterliste hält 2 oder mehr Wiederholungen einer einzigen Zahl. Die nächsten 7 bits geben die Nummer ein. Dann kommen null oder mehr 7-bit-Einträge mit dem Wert 1, gefolgt von einer 7-bit-Eintrag mit dem Wert 0. Die Länge der Teilliste Körper bestimmt die Anzahl der Wiederholungen. Zum Beispiel, die zahlen 12,12 würde gespeichert werden (12,0), die zahlen 12,12,12 würde gespeichert werden (12,1,0), 12,12,12,12 wäre (12,1,1,0) und so weiter.

Ich beginne mit einer leeren Liste, Lesen eine Reihe von zahlen, die in und speichern Sie Sie als 32-bit-Ganzzahlen Sortieren Sie die neuen Nummern (mit heapsort, wahrscheinlich) und dann verschmelzen Sie in eine neue, kompakte sortierte Liste. Wiederholen Sie, bis es keine mehr zahlen zu Lesen, dann zu Fuß die kompakte Liste einmal mehr die Ausgabe zu generieren.

In der Zeile darunter steht-Speicher kurz vor dem start der Liste merge-Vorgang. Die "O"s sind die region, halten Sie die sorted-32-bit-Ganzzahlen. Die "X"sind die region, halten die alten kompakten Liste. Die " = " - Zeichen sind die Erweiterung Raum für die compact Liste, 7 bits für jede ganze Zahl in die "O"s. Die "Z"s sind andere zufällige Aufwand.
```
ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX
```
Der merge-routine liest die am weitesten Links stehende "O" und auf dem linken "X", und beginnt mit dem schreiben an die am weitesten Links stehende "=". Die schreib-Zeiger nicht fangen die kompakten Liste gelesen Zeiger, bis alle neuen Ganzzahlen zusammengeführt werden, da beide die Zeiger Voraus 2 bits für jede Teilliste und 7 bits für jeden Eintrag in der alten kompakten Liste, und es gibt genug extra Zimmer für die 7-bit-Einträge für die neuen zahlen.

Teil 2, pauken es in 1M

Squeeze die Lösung oben in 1M, die ich brauche, um die kompakte Liste format ein bisschen mehr kompakt. Ich werde Sie loszuwerden, ein von der Unterliste Arten, so dass es nur 3 verschiedene mögliche Teilliste header-Werte. Dann kann ich verwenden "00", "01" und "1" als Unterliste header-Werte und speichern Sie ein paar bits. Die Unterliste Arten sind:

Einem Leeren Unterverzeichnis, nichts folgt.

B Singleton ist, es ist nur ein Eintrag in der Teilliste und und die nächsten 7 bits halten.

C Die Unterliste hält mindestens 2 verschiedene zahlen. Die Einträge sind gespeichert in nicht-absteigender Reihenfolge, außer, dass der Letzte Eintrag ist weniger als oder gleich dem ersten. Dies ermöglicht dem Ende der Teilliste identifiziert werden. Zum Beispiel, die zahlen 2,4,6 würde gespeichert werden (4,6,2). Die zahlen 2,2,3,4,4 würde gespeichert werden (2,3,4,4,2).

D Die Unterliste besteht aus 2 oder mehr Wiederholungen einer einzigen Zahl.

Meine 3 Teilliste header-Werte "A", "B" und "C", also brauche ich eine Methode zur Darstellung von D-Typ-Teillisten.

Denke, ich habe den C-Typ-Teilliste-header, gefolgt von 3-Einträge, wie beispielsweise "C[17][101][58]". Diese können nicht Teil einer gültigen C-Typ-Teilliste, wie oben beschrieben, da der Dritte Eintrag ist kleiner als der zweite aber mehr als der erste. Ich kann diese Art von Konstrukt zur Darstellung eines D-Typ-Teilliste. In etwas Hinsicht, überall habe ich "C{00?????}{1??????}{01?????}" ist eine Unmögliche Typ C-Teilliste. Ich werde diese repräsentieren eine Teilliste bestehend aus 3 oder mehr Wiederholungen einer einzigen Zahl. Die ersten beiden 7-bit-Worte codieren, die Anzahl (das "N" bits unten) und werden gefolgt von null oder mehr {0100001} Wörtern, gefolgt von einem {0100000} Wort.
```
For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.
```
, Der nur aus Listen, die halten genau 2 Wiederholungen einer einzigen Zahl. Ich werde repräsentieren diese mit anderen unmöglich C-Typ-Teilliste Muster: "C{0??????}{11?????}{10?????}". Es gibt viel Platz für die 7 bits der Zahl in den ersten 2 Worten, aber dieses Muster ist mehr als die Teilliste, die er vertritt, das macht die Sache ein bisschen komplexer. Die fünf Frage-Zeichen am Ende betrachtet werden kann, nicht Teil des Musters, also ich habe: "C{0NNNNNN}{11N????}10", wie meine Muster, mit dem die Anzahl wiederholt werden gespeichert in der "N"s. Das sind 2 bits zu lang.

Werde ich zu leihen, 2 bits und zahlen Ihnen zurück von der 4 ungenutzte bits in dieses Muster. Beim Lesen, auf die Begegnung mit "C{0NNNNNN}{11N00AB}10", Ausgabe 2 Instanzen von der Zahl in der "N"s, überschreiben Sie die "10" am Ende mit bits A und B, vor-und Zurückspulen der lese-Zeiger um 2 bits. Destruktive liest sind ok für diesen Algorithmus, da jedes kompakte Liste wird ging nur einmal.

Beim schreiben eine Unterliste von 2 Wiederholungen einer einzelnen Nummer, schreiben Sie "C{0NNNNNN}11N00", und setzen Sie das geliehene bit-Zähler auf 2. Bei jedem schreiben wo das geliehene bit-Zähler ungleich null ist, verringert für jedes bit geschrieben, und "10" geschrieben wird, wenn der Zähler null schlägt. So die nächsten 2 bits geschrieben wird, gehen Sie in die slots A und B, und dann die "10" wird fallen gelassen auf das Ende.

Mit 3 Teilliste-header-Werte, dargestellt durch "00", "01" und "1", kann ich zuweisen "1" zu den beliebtesten Teilliste geben. Ich benötige eine kleine Tabelle anzeigen Teilliste header-Werte zu Teilliste Typen, und ich brauche ein Ereignis-Zähler für jede Teilliste-Typ, so dass ich weiß, was das beste Teilliste header-mapping ist.

Schlimmsten Fall minimale Darstellung einer vollständig bestückten kompakte Liste tritt auf, wenn alle der Unterliste Arten sind gleichermaßen beliebt. In diesem Fall habe ich speichern 1 bit für jeden 3 Teilliste-Header, also die Liste die Größe ist 2*781250 + 7*1000000 - 781250/3 = 8302083.3 bit. Aufrunden auf eine 32-bit-Wort-Grenze, das ist 8302112 bits, oder 1037764 bytes.

1M minus 2k für TCP/IP-Zustand und buffer 1022*1024 = 1046528 bytes, ließ mich 8764 bytes, um mit zu spielen.

Aber was ist der Prozess der Veränderung der Unterliste header-mapping ? In der memory-Karte, "Z" ist zufällig overhead "=" frei ist, "X" ist die kompakte Liste.
```
ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
```
Beginn der Lektüre am weitesten Links stehende "X" und starten Sie das schreiben mit der linken "=" und rechts arbeiten. Wenn es fertig ist das kompakte Liste wird etwas kürzer sein und es wird am falschen Ende der Erinnerung:
```
ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======
```
So, dann werde ich brauchen, um shunt, um die richtige:
```
ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
```
In der header-mapping change-Prozess, bis zu 1/3 der Unterliste Header ändern von 1-bit 2-bit. Im schlimmsten Fall werden Sie alle werden an der Spitze der Liste, so werde ich brauchen, zumindest 781250/3 bits Speicherplatz, bevor ich anfange, das bringt mich zurück zu der Speicherbedarf von der vorherigen version des kompakten Liste 🙁

Umgehen können, wir teilen die 781250 Teillisten in 10 Teilliste Gruppen von 78125 Teillisten jede. Jede Gruppe hat Ihren eigenen, unabhängigen Teilliste header-mapping. Mit den Buchstaben A bis J für die Gruppen:
```
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
```
Jede subliste Gruppe schrumpft oder gleich bleibt, während eine Unterliste header-mapping ändern:
```
ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ
ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ=======
ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ
```
Schlimmsten Fall die vorübergehende Ausdehnung einer Unterliste Gruppe während eines mapping ändern ist 78125/3 = 26042 bits, unter 4k. Wenn ich damit 4k plus die 1037764 bytes für eine voll bestückte kompakte Liste, das lässt mich 8764 - 4096 = 4668 bytes für die "Z"s in der memory map.

Werden sollte, dass viel für die 10 Teilliste header-mapping Tabellen, 30 Teilliste header vorkommen zählt und das andere paar Zähler, Zeiger und kleine Puffer werde ich brauchen, und der Raum, den ich verwendet habe, ohne zu merken, wie stack-Speicher für die Funktion call-return-Adressen und lokale Variablen.

Teil 3, wie lange würde es dauern?

Mit einem leeren kompakte Liste der 1-bit-Liste-header verwendet werden, für die eine Teilliste leer, und die Anfangsgröße der Liste " wird 781250 bits. Im schlimmsten Fall wird die Liste wächst von 8 bit für jede Zahl Hinzugefügt, also 32 + 8 = 40 bits an Speicherplatz benötigt werden, für jede der 32-bit-zahlen ganz oben auf der Liste-Puffer und dann sortiert und zusammengeführt. Im schlimmsten Fall, die änderung der Unterliste header-mapping-Ergebnisse in einem Raum, Nutzung der 2*781250 + 7*Einträge - 781250/3 bits.

Mit einer Politik der änderung der Unterliste header-mapping nach jedem fünften verschmelzen, sobald es mindestens 800000 zahlen in der Liste, schlimmsten Fall würde eine Summe von etwa 30M von compact-Liste Lesen und schreiben.

Quelle:

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

InformationsquelleAutor der Antwort

Gilmanov die Antwort ist ganz falsch in seiner Annahmen. Es beginnt, darüber zu spekulieren, in einem sinnlos Maßnahme von einer million aufeinander folgenden zahlen. Das bedeutet, dass keine Lücken entstehen. Diese zufällige Lücken, jedoch klein ist, lässt es wirklich eine schlechte Idee.

Versuchen Sie es selbst. Holen Sie sich 1 million random-27-bit-Ganzzahlen, Sie zu Sortieren, komprimieren mit 7-Zip, xz, was LZMA Sie wollen. Das Ergebnis ist mehr als 1,5 MB. Die Prämisse, auf der Oberseite ist die Kompression von fortlaufenden Nummern. Auch delta-Kodierung das ist über 1,1 MB. Und nie daran, dies ist mit über 100 MB RAM für die Kompression. So auch die komprimierten Ganzzahlen passen nicht in das problem und nie Verstand run time RAM-Auslastung.

Es macht mich traurig, wie Menschen nur upvote hübsche Grafik und Rationalisierung.

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

}

Nun komprimieren mit int-Werten.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

InformationsquelleAutor der Antwort

39

Ich denke, ein Weg, um über diese denken ist von einem kombinatorischen Standpunkt: wie viele mögliche Kombinationen sortiert Anzahl Ordnungen gibt es? Wenn wir Ihnen die Kombination 0,0,0,....,0 code 0, 0,0,0,...,1 den code 1 und 99999999, 99999999, ... 99999999 code N, was ist N? In anderen Worten, wie groß ist das Resultat Raum?

Gut, eine Weise zu denken, dazu ist zu bemerken, dass dies eine bijection des Problems zu finden, die Zahl der monotonen Wege in ein N x M Gitter, wobei N = 1.000.000 und M = 100,000,000. In anderen Worten, wenn Sie ein raster verwenden, das ist 1.000.000 breit und 100.000.000 hoch, wie viele kürzeste Wege von unten Links nach oben rechts gibt es? Kürzeste Pfade natürlich verlangen, dass Sie immer nur entweder nach rechts oder nach oben (wenn Sie nach unten oder Links würden Sie rückgängig machen der zuvor erreicht den Fortschritt). Um zu sehen, wie dies ist eine bijection unserer Nummer Sortieren problem, beachten Sie Folgendes:

Können Sie sich vorstellen, jedes horizontalen Schenkels auf unserem Weg als eine Zahl in unserer Bestellung, wo die Y-Position des Beines stellt den Wert.

So, wenn der Pfad einfach nach rechts bewegt den ganzen Weg bis zum Ende, dann springt den ganzen Weg an die Spitze, das ist äquivalent zu der Bestellung 0,0,0,...,0. wenn es stattdessen beginnt durch springen den ganzen Weg nach oben und dann nach rechts bewegt 1.000.000 mal, das ist äquivalent zu 99999999,99999999,..., 99999999. Einen Weg, wo es nach rechts einmal, dann einmal, dann den rechten, dann auf einmal, etc, um ganz am Ende (dann unbedingt springt den ganzen Weg an die Spitze), ist äquivalent zum 0,1,2,3,...,999999.

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

(1,000,000 + 100,000,000) Wählen (100,000,000) ~= 2.27 * 10^2436455

N entspricht somit 2.27 * 10^2436455, und so wird der code 0 steht 0,0,0,...,0 und der code 2.27 * 10^2436455 und einige Veränderungen stellt 99999999,99999999,..., 99999999.

Um zu speichern, alle zahlen von 0 bis 2.27 * 10^2436455 Sie brauchen, lg2 (2.27 * 10^2436455) = 8.0937 * 10^6 bit.

1 megabyte = 8388608 bits > 8093700 bits

So scheint es, dass wir zumindest haben tatsächlich genug Platz, um das Ergebnis speichern! Jetzt ist natürlich der interessante Teil ist dabei die Sortierung der Nummern-stream. Sicher nicht der beste Ansatz, um dies gegeben ist, haben wir 294908 bits übrig. Ich Stelle mir eine interessante Technik, um an jedem Punkt davon ausgehen, dass die gesamte Bestellung, finden Sie den code für die Bestellung, und dann, wie Sie erhalten eine neue Nummer gehen Sie zurück und aktualisieren Sie den vorherigen code. Hand-Welle hand-Welle.

InformationsquelleAutor der Antwort
18

Meine Vorschläge hier viel zu verdanken Dan ' s Lösung

Ersten aus-ich nehme an, die Lösung behandeln muss alle möglich input-Listen. Ich denke, dass die gängigen Antworten, die nicht in dieser Annahme (was IMO ein großer Fehler).

Es ist bekannt, dass es keine verlustfreie Komprimierung reduziert die Größe aller Eingänge.

Alle gängigen Antworten nehme an, Sie werden in der Lage sein zu gelten, Kompression wirksam genug, um Ihnen zu erlauben extra Raum. In der Tat, ein Stück extra Raum groß genug zu halten ein Teil Ihres teilweise fertige Liste in eine unkomprimierte form und es Ihnen ermöglichen, zur Erfüllung Ihrer Sortier-Operationen. Dies ist nur eine falsche Annahme.

Für eine solche Lösung, wer mit wissen, wie Sie Ihre Kompression in der Lage, einige input-Daten, die nicht komprimiert gut für diese Regelung, und die "Lösung" wird höchstwahrscheinlich dann Pause wegen Platzmangel.

Stattdessen nehme ich einen mathematischen Ansatz. Die Ausgänge sind alle Listen der Länge LEN, bestehend aus Elementen, die in den Bereich 0..MAX. Hier die LEN 1.000.000 und unser MAX ist 100,000,000.

Für beliebige LEN und MAX, die Menge der bits erforderlich zum codieren dieser Zustand ist:

Log2(MAX Multichoose LEN)

Also für unsere zahlen, sobald wir abgeschlossen haben, erhalten und Sortieren, benötigen wir mindestens Log2(100,000,000 MC 1,000,000) bits speichern das Ergebnis in einer Form, die eindeutig zu unterscheiden, alle möglichen Ausgänge.

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

[Gelöscht, die sinnlos wuchernden nun, dass bessere Beispiele vorhanden...]

Beste Antwort hier.

Andere gute Antwort hier und verwendet grundsätzlich insertion sort als Funktion um die Liste zu erweitern, indem Sie ein element (Puffer ein paar Elemente und pre-Art, ermöglichen die insertion von mehr als ein zu einer Zeit, spart ein bisschen Zeit). nutzt ein schön kompaktes state-Kodierung, Eimern, sieben-bit-deltas

InformationsquelleAutor der Antwort
17

Nehme an, diese Aufgabe möglich ist. Kurz vor der Ausgabe wird es eine in-memory-Repräsentation der Millionen von sortierten zahlen. Wie viele verschiedene derartige Darstellungen gibt es? Da kann es wiederholt werden zahlen, die wir nicht verwenden können, nCr (), aber es ist ein Betrieb namens multichoose, dass die arbeiten an multimengen.
- Es gibt 2.2e2436455 Möglichkeiten, um wählen Sie eine million zahlen im Bereich 0..99,999,999.
- Erfordert 8,093,730 bits zu repräsentieren jede mögliche Kombination, oder 1,011,717 bytes.
Also theoretisch kann es möglich sein, wenn Sie mit oben kommen kann, dass ein geistig gesunder (genug) Darstellung der sortierten Liste von zahlen. Zum Beispiel, eine unglaubliche Darstellung, möglicherweise eine 10MB-lookup-Tabelle oder Tausende Zeilen von code.

Jedoch, wenn "1 MB RAM" bedeutet eine million bytes, dann ist klar, dass nicht genug Speicherplatz vorhanden ist. Die Tatsache, dass 5% mehr Speicher macht es theoretisch möglich ist, lässt mich vermuten, dass die Darstellung SEHR effizient und wahrscheinlich auch nicht zurechnungsfähig.

InformationsquelleAutor der Antwort
12

(Meine ursprüngliche Antwort falsch war, sorry für die schlechte Mathe, finden Sie unterhalb der Pause.)

Wie über dieses?

Den ersten 27 bits speichern Sie die niedrigste Zahl, die Sie gesehen haben, dann ist die Differenz zur nächsten Zahl gesehen, wie folgt codiert: 5 bits, die zum speichern der Anzahl der verwendeten bits bei der Speicherung der Unterschied, der Unterschied. Verwenden 00000, um anzuzeigen, dass Sie sah, dass Zahl wieder.

Dies funktioniert, weil da mehr zahlen eingefügt werden, der Durchschnittliche Unterschied zwischen den zahlen geht nach unten, so dass man weniger bits zum speichern der Differenz, die Sie hinzufügen, mehr zahlen. Ich glaube, das heißt eine delta-Liste.

Schlimmsten Fall ich denken kann, ist alle zahlen gleichmäßig verteilt (von 100), Vorausgesetzt, z.B. 0 ist die erste Zahl:
```
000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k
```
Reddit ist die Rettung!

Wenn alles, was Sie zu tun hatte war, Sie zu Sortieren, dieses problem wäre leicht. Es dauert 122k (1 million bits) zu speichern, die zahlen, die Sie gesehen haben (das 0. bit auf ein, wenn die 0 zu sehen war, 2300th bit auf ein, wenn die 2300 zu sehen war, etc.

Lesen Sie die zahlen, speichern Sie Sie in das bit-Feld, und dann verschieben die bits aus, während eine Anzahl.

ABER, Sie haben zu daran erinnern, wie viele Sie gesehen haben. Ich wurde inspiriert durch die Unterliste Antwort oben zu kommen mit diesem Schema:

Anstatt ein bit, entweder 2 oder 27 bits:
- 00 bedeutet, dass Sie nicht sehen, die Zahl.
- 01 bedeutet, man sah es einmal
- 1 bedeutet, dass Sie es sah, und die nächsten 26 bits sind, die zählen, wie viele Male.
Ich denke, das funktioniert: wenn keine Duplikate vorhanden sind, haben Sie eine 244k Liste.
Im schlimmsten Fall sehen Sie jede Zahl zweimal (wenn Sie sehen, eine Zahl dreimal, verkürzt es den rest der Liste für Sie), das heißt, Sie haben gesehen, die 50.000 mehr als einmal, und Sie haben gesehen, 950,000 Elemente 0 oder 1 mal.

50,000 * 27 + 950,000 * 2 = 396.7 k.

Können Sie weiter zu verbessern, wenn Sie die folgenden Codierung:

0 bedeutet, dass Sie nicht sehen, die Zahl
10 bedeutet, dass Sie sah es einmal
11 ist, wie Sie zählen,

Wird, auf Durchschnitt, das Ergebnis in 280.7 Kb Speicher.

EDIT: mein Sonntag morgen Mathe war falsch.

Schlimmsten Fall sehen wir die 500.000 zahlen zweimal, so dass die Mathematik wird:

500,000 *27 + 500,000 *2 = 1.77 M

Die Alternative Kodierung ergibt sich eine Durchschnittliche Speicherung von

500,000 * 27 + 500,000 = 1,70 M

: (

InformationsquelleAutor der Antwort
9

Es gibt eine Lösung für dieses problem über alle möglichen Eingaben. Cheat.
1. Lesen m Werte über TCP, wobei m in der Nähe der max, die sortiert werden können, in der Erinnerung, vielleicht ist n/4.
2. Art der 250.000 (oder so) zahlen und ausgegeben werden.
3. Wiederholen Sie den Vorgang für die anderen 3 Viertel.
4. Lassen Sie den Empfänger fasse die 4 Listen von zahlen, erhalten hat, wie es verarbeitet wird. (Es ist nicht viel langsamer als die Verwendung einer einzelnen Liste.)
InformationsquelleAutor der Antwort
7

Ich würde versuchen, eine Radix Baum. Wenn Sie die Speicherung der Daten in einem Baum, man könnte dann eine in-order Durchlaufen, um die Daten zu übermitteln.

Ich bin nicht sicher, ob Sie passen könnte das in 1MB, aber ich denke, es ist einen Versuch Wert.

InformationsquelleAutor der Antwort
7

Welche Art von computer benutzt du? Es dürfen keine anderen "normalen" lokalen Speicher, aber muss es video-RAM zum Beispiel? 1-megapixel-x-32 bits pro pixel (sagen) ist ziemlich nah an Ihre benötigten Daten input-Größe.

(Ich weitgehend zu bitten in Erinnerung an die alten Acorn RISC PC, das könnte 'leihen' VRAM zu erweitern, die verfügbaren system-RAM, wenn Sie sich für eine niedrige Auflösung oder niedrige Farbtiefe-screen-Modus!). Dies war sehr nützlich, auf einem Computer mit nur ein paar MB normalen RAM.

InformationsquelleAutor der Antwort
6

Einem radix-Baum-Darstellung würde nahe zu kommen, um die Behandlung dieses Problems, da die radix-Baum nutzt die "Präfix-Komprimierung". Aber es ist schwer zu begreifen, von einer radix-Darstellung, darstellen könnte, die einen einzelnen Knoten in einem byte -- zwei ist wohl über das limit.

Aber, unabhängig davon, wie die Daten dargestellt werden, wenn es einmal sortiert ist, kann es gespeichert werden in Präfix-komprimierte form, in der die zahlen 10, 11 und 12 vertreten sein werden durch, sagen 001b, 001b, 001b, was auf eine Schrittweite von 1 von der vorherigen Zahl ist. Vielleicht, dann, 10101b darstellen würde eine Schrittweite von 5, 1101001b einen Zuwachs von 9, etc.

InformationsquelleAutor der Antwort
6

Gibt es 10^6 Werte in einem Bereich von 10^8, also gibt es einen Wert pro hundert-code Punkte im Durchschnitt. Speichern Sie den Abstand von der N-TEN Punkt auf den (N+1)th. Doppelte Werte haben eine skip-0. Dies bedeutet, dass das überspringen braucht durchschnittlich knapp 7 bit zu speichern, also eine million von Ihnen gerne passen in unseren 8 Millionen bits Speicher.

Diese überspringt, müssen codiert werden, in einem bitstream, also durch Huffman-Codierung. Insertion ist durch Durchlaufen der bitstream-und umschreiben nach den neuen Wert. Ausgabe durch Durchlaufen und schreiben der implizierten Werte. Für die Praktikabilität, ist es wahrscheinlich, will getan werden, als, sagen wir, 10^4 Listen für 10^4 code Punkte (und im Durchschnitt 100 Werte).

Einen guten Huffman-Baum für zufällige Daten können errichtet werden a priori von der Annahme einer Poisson-Verteilung (Mittelwert=Varianz=100) auf die Länge der überspringt, aber wirkliche Statistiken gehalten werden kann auf die Eingabe und verwendet, um eine optimale Struktur zum Umgang mit pathologischen Fällen.

InformationsquelleAutor der Antwort
5

Ich habe einen computer mit 1M RAM und keine anderen lokalen Speicher

Andere Weise zu betrügen: Sie könnte die Verwendung von nicht-lokalen (vernetzt) - Speicher statt (Ihre Frage nicht entgegenstehen) und rufen Sie einen vernetzten service könnten einfache disk-basierte mergesort (oder einfach nur genug Speicher zum Sortieren im Speicher, da Sie nur brauchen, um zu akzeptieren 1M-Nummern), ohne die (zugegebenermaßen geniale) - Lösungen bereits gegeben.

Diese könnte betrügen, aber es ist nicht klar, ob Sie auf der Suche nach einer Lösung für einen real-world-problem oder ein Rätsel, das einlädt, biegen der Regeln... wenn letzteres, dann eine einfache cheat bekommen kann bessere Ergebnisse als eine komplexe, aber "echte" Lösung (die wie andere haben darauf hingewiesen, kann nur funktionieren, für kompressible Eingänge).

InformationsquelleAutor der Antwort
5

Ich glaube, die Lösung ist die Kombination von Techniken aus der video-Codierung, nämlich die diskrete Cosinus-transformation. In der digitalen video -, sondern die Aufnahme der änderung der Helligkeit oder Farbe des Videos als reguläre Werte wie 110 112 115 116 jeweils abgezogen wird, die letzten (ähnlich wie run-length-encoding). 110 112 115 116 wird 110 2 3 1. Die Werte, 2 3 1 benötigen weniger bits als die Originale.

Also angenommen, wir erstellen eine Liste mit den input-Werten, wie Sie kommen auf den sockel. Wir speichern in jedem element, nicht der Wert, sondern der offset des einen vor ihm. Wir Sortieren, wie wir gehen, so dass die offsets sind nur gehen, um positiv zu sein. Aber der offset kann 8 Dezimalziffern breit, das passt in 3 bytes. Jedes element kann nicht 3 bytes, also müssen wir packen diese. Konnten wir das oberste bit eines jeden byte als ein "weiter-bit" gesetzt, was angibt, dass das nächste byte ist Teil der Nummer und die unteren 7 bits von jedem byte kombiniert werden müssen. null gültig für Duplikate.

Als die Liste füllt sich, die zahlen sollten näher zusammen, d.h. im Durchschnitt nur 1 byte verwendet wird, um zu bestimmen, den Abstand zum nächsten Wert. 7 bits von value und 1 bit-offset wenn bequem, aber es kann eine sweet-spot, der benötigt weniger als 8 bits für einen "weiter" - Wert.

Jedenfalls hatte ich etwas Experimentieren. Ich verwenden einen Zufallszahlengenerator, und ich kann passen eine million sortiert 8-stellige Dezimalzahlen in über 1279000 bytes. Der Durchschnittliche Abstand zwischen jeder Zahl ist konstant 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);
    }
}
```
InformationsquelleAutor der Antwort
4

Könnten wir spielen mit den Netzwerk-stack zu senden, die zahlen in sortierter Reihenfolge vor, die wir alle zahlen. Wenn Sie senden Sie 1M Daten, TCP/IP, wird es brechen in 1500 byte-Paketen und streamen Sie Sie, um das Ziel. Jedes Datenpaket erhält eine Sequenznummer.

Können wir diese von hand machen. Kurz bevor wir füllen unsere RAM Sortieren wir, was wir haben und schicken Sie die Liste an unser Ziel, aber lassen Sie Löcher in der Sequenz, um jede Anzahl. Dann den 2 1/2 die zahlen auf die gleiche Weise mit denen Löcher in der Sequenz.

Den Netzwerk-stack auf der Gegenseite versammeln sich die resultierende Datenstrom in der Reihenfolge der Sequenz, bevor er Sie von der Anwendung ab.

Es ist über das Netzwerk zum durchführen einer merge-sort. Dieses ist ein Gesamt-hack, aber ich wurde inspiriert durch die anderen Netzwerke hack zuvor aufgeführt.

InformationsquelleAutor der Antwort
4

Google's (bad) - Ansatz, von HN-thread. Speichern die RLE-Stil zählt.

Ihre erste Datenstruktur ist '99999999:0' (alles Nullen, habe nicht gesehen, keine zahlen) und dann sagen wir, dass Sie die Anzahl 3,866,344 so Ihre Datenstruktur wird '3866343:0,1:1,96133654:0' wie Sie sehen können die zahlen immer abwechseln zwischen der Anzahl der null-bits und der Anzahl von '1' - bits, so können Sie nur annehmen, die ungeraden zahlen stehen für 0-bits und die geraden zahlen 1-bits. Wird diese (3866343,1,96133654)

Ihre problem scheint sich nicht zu decken, Duplikate, aber lassen Sie uns sagen, verwenden Sie "0:1" für Duplikate.

Großes problem #1: Einschübe für 1M ganzen zahlen würde Jahre dauern.

Großes problem #2: wie alle einfachen delta-encoding-Lösungen, einige Distributionen, die nicht damit abgedeckt werden. Zum Beispiel, 1m ganzen zahlen mit den Entfernungen 0:99 (z.B. +99 jeder ein). Denken Sie jetzt das gleiche, aber mit random Entfernung in der Bereich von 0:99. (Hinweis: 99999999/1000000 = 99.99)

Google ' s Ansatz ist unwürdig (langsam) und falsch. Aber zu Ihrer Verteidigung, Ihr problem wurde möglicherweise etwas anders.

InformationsquelleAutor der Antwort
3

Repräsentieren die sortierten array kann man speichern nur das erste element und den Unterschied zwischen den angrenzenden Elementen. Auf diese Weise sind wir besorgt mit Codierung 10^6 Elemente, kann die Summe bis zu maximal 10^8. Nennen wir diese D. Zur Kodierung der Elemente von D man kann mit einem Huffman-code. Das Wörterbuch für den Huffman-code erstellt werden kann, auf die das array jedes mal aktualisiert, wenn ein neues Element eingefügt wird, in dem sortierten array (insertion sort). Beachten Sie, dass, wenn das Wörterbuch sich ändert, weil ein neues Element des ganzen Arrays sollte aktualisiert werden, um mit den neuen Codierung.

Die Durchschnittliche Anzahl von bits für die Codierung jedes element von D maximiert ist, wenn wir die gleiche Anzahl von jeder eindeutigen element. Sagen Elemente d1, d2, ..., dN in D jedem erscheinen F Zeiten. In diesem Fall (im schlimmsten Fall haben wir beide 0 und 10^8 in der Eingangs-Sequenz) wir haben

Summe(1<=ich<=N) F. di = 10^8

wo

Summe(1<=ich<=N) F = 10^6, oder F=10^6/N und die normalisierte Frequenz p= F/10^=1/N

Die Durchschnittliche Anzahl von bit -log2(1/P) = log2(N). Unter diesen Umständen sollten wir finden einen Fall, der maximiert N. Dies geschieht, wenn wir haben fortlaufende Nummern für di ab 0, oder, di= ich-1, also

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

d.h.

N <= 201. Und für diesen Fall die Durchschnittliche Anzahl der bits log2(201)=7.6511 das heißt, wir müssen um 1 byte pro input-element zum speichern der sortierten array. Beachten Sie, dass dies nicht bedeutet, D im Allgemeinen nicht mehr als 201 Elementen. Es ist nur Sauen, wenn die Elemente der D gleichmäßig verteilt, es kann nicht mehr als 201 eindeutige Werte.

InformationsquelleAutor der Antwort
3

Ich würde ausnutzen, die Weiterverbreitung Verhalten von TCP.
1. Machen die TCP-Komponente erstellen, die ein großes Fenster erhalten.
2. Erhalten eine gewisse Menge der Pakete, ohne das senden einer ACK für Sie.
  - Zu verarbeiten, die geht in die Schaffung von etwas (Präfix) für komprimierte Daten Struktur
  - Senden Duplikat-ack für das Letzte Paket, das nicht mehr benötigt wird/wait for retransmission timeout
  - Goto 2
3. Alle Pakete angenommen wurden,
Diese übernimmt irgendeine Art von nutzen von Eimern oder in mehreren Durchgängen.

Wahrscheinlich durch die Sortierung der Chargen/Eimer und Zusammenführen. -> radix Bäume

Verwenden Sie diese Technik zu akzeptieren und zu Sortieren, die ersten 80%, dann Lesen Sie die letzten 20%, stellen Sie sicher, dass die letzten 20% nicht, die zahlen enthalten, landen in den ersten 20% des niedrigsten zahlen. Senden Sie dann die 20% niedrigsten Nummern, entfernen von Speicher -, akzeptieren Sie die übrigen 20% der neuen zahlen und Zusammenführen.**

InformationsquelleAutor der Antwort
2

Wir haben 1 MB - 3 KB RAM = 2^23 - 3*2^13 bit = 8388608 - 24576 = 8364032 bits zur Verfügung.

Bekommen wir 10^6 zahlen in einer 10^8 Bereich. Dies ergibt eine Durchschnittliche Lücke von ~100 < 2^7 = 128

Betrachten Sie zunächst das einfachere problem der relativ gleichmäßig verteilte zahlen, wenn alle Lücken sind < 128. Das ist einfach. Speichern nur die erste Zahl und die 7-bit-Lücken:

(27 bits) + 10^6-7-bit-gap-zahlen = 7000027 erforderlichen bits

Hinweis wiederholten zahlen haben Lücken von 0.

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

OK, sagen wir eine Lücke-Größe < 127 wird direkt dargestellt, sondern eine Lücke-Größe von 127 ist gefolgt von einer kontinuierlichen 8-bit-Codierung für die tatsächliche Lücke Länge:
```
 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151
```
etc.

Hinweis: diese Zahl Darstellung beschreibt seine eigene Länge, so dass wir wissen, Wann die nächste Lücke-Nummer beginnt.

Mit nur kleinen Lücken < 127, dies erfordert noch 7000027 bits.

Kann es bis zu (10^8)/(2^7) = 781250 23-bit-Lücke-Nummer, eine zusätzliche 16*781,250 = 12,500,000 bits, die ist zu viel. Wir brauchen eine kompakte und langsam wachsende Darstellung von Lücken.

Die Durchschnittliche lückengröße ist 100, also wenn wir ordnen Sie als
[100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...]
und diese index-mit einem dichten binäre Fibonacci-base-Codierung ohne Paare von Nullen (zum Beispiel, 11011=8+5+2+1=16) mit zahlen getrennt durch '00' dann denke ich, wir können die Lücke, die Darstellung kurz, aber es braucht mehr Analyse.

InformationsquelleAutor der Antwort
2

Wenn der input stream können empfangen werden paar mal, dies wäre viel
einfacher (keine information über diese, Idee und Zeit-performance-problem).

Dann, wir könnten zählen die dezimal-Werte. Mit zahlwerten, es wäre
einfach, um den Ausgabe-stream. Komprimieren der zu zählenden Werte. Es
hängt davon ab, was wäre in der input-stream.

InformationsquelleAutor der Antwort
1

Wenn der input stream können empfangen werden paar mal, das wäre viel einfacher (keine Infos, Idee und Zeit-performance-problem). Dann könnten wir die Anzahl der dezimal-Werte. Mit zahlwerten es würde leicht sein, um den Ausgabe-stream. Komprimieren der zu zählenden Werte.
Es hängt davon ab, was wäre in der input-stream.

InformationsquelleAutor der Antwort
1

Sortierung ist ein sekundäres problem. Wie andere gesagt, nur das speichern der ganzen zahlen ist hart, und nicht arbeiten können, die auf alle Eingänge, seit 27 bits pro Zahl wäre notwendig.

Meine Meinung dazu ist: speichern nur die Unterschiede zwischen den aufeinander folgenden (sortierten) zahlen, wie Sie wird wahrscheinlich kleine. Dann verwenden Sie eine Komprimierung, z.B. mit 2 zusätzlichen bits pro Eingang Nummer zu codieren, wie viele bits die Anzahl gespeichert ist.
So etwas wie:
```
00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits
```
Sollte es möglich sein, speichern Sie eine ganze Reihe von möglichen input-Listen, die in dem gegebenen Speicher-Einschränkung. Die Mathe-gewusst wie: wählen Sie die Komprimierung, um es Arbeit auf die maximale Anzahl von Eingängen, sind mir schleierhaft.

Ich hoffe, Sie können nutzen zu können domain-spezifische wissen Ihrer Eingabe zu finden, die gut genug ist, integer compression scheme auf dieser Basis.

Oh, und dann, Sie machen eine insertion Sortieren, die sortierte Liste, wie du die Daten empfangen.

InformationsquelleAutor der Antwort
1

Ziel ist es jetzt zu einer tatsächlichen Lösung, die alle möglichen Fälle der Eingabe in den 8 stelligen Bereich mit nur 1MB RAM. HINWEIS: work in progress, wird morgen fortgesetzt. Mit Hilfe der arithmetischen Codierung des deltas von der int-Werte sortiert, schlimmsten Fall für 1M sortiert ints Kosten würde, über die 7bits pro Eintrag (da 99999999/1000000 ist 99, und log2(99) ist fast 7 bits).

Aber Sie müssen die 1m Ganzzahlen sortiert zu bekommen, um 7 oder 8 bits! Kürzere Serie hätte größer deltas, also mehr bits pro element.

Dem ich arbeite, so viele wie möglich und komprimieren (fast) in-place. Erste charge von knapp 250K ints brauchen würde, etwa 9 bits jedes am besten. Also Ergebnis würde etwa 275KB. Wiederholen Sie mit den restlichen freien Speicher ein paar mal. Dann entpacken-merge-in-place-komprimieren diese komprimierten Blöcken. Dies ist ziemlich hart, aber möglich. Ich denke.

Zusammengeführten Listen bekommen würde, näher und näher an die 7bit pro integer-Ziel. Aber ich weiß nicht, wie viele Iterationen es dauern würde, von der merge-Schleife. Vielleicht 3.

Aber die Ungenauigkeit der arithmetischen Codierung Implementierung könnte es unmöglich machen. Wenn dieses problem überhaupt möglich ist, wäre es extrem eng zu.

Irgendwelche Freiwilligen?

InformationsquelleAutor der Antwort
1

Brauchen Sie nur zum speichern der Differenzen zwischen den zahlen in der Reihenfolge, und verwenden Sie eine Codierung zu komprimieren, diese Sequenznummern. Wir haben 2^23 bits. Wir teilen es in 6bit Stücke, und lassen Sie das Letzte bisschen angeben, ob die Zahl reicht, um weitere 6 bits (5bits plus Verlängerung chunk).

So, 000010 1 000100 2. 000001100000 ist 128. Nun, betrachten wir die schlechteste Besetzung in der Vertretung der Unterschiede in der Sequenz der zahlen bis zu 10,000,000. Kann es sein 10,000,000/2^5 Unterschiede größer als 2^5, 10,000,000/2^10 Unterschiede größer als 2^10, und von 10.000.000/2^15 Unterschiede größer als 2^15, etc.

So, fügen wir, wie viele bits es dauern wird, vertreten unsere die Folge. Wir haben für 1.000.000*6 + roundup(10,000,000/2^5)*6+roundup(10,000,000/2^10)*6+roundup(10,000,000/2^15)*6+roundup(10,000,000/2^20)*4=7935479.

2^24 = 8388608. Da 8388608 > 7935479, wir sollten einfach genug Speicher haben. Wir müssen wahrscheinlich noch ein wenig bit-Speicher zum speichern der Summe wo sind beim einfügen neuer Nummern. Wir fahren dann durch die Reihenfolge, und finden Sie, wo stecken unsere neue Nummer, verringern Sie die nächste Differenz, wenn nötig, und verlagern alles nach rechts.

InformationsquelleAutor der Antwort
1

Wenn wir nicht wissen, etwas über diese zahlen, wir sind begrenzt durch folgende Einschränkungen:
- müssen wir laden Sie alle zahlen, bevor wir können, Sortieren Sie Sie,
- der Satz von zahlen ist nicht komprimierbar.
Wenn diese Annahmen halten, es gibt keinen Weg, um die Erfüllung Ihrer Aufgabe, wie Sie benötigen mindestens 26,575,425 bits von Speicher (3,321,929 bytes).

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

InformationsquelleAutor der Antwort
1

Der trick ist, stellen die algorithmen Zustand, das ist ein integer-multi-set, als komprimierten stream von "Zähler erhöhen"="+" und "output counter"="!" - Zeichen. Zum Beispiel die Menge {0,3,3,4} repräsentiert werden würde, als "!+++!!+!", gefolgt von einer beliebigen Anzahl von " + " - Zeichen. Zum ändern der multi-set-Streams, die Zeichen, halten nur eine Konstante Menge dekomprimiert, zu einer Zeit, und machen änderungen inplace vor streaming zurück in komprimierter form.

Details

Wir wissen, es sind genau 10^6 zahlen im letzten Satz, so gibt es höchstens 10^6 "! " - Zeichen. Wir wissen auch, dass unser Angebot hat die Größe 10^8, D. H. es sind maximal 10^8 " + " - Zeichen. Die Anzahl der Möglichkeiten können wir arrangieren, 10^6 "!"s unter 10^8 "+"s ist (10^8 + 10^6) choose 10^6, und so werden Sie einige Besondere Anordnung nimmt ~0.965 MiB" von Daten. Das wird eine enge Passform.

Können wir behandeln jedes Zeichen als unabhängige ohne über unser Kontingent. Es sind genau 100 mal mehr "+" als Zeichen "! "- Zeichen, die vereinfacht zu 100:1 Chancen jeder Charakter wird, ein"+", wenn wir vergessen, dass Sie abhängig sind. Quote von 100:101 entspricht ~0.08 bits pro Zeichen, für eine fast identische insgesamt ~0.965 MiB (ignorieren der Abhängigkeit hat eine Gebühr von nur ~12 bits in diesem Fall!).

Die einfachste Technik für die Speicherung von unabhängigen Zeichen mit bekannt vor Wahrscheinlichkeit ist Die Huffman-Codierung. Beachten Sie, dass wir benötigen eine unpraktikabel enge großer Baum (Eine huffman-Baum für Blöcke von 10 Zeichen hat eine Durchschnittliche Kosten pro block von etwa 2,4 bits, für eine Gesamtmenge von ~2.9 Mib. Ein huffman-Baum für Blöcke von 20 Zeichen hat eine Durchschnittliche Kosten pro block von 3 bits, die insgesamt ~1.8 MiB. Wir sind wahrscheinlich zu benötigen, einen block der Größe in der Größenordnung von hundert, was bedeutet, mehrere Knoten in unserem Baum, als alle computer-Ausrüstung, die es je gegeben hat, speichern können.). Allerdings, ROM ist technisch "frei" nach den problem-und praxisgerechte Lösungen, die die Vorteile der Regelmäßigkeit in der Struktur Aussehen wird, im wesentlichen gleich.

Pseudo-code
- Einen ausreichend großen huffman-Baum (oder ähnliche block-by-block-Kompressions-data), die im ROM gespeichert
- Beginnen mit einer komprimierten string von 10^8 " + " - Zeichen.
- Zum einfügen der Zahl N ist, Strom aus den komprimierten string bis N " + " - Zeichen Weg Vergangenheit fügen Sie ein "!". Stream die stärker komprimiert string zurück, gegenüber dem Vorjahr ein, wie Sie gehen, halten Sie eine Konstante Menge von gepufferten Blöcken zu vermeiden, über - /unter-läuft.
- Wiederholen eine million mal: [Eingabe-stream entpacken>einfügen - >komprimieren], dann dekomprimiert die Ausgabe
InformationsquelleAutor der Antwort
0

Während der den stream empfangen führen Sie diese Schritte.

1. Satz einige vernünftige chunk-Größe

Pseudo-Code Idee:
1. Würde der erste Schritt sein, um herauszufinden, alle Duplikate und kleben Sie diese in einem Wörterbuch mit der Anzahl und entfernen Sie Sie.
2. Der Dritte Schritt wäre die Anzahl, die vorhanden sind in der Reihenfolge Ihrer algorithmischen Schritte und legen Sie Sie in Schalter spezielle Wörterbücher mit der ersten Zahl und Ihrem Schritt, wie n, n+1 ... ,n+2, 2n, 2n+1, 2n+2...
3. Beginnen zu komprimieren, die in Blöcken einige vernünftige Reichweiten-Zahl wie jede 1000 oder je 10000 die restlichen zahlen, die erscheinen weniger oft zu wiederholen.
4. Dekomprimieren, die Reichweite, wenn eine Zahl gefunden wird, und fügen Sie es auf den Bereich und lassen Sie es unkomprimiert für eine Weile.
5. Ansonsten nur hinzufügen, dass die Zahl in ein byte[chunkSize]
Weiterhin die ersten 4 Schritte, während Sie den stream empfangen.
Der Letzte Schritt wäre zu Versagen, wenn Sie überschritten Speicher oder starten Sie die Ausgabe des Ergebnis sobald alle Daten gesammelt, die von Anfang an um die Sortierung der Bereiche und spuckte die Ergebnisse in Ordnung und Dekomprimieren diejenigen um, die dekomprimiert werden müssen, und Sortieren Sie Sie, wenn Sie Sie bekommen.

InformationsquelleAutor der Antwort
-1

Dies wird vorausgesetzt, base 10 und beispielsweise der Speicher mit 8-bit-Wörtern:
Speicher Karte die gesamte Reihe von zahlen mit 3 bit-Schritten. Die Ersten 3 bits entspräche der Zahl 0. Der zweite Satz von 3 bit würde die Karte Nummer 1. Drei hunderttausendstel Satz von 3-bit würde die Karte, um die Anzahl 300k. Wiederholen Sie dies, bis Sie zugeordnet haben alle der 8-stellige zahlen. Dies würde insgesamt 375k bytes insgesamt, wenn der Speicher-Bereich wurde kontinuierlich.

Dem 1. bit aus dem 3 markieren würde die Anwesenheit von der Reihe. Die nächsten 2 bits geben würde, die Menge der Duplikate, die dargestellt werden können, in bytes(1..3) wenn keine, Duplikate Feld wäre 00. Es wird eine zweite Liste, die verwendet einen Zähler, der inkrementiert jedes mal, wenn ein 3-bit-Feld ist markiert als ein Duplikat. Wenn es markiert mit 1 es wird eine einzelne bit-Sortiment zählen Sie die Anzahl der Duplikate, die es hat. 8 bits darstellen kann eine Reihe 255.

Als ich ' m verlieren verfolgen der Gedanken. Die zweite Liste wird verfolgen, wie viele Duplikate für jede Zahl. wenn die 255th Zahl hat eine doppelte und ist die erste Zahl zu haben, ein Duplikat es der index in der Liste ist 0. Wenn 23,543 ist die zweite Zahl zu haben, ein Duplikat ist es index 1. Waschen,steigen und wiederholen.

Worst-case-Szenario ist, haben Sie 500k zahlen mit Duplikaten. Dies kann dargestellt werden durch ein einzelnes byte(seit 1 passt einfach). Also 375kB(im Idealfall) + 500kB bytes ist in der Nähe .875MB. Je nach Prozessor dies sollte genügend Platz übrig für Zeiger,Indizierung und all die anderen Dinge, die Spaß machen.

Wenn Sie eine einzelne Zahl, 1M Duplikate. alles, was Sie brauchen, ist 3 bytes, da Sie Ihre begrenzten 1M zahlen, das ist alles, was Sie haben Grund zur Sorge. Also auf deine zweite Liste, es werden nur 3 byes mit dem Gesamtbetrag.

Nun zum spaßigen Teil. Die zweite Liste muss sortiert sein, für jede neue Zahl, die kommt. In der 3-bit-Feld für die letzten 2 sind die Anzahl der bytes enthält, die die Anzahl der Duplikate. Da die zweite Liste wird voraussichtlich in Ordnung zu sein, wird es brauchen, um sortiert werden. Da die Menge der bytes, die variieren können. Denke insertion sort!

Diese halten würde, die Menge von Zeigern und Dinge, die Sie brauchen, um Schrittweite auf ein minimum, so sollten Sie haben ein wenig Flexibilität mit vielleicht 250k bytes Links.

GoodLuck! Das hört sich so viel eleganter in meinem Kopf...

InformationsquelleAutor der Antwort

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.