Mam komputer z 1 MB pamięci RAM i bez innych lokalnych pamięci. Muszę go użyć, aby zaakceptować 1 milion 8 cyfr po przecinku przez połączenie TCP, posortować je, a następnie wysłać posortowaną listę przez inne połączenie TCP.

Lista liczb może zawierać duplikaty, których nie wolno mi odrzucić. Kod zostanie umieszczony w pamięci ROM, więc nie muszę odejmować wielkości mojego kodu od 1 MB. Mam już kod do sterowania portem Ethernet i obsługi połączeń TCP / IP, a dane stanu wymagają 2 KB, w tym bufora 1 KB, przez który kod będzie odczytywał i zapisywał dane. Czy istnieje rozwiązanie tego problemu?

Źródła pytań i odpowiedzi:

slashdot.org

cleaton.net

Jest jedna raczej podstępna sztuczka, o której dotychczas nie wspomniano. Zakładamy, że nie masz dodatkowego sposobu przechowywania danych, ale nie jest to do końca prawdą.

Jednym ze sposobów rozwiązania problemu jest zrobienie następującej okropnej rzeczy, której nikt nie powinien podejmować w żadnym wypadku: Użyj ruchu sieciowego do przechowywania danych. I nie, nie mam na myśli NAS.

Liczby można sortować za pomocą zaledwie kilku bajtów pamięci RAM w następujący sposób:

• Najpierw weź 2 zmienne: COUNTERi VALUE.
• Najpierw ustaw wszystkie rejestry na 0;
• Za każdym razem, gdy otrzymasz liczbę całkowitą I, przyrost COUNTERi ustaw VALUEna max(VALUE, I);
• Następnie wyślij Ido routera pakiet żądania echa ICMP z zestawem danych . WymazaćI i powtórz.
• Za każdym razem, gdy otrzymujesz zwrócony pakiet ICMP, po prostu wyodrębniasz liczbę całkowitą i wysyłasz ją z powrotem w kolejnym żądaniu echa. To powoduje powstanie ogromnej liczby żądań ICMP przewijających się do tyłu i do przodu, zawierających liczby całkowite.

Po COUNTERosiągnięciu 1000000masz wszystkie wartości zapisane w nieprzerwanym strumieniu żądań ICMP, a VALUEteraz zawiera maksymalną liczbę całkowitą. Wybierz trochę threshold T >> 1000000. Ustawiony COUNTERna zero. Za każdym razem, gdy otrzymujesz pakiet ICMP, zwiększaj COUNTERi wysyłaj zawartą liczbę całkowitą z Ipowrotem w innym żądaniu echa, chyba że I=VALUEw takim przypadku przekaż go do miejsca docelowego dla posortowanych liczb całkowitych. Raz COUNTER=Tzmniejsz VALUEo 1, zresetuj COUNTERdo zera i powtórz. Kiedy VALUEosiągnie zero, powinieneś przesłać wszystkie liczby całkowite, od największej do najmniejszej, do miejsca docelowego i użyłeś tylko około 47 bitów pamięci RAM dla dwóch trwałych zmiennych (i jakiejkolwiek niewielkiej ilości potrzebnej do wartości tymczasowych).

Wiem, że to okropne i wiem, że mogą istnieć różnego rodzaju praktyczne problemy, ale pomyślałem, że to może wywołać u niektórych śmiech lub przynajmniej przerazić.

Oto działający kod C ++, który rozwiązuje problem.

Dowód spełnienia ograniczeń pamięci:

Redaktor: Nie ma dowodu na maksymalne wymagania pamięci oferowane przez autora ani w tym poście, ani na jego blogach. Ponieważ liczba bitów potrzebna do zakodowania wartości zależy od wcześniej zakodowanych wartości, taki dowód prawdopodobnie nie jest trywialny. Autor zauważa, że ​​największy zakodowany rozmiar, na jaki mógł natknąć się empirycznie 1011732, wybrał rozmiar bufora 1013000arbitralnie.

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

    ...

Razem te dwie tablice zajmują 1045000 bajtów pamięci. Pozostawia to 1048576 - 1045000 - 2 × 1024 = 1528 bajtów dla pozostałych zmiennych i przestrzeni stosu.

Działa za około 23 sekund na moim Xeon W3520. Możesz sprawdzić, czy program działa przy użyciu następującego skryptu Python, przyjmując nazwę programu 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!')

Szczegółowe wyjaśnienie algorytmu można znaleźć w następującej serii postów:

• 1 MB Wyjaśnienie sortowania
• Kodowanie arytmetyczne i problem z sortowaniem 1 MB
• Kodowanie arytmetyczne za pomocą matematyki stałoprzecinkowej

Proszę zobaczyć pierwszą poprawną odpowiedź lub późniejszą odpowiedź z kodowaniem arytmetycznym . Poniżej znajdziesz zabawne, ale nie w 100% kuloodporne rozwiązanie.

To dość interesujące zadanie, a oto inne rozwiązanie. Mam nadzieję, że ktoś uzna ten wynik za użyteczny (lub przynajmniej interesujący).

Etap 1: Wstępna struktura danych, podejście zgrubne, podstawowe wyniki

Zróbmy prostą matematykę: mamy 1M (1048576 bajtów) pamięci RAM początkowo dostępnych do przechowywania 10 ^ 6 8 cyfr po przecinku. [0; 99999999]. Dlatego do przechowywania jednej liczby potrzebnych jest 27 bitów (przy założeniu, że zostaną użyte liczby bez znaku). Zatem do przechowywania surowego strumienia potrzebne będzie ~ 3,5 mln pamięci RAM. Ktoś już powiedział, że nie wydaje się to możliwe, ale powiedziałbym, że zadanie można rozwiązać, jeśli dane wejściowe są „wystarczająco dobre”. Zasadniczo chodzi o to, aby skompresować dane wejściowe ze współczynnikiem kompresji 0,29 lub wyższym i przeprowadzić sortowanie we właściwy sposób.

Najpierw rozwiążmy problem kompresji. Istnieje już kilka odpowiednich testów:

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

„Przeprowadziłem test, aby skompresować milion kolejnych liczb całkowitych przy użyciu różnych form kompresji. Wyniki są następujące:”

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Wygląda na to, że LZMA ( algorytm łańcuchowy Lempel – Ziv – Markov ) jest dobrym wyborem, aby kontynuować. Przygotowałem prosty PoC, ale wciąż jest kilka szczegółów do podkreślenia:

1. Pamięć jest ograniczona, dlatego pomysł polega na wstępnym zapisaniu liczb i użyciu skompresowanych segmentów (rozmiar dynamiczny) jako tymczasowego magazynu
2. Łatwiej jest osiągnąć lepszy współczynnik kompresji przy wstępnie zapisanych danych, więc dla każdego segmentu istnieje bufor statyczny (liczby z bufora należy posortować przed LZMA)
3. Każde wiadro ma określony zakres, więc ostateczne sortowanie można wykonać dla każdego wiadra osobno
4. Rozmiar segmentu można odpowiednio ustawić, dzięki czemu będzie wystarczająca ilość pamięci do dekompresji przechowywanych danych i wykonania ostatecznego sortowania dla każdego segmentu osobno

Uwaga: załączony kod to POC , nie można go użyć jako ostatecznego rozwiązania, po prostu demonstruje on pomysł użycia kilku mniejszych buforów do przechowywania wstępnie ustawionych liczb w optymalny sposób (ewentualnie skompresowany). LZMA nie jest proponowane jako ostateczne rozwiązanie. Jest używany jako najszybszy możliwy sposób wprowadzenia kompresji do tego PoC.

Zobacz kod PoC poniżej (pamiętaj, że to tylko wersja demonstracyjna, aby go skompilować potrzebna będzie LZMA-Java ):

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

W przypadku liczb losowych daje następujące wyniki:

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

W przypadku prostej sekwencji rosnącej (używane jest jedno wiadro):

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

EDYTOWAĆ

Wniosek:

1. Nie próbuj oszukiwać Natury
2. Użyj prostszej kompresji przy mniejszym zużyciu pamięci
3. Naprawdę potrzebne są dodatkowe wskazówki. Wspólne rozwiązanie kuloodporne nie wydaje się możliwe.

Etap 2: Ulepszona kompresja, końcowy wniosek

Jak już wspomniano w poprzednim rozdziale, można zastosować dowolną odpowiednią technikę kompresji. Pozbądźmy się LZMA na rzecz prostszego i lepszego (jeśli to możliwe) podejścia. Istnieje wiele dobrych rozwiązań, w tym kodowanie arytmetyczne , drzewo Radix itp.

W każdym razie prosty, ale użyteczny schemat kodowania będzie bardziej ilustracyjny niż kolejna zewnętrzna biblioteka, zapewniająca sprytny algorytm. Rzeczywiste rozwiązanie jest dość proste: ponieważ istnieją segmenty z częściowo posortowanymi danymi, zamiast liczb można stosować delty.

Losowy test wejściowy pokazuje nieco lepsze wyniki:

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

Przykładowy kod

  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;
}

Uwaga: to podejście:

1. nie zużywa dużo pamięci
2. działa ze strumieniami
3. zapewnia niezłe wyniki

Pełny kod można znaleźć tutaj , implementacje BinaryInput i BinaryOutput można znaleźć tutaj

Ostateczna konkluzja

Bez ostatecznego wniosku :) Czasami naprawdę dobrym pomysłem jest przejście o jeden poziom wyżej i przejrzenie zadania z meta-poziomu .

Przyjemnie było spędzić trochę czasu z tym zadaniem. BTW, poniżej znajduje się wiele interesujących odpowiedzi. Dziękujemy za uwagę i życzymy udanego kodowania.

Rozwiązanie jest możliwe tylko ze względu na różnicę między 1 megabajtem a 1 milionem bajtów. Istnieje około 2 do potęgi 8093729.5 różnych sposobów wyboru 1 miliona 8-cyfrowych liczb z dozwolonymi duplikatami i zamówienia nieistotnego, więc maszyna z zaledwie 1 milionem bajtów RAM nie ma wystarczającej liczby stanów, aby reprezentować wszystkie możliwości. Ale 1M (mniej 2k dla TCP / IP) to 1022 * 1024 * 8 = 8372224 bitów, więc rozwiązanie jest możliwe.

Część 1, wstępne rozwiązanie

To podejście wymaga nieco więcej niż 1 mln, dopracuję je, aby pasowało do 1 mln później.

Będę przechowywać zwięzłą posortowaną listę liczb z zakresu od 0 do 99999999 jako sekwencję list podrzędnych liczb 7-bitowych. Pierwsza lista zawiera numery od 0 do 127, druga lista zawiera liczby od 128 do 255, itd. 100000000/128 to dokładnie 781250, więc 781250 takie listy będą potrzebne.

Każda podlista składa się z 2-bitowego nagłówka podlisty, po którym następuje treść podlisty. Ciało podlisty zajmuje 7 bitów na wpis podlisty. Wszystkie listy podrzędne są łączone razem, a format umożliwia określenie, gdzie kończy się jedna lista, a zaczyna druga. Całkowita pamięć potrzebna do wypełnienia listy wynosi 2 * 781250 + 7 * 1000000 = 8562500 bitów, co stanowi około 1.021 megabajtów.

4 możliwe wartości nagłówka listy podrzędnej to:

00 Pusta podlista, nic nie wynika.

01 Singleton, na liście podrzędnej jest tylko jeden wpis i zawiera go kolejnych 7 bitów.

10 Podlista zawiera co najmniej 2 różne liczby. Wpisy są przechowywane w kolejności malejącej, z tym wyjątkiem, że ostatni wpis jest mniejszy lub równy pierwszemu. Pozwala to zidentyfikować koniec podlisty. Na przykład liczby 2,4,6 byłyby przechowywane jako (4,6,2). Liczby 2,2,3,4,4 będą przechowywane jako (2,3,4,4,2).

11 Podlista zawiera 2 lub więcej powtórzeń jednego numeru. Kolejne 7 bitów podaje liczbę. Następnie przychodzi zero lub więcej 7-bitowych wpisów o wartości 1, a następnie 7-bitowych wpisów o wartości 0. Długość treści listy podrzędnej określa liczbę powtórzeń. Na przykład liczby 12,12 byłyby przechowywane jako (12,0), liczby 12,12,12 byłyby przechowywane jako (12,1,0), 12,12,12,12 to (12,1 , 1,0) i tak dalej.

Zaczynam od pustej listy, czytam kilka liczb i przechowuję je jako 32-bitowe liczby całkowite, sortuję nowe liczby na miejscu (prawdopodobnie za pomocą heapsortu), a następnie łączę je w nową zwartą listę posortowaną. Powtarzaj tę czynność, aż nie będzie już więcej liczb do odczytania, a następnie ponownie przejrzyj listę kompaktową, aby wygenerować wynik.

Poniższy wiersz przedstawia pamięć tuż przed rozpoczęciem operacji scalania listy. „O” to region przechowujący posortowane 32-bitowe liczby całkowite. „X” to region zawierający starą listę kompaktową. Znaki „=” to pomieszczenie rozszerzeń dla listy kompaktowej, 7 bitów na każdą liczbę całkowitą w „O”. „Z” to inne losowe koszty ogólne.

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

Procedura scalania rozpoczyna się od skrajnego lewego „O” i skrajnego lewego „X” i zaczyna pisać od skrajnego lewego „=”. Wskaźnik zapisu nie łapie wskaźnika odczytu listy kompaktowej, dopóki wszystkie nowe liczby całkowite nie zostaną scalone, ponieważ oba wskaźniki przesuwają 2 bity dla każdej podlisty i 7 bitów dla każdego wpisu na starej liście zwartej, a jest wystarczająco dużo miejsca dla 7-bitowe wpisy dla nowych numerów.

Część 2, wbijając go w 1M

Aby wycisnąć powyższe rozwiązanie do 1M, muszę uczynić format listy kompaktowej nieco bardziej kompaktowym. Pozbędę się jednego z typów listy podrzędnej, aby były tylko 3 różne możliwe wartości nagłówka listy podrzędnej. Następnie mogę użyć „00”, „01” i „1” jako wartości nagłówka listy podrzędnej i zapisać kilka bitów. Rodzaje podlisty to:

Pusta lista, nic nie wynika.

B Singleton, na liście podrzędnej jest tylko jeden wpis i zawiera go kolejnych 7 bitów.

C Podlista zawiera co najmniej 2 różne liczby. Wpisy są przechowywane w kolejności malejącej, z tym wyjątkiem, że ostatni wpis jest mniejszy lub równy pierwszemu. Pozwala to zidentyfikować koniec podlisty. Na przykład liczby 2,4,6 byłyby przechowywane jako (4,6,2). Liczby 2,2,3,4,4 będą przechowywane jako (2,3,4,4,2).

D Podlista składa się z 2 lub więcej powtórzeń jednego numeru.

Moje 3 nagłówki podlisty to „A”, „B” i „C”, więc potrzebuję sposobu na reprezentowanie podlist typu D.

Załóżmy, że mam nagłówek podlisty typu C, a po nim 3 wpisy, takie jak „C [17] [101] [58]”. Nie może to być częścią prawidłowej podlisty typu C, jak opisano powyżej, ponieważ trzeci wpis jest mniejszy niż drugi, ale większy niż pierwszy. Mogę użyć tego typu konstruktu do przedstawienia podlisty typu D. Krótko mówiąc, gdziekolwiek mam „C {00 ?????} {1 ??????} {01 ?????}” to niemożliwa podlista typu C. Użyję tego do przedstawienia podlisty składającej się z 3 lub więcej powtórzeń jednego numeru. Pierwsze dwa 7-bitowe słowa kodują liczbę (bity „N” poniżej), po których następuje zero lub więcej słów {0100001}, a następnie słowo {0100000}.

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

To tylko pozostawia listy, które zawierają dokładnie 2 powtórzenia jednego numeru. Przedstawię te z innym niemożliwym wzorcem listy typu C: „C {0 ??????} {11 ?????} {10 ?????}”. Jest dużo miejsca na 7 bitów liczby w pierwszych 2 słowach, ale ten wzór jest dłuższy niż podlista, którą reprezentuje, co sprawia, że ​​sprawy są nieco bardziej złożone. Pięć znaków zapytania na końcu można uznać za nie stanowiących części wzorca, więc mam: „C {0NNNNNN} {11N ????}} 10” jako mój wzorzec, a liczbę do powtórzenia zapisano w „N „s. To o 2 bity za długo.

Będę musiał pożyczyć 2 bity i spłacić je z 4 nieużywanych bitów w tym wzorze. Podczas czytania, po napotkaniu „C {0NNNNNN} {11N00AB} 10”, wypisz 2 wystąpienia liczby w „N”, nadpisz „10” na końcu bitami A i B i przewiń wskaźnik odczytu o 2 bitów Odczyty niszczące są odpowiednie dla tego algorytmu, ponieważ każda zwarta lista jest przeprowadzana tylko raz.

Pisząc podlistę z 2 powtórzeniami pojedynczej liczby, napisz „C {0NNNNNN} 11N00” i ustaw licznik pożyczonych bitów na 2. Przy każdym zapisie, w którym licznik pożyczonych bitów jest różny od zera, jest zmniejszany dla każdego zapisanego bitu i „10” jest zapisywane, gdy licznik osiągnie zero. Tak więc kolejne 2 zapisane bity trafią do gniazd A i B, a następnie „10” zostanie upuszczone na koniec.

Z 3 wartościami nagłówków listy podrzędnej reprezentowanymi przez „00”, „01” i „1”, mogę przypisać „1” do najpopularniejszego typu listy. Potrzebuję małej tabeli, aby zmapować wartości nagłówka listy podrzędnej na typy listy podlisty, i potrzebuję licznika wystąpień dla każdego typu listy podlisty, aby wiedzieć, jakie jest najlepsze mapowanie nagłówka listy podrzędnej.

Najgorszy przypadek minimalnej reprezentacji w pełni zaludnionej listy zwartej występuje, gdy wszystkie typy podlisty są równie popularne. W takim przypadku zapisuję 1 bit na każde 3 nagłówki listy podrzędnej, więc rozmiar listy wynosi 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 bitów. Zaokrąglanie w górę do 32-bitowej granicy słów, czyli 8302112 bitów lub 1037764 bajtów.

1M minus 2k dla stanu TCP / IP i buforów wynosi 1022 * 1024 = 1046528 bajtów, pozostawiając mi 8764 bajtów do zabawy.

Ale co z procesem zmiany mapowania nagłówków sublist? Na poniższej mapie pamięci „Z” to losowy narzut, „=” to wolne miejsce, „X” to zwarta lista.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Zacznij czytać od lewej „X” i zacznij pisać od lewej „=” i pracuj w prawo. Po zakończeniu lista kompaktowa będzie nieco krótsza i znajdzie się na niewłaściwym końcu pamięci:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Więc będę musiał przesunąć go w prawo:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

W procesie zmiany mapowania nagłówków do 1/3 nagłówków listy podrzędnej zmieni się z 1-bitowej na 2-bitową. W najgorszym przypadku będą one znajdować się na początku listy, więc zanim zacznę, będę potrzebować co najmniej 781250/3 bitów wolnego miejsca, co zabierze mnie z powrotem do wymagań dotyczących pamięci poprzedniej wersji listy kompaktowej: (

Aby obejść ten problem, podzielę 781250 podlist na 10 grup podlist po 78125 podlist. Każda grupa ma własne niezależne mapowanie nagłówka listy podrzędnej. Używając liter od A do J dla grup:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Każda grupa listy podrzędnej kurczy się lub pozostaje taka sama podczas zmiany mapowania nagłówka listy podrzędnej:

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

Najgorszy przypadek tymczasowego rozszerzenia grupy listy podrzędnej podczas zmiany mapowania wynosi 78125/3 = 26042 bitów, poniżej 4k. Jeśli pozwolę 4k plus 1037764 bajtów na w pełni wypełnioną listę kompaktową, to pozostawi mi 8764 - 4096 = 4668 bajtów dla „Z” na mapie pamięci.

To powinno wystarczyć dla 10 tabel odwzorowania nagłówków podlisty, 30 wystąpień nagłówka podlisty i pozostałych kilku liczników, wskaźników i małych buforów, których potrzebuję, i przestrzeni, której użyłem bez zauważenia, na przykład przestrzeni stosu dla adresów zwrotnych wywołań funkcji i zmienne lokalne.

Część 3, ile czasu zajmie uruchomienie?

W przypadku pustej listy kompaktowej 1-bitowy nagłówek listy zostanie użyty do pustej listy podrzędnej, a początkowy rozmiar listy będzie wynosił 781250 bitów. W najgorszym przypadku lista powiększa się o 8 bitów na każdą dodaną liczbę, więc 32 + 8 = 40 bitów wolnego miejsca jest potrzebnych do umieszczenia każdej z 32-bitowych liczb na górze bufora listy, a następnie posortowania i scalenia. W najgorszym przypadku zmiana mapowania nagłówka listy podrzędnej powoduje użycie miejsca 2 * 781250 + 7 * wpisów - 781250/3 bitów.

Przy polityce zmiany mapowania nagłówka listy podrzędnej po co piątym scaleniu, gdy na liście znajduje się co najmniej 800 000 liczb, najgorszy przypadek wymagałby w sumie około 30 mln czynności związanych z czytaniem i pisaniem list.

Źródło:

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

Odpowiedź Gilmanowa jest bardzo błędna w swoich założeniach. Zaczyna spekulować w oparciu o bezcelową miarę miliona kolejnych liczb całkowitych. To oznacza brak luk. Te przypadkowe luki, jakkolwiek małe, naprawdę sprawiają, że jest to zły pomysł.

Spróbuj sam. Zbierz 1 milion losowych liczb całkowitych 27-bitowych, posortuj je, skompresuj za pomocą 7-Zip , xz, jakiejkolwiek LZMA, jakiej chcesz. Wynik to ponad 1,5 MB. Założeniem na górze jest kompresja kolejnych liczb. Nawet kodowanie delta tego wynosi ponad 1,1 MB . I nie wspominając o tym, że do kompresji używa ponad 100 MB pamięci RAM. Więc nawet skompresowane liczby całkowite nie pasują do problemu i nie wspominając o zużyciu pamięci RAM w czasie wykonywania .

Zasmuca mnie to, jak ludzie opowiadają się za ładną grafiką i racjonalizacją.

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

}

Teraz skompresuj ints.bin za pomocą 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

Myślę, że jednym ze sposobów myślenia o tym jest z punktu widzenia kombinatoryki: ile jest możliwych kombinacji uporządkowanych liczb? Jeśli podamy kombinację 0,0,0, ...., 0 kod 0, a 0,0,0, ..., 1 kod 1, a 99999999, 99999999, ... 99999999 kod N, co to jest N? Innymi słowy, jak duża jest przestrzeń wynikowa?

Cóż, jednym ze sposobów myślenia o tym jest zauważenie, że jest to sprzeczne z problemem znalezienia liczby ścieżek monotonicznych w siatce N x M, gdzie N = 1 000 000, a M = 100 000 000. Innymi słowy, jeśli masz siatkę o szerokości 1 000 000 i wysokości 100 000 000, ile jest najkrótszych ścieżek od lewego dolnego do prawego górnego rogu? Najkrótsze ścieżki oczywiście wymagają jedynie ruchu w prawo lub w górę (jeśli miałbyś przejść w dół lub w lewo, cofnąłbyś wcześniej osiągnięty postęp). Aby zobaczyć, w jaki sposób jest to problem naszego problemu sortowania liczb, wykonaj następujące czynności:

Możesz sobie wyobrazić dowolną poziomą odnogę na naszej ścieżce jako liczbę w naszym porządku, w której położenie Y odnogi reprezentuje wartość.

Więc jeśli ścieżka po prostu przesuwa się w prawo aż do końca, a następnie przeskakuje na samą górę, co odpowiada uporządkowaniu 0,0,0, ..., 0. jeśli zamiast tego zaczyna się od skoku na samą górę, a następnie przesuwa się w prawo 1 000 000 razy, co odpowiada 99999999,9999999999, ..., 99999999. Ścieżka, w której przesuwa się raz w prawo, potem w górę, potem w prawo , potem w górę itp. do samego końca (wtedy koniecznie przeskakuje aż do góry), jest równoważne 0,1,2,3, ..., 999999.

Na szczęście dla nas ten problem został już rozwiązany, taka siatka ma (N + M) Wybierz ścieżki (M):

(1 000 000 + 100 000 000) Wybierz (100 000 000) ~ = 2,27 * 10 ^ 2436455

N równa się zatem 2,27 * 10 ^ 2436455, a zatem kod 0 reprezentuje 0,0,0, ..., 0, a kod 2,27 * 10 ^ 2436455, a pewna zmiana reprezentuje 99999999,99999999, ..., 99999999.

Aby zapisać wszystkie liczby od 0 do 2,27 * 10 ^ 2436455, potrzebujesz lg2 (2,27 * 10 ^ 2436455) = 8,0937 * 10 ^ 6 bitów.

1 megabajt = 8388608 bitów> 8093700 bitów

Wygląda więc na to, że przynajmniej mamy wystarczająco dużo miejsca do przechowywania wyniku! Teraz oczywiście interesującym bitem jest sortowanie, gdy napływają liczby. Nie jestem pewien, czy najlepszym rozwiązaniem jest 294908 bitów. Wyobrażam sobie, że interesującą techniką byłoby zakładanie w każdym punkcie, że to jest całe zamawianie, znajdowanie kodu dla tego zamawiania, a następnie otrzymywanie nowego numeru wracając i aktualizując poprzedni kod. Fala dłoni Fala dłoni.

Moje sugestie wiele zawdzięczają rozwiązaniu Dana

Po pierwsze zakładam, że rozwiązanie musi obsłużyć wszystkie możliwe listy danych wejściowych. Myślę, że popularne odpowiedzi nie popierają tego założenia (który IMO jest wielkim błędem).

Wiadomo, że żadna forma bezstratnej kompresji nie zmniejszy rozmiaru wszystkich danych wejściowych.

Wszystkie popularne odpowiedzi zakładają, że będą w stanie zastosować kompresję na tyle efektywną, aby zapewnić im dodatkową przestrzeń. W rzeczywistości fragment dodatkowej przestrzeni wystarczająco dużej, aby pomieścić część częściowo wypełnionej listy w nieskompresowanej formie i pozwolić im na wykonanie operacji sortowania. To tylko złe założenie.

W przypadku takiego rozwiązania każdy, kto ma wiedzę na temat sposobu kompresji, będzie w stanie zaprojektować dane wejściowe, które nie będą dobrze kompresowane dla tego schematu, a „rozwiązanie” najprawdopodobniej ulegnie awarii z powodu braku miejsca.

Zamiast tego przyjmuję podejście matematyczne. Nasze możliwe wyniki to wszystkie listy długości LEN składające się z elementów z zakresu 0..MAX. Tutaj LEN wynosi 1 000 000, a nasz MAX wynosi 100 000 000.

W przypadku dowolnego LEN i MAX ilość bitów potrzebnych do zakodowania tego stanu wynosi:

Log2 (MAX Multichoose LEN)

Tak więc dla naszych liczb, po zakończeniu pobierania i sortowania, będziemy potrzebować co najmniej Log2 (100 000 000 MC 1 000 000) bitów, aby zapisać nasz wynik w sposób, który będzie w stanie jednoznacznie rozróżnić wszystkie możliwe wyniki.

To jest ~ = 988kb . Mamy więc wystarczająco dużo miejsca, aby utrzymać nasz wynik. Z tego punktu widzenia jest to możliwe.

[Usunięto bezsensowne włóczenie się, skoro istnieją lepsze przykłady ...]

Najlepsza odpowiedź jest tutaj .

Inna dobra odpowiedź jest tutaj i zasadniczo używa sortowania wstawiania jako funkcji do rozszerzenia listy o jeden element (buforuje kilka elementów i sortuje wstępnie, aby umożliwić wstawianie więcej niż jednego na raz, oszczędza to trochę czasu). używa też ładnego kompaktowego kodowania stanu, segmentów siedmiobitowych delt

Załóżmy, że to zadanie jest możliwe. Tuż przed wyjściem pojawi się w pamięci reprezentacja miliona posortowanych liczb. Ile jest takich różnych reprezentacji? Ponieważ mogą się powtarzać liczby, nie możemy użyć nCr (wybierz), ale istnieje operacja o nazwie multichoose, która działa na multisets .

• Istnieje 2,2e2436455 sposobów na wybranie miliona liczb z zakresu 0..99,999,999.
• Wymaga to 8 093 730 bitów do przedstawienia każdej możliwej kombinacji, czyli 1 011,717 bajtów.

Teoretycznie może to być możliwe, jeśli uda się wymyślić rozsądną (wystarczającą) reprezentację posortowanej listy liczb. Na przykład szalona reprezentacja może wymagać tabeli wyszukiwania 10 MB lub tysięcy wierszy kodu.

Jeśli jednak „1M RAM” oznacza milion bajtów, to wyraźnie nie ma wystarczającej ilości miejsca. Fakt, że 5% więcej pamięci sprawia, że ​​teoretycznie jest to możliwe, sugeruje mi, że reprezentacja będzie musiała być BARDZO wydajna i prawdopodobnie nie zdrowa psychicznie.

(Moja pierwotna odpowiedź była zła, przepraszam za złą matematykę, patrz poniżej przerwy).

Co powiesz na to?

Pierwsze 27 bitów przechowuje najmniejszą liczbę, którą widziałeś, a następnie różnicę do następnej liczby, kodowanej w następujący sposób: 5 bitów do przechowywania liczby bitów użytych do przechowywania różnicy, a następnie różnicy. Użyj 00000, aby wskazać, że ponownie widziałeś ten numer.

Działa to, ponieważ w miarę wstawiania większej liczby liczb średnia różnica między liczbami maleje, więc do zapisania różnicy używasz mniejszej liczby bitów, gdy dodajesz więcej liczb. Wierzę, że to się nazywa lista delta.

Najgorszym przypadkiem, o którym myślę, są wszystkie liczby równomiernie rozmieszczone (o 100), np. Zakładając, że 0 jest pierwszą liczbą:

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

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

Reddit na ratunek!

Gdyby wszystko, co trzeba było zrobić, to posortować je, ten problem byłby łatwy. Zapamiętanie liczb, które widziałeś, zajmuje 122 000 (1 milion bitów) (0 bit przy włączeniu 0, 2300 bit przy zarejestrowaniu 2300 itd.

Odczytujesz liczby, przechowujesz je w polu bitowym, a następnie przesuwasz bity, zachowując zliczanie.

ALE musisz pamiętać, ile widziałeś. Zainspirowała mnie powyższa odpowiedź sublistyczna, aby wymyślić ten schemat:

Zamiast jednego bitu użyj 2 lub 27 bitów:

• 00 oznacza, że ​​nie widziałeś numeru.
• 01 oznacza, że ​​widziałeś to raz
• 1 oznacza, że ​​to widziałeś, a kolejne 26 bitów jest liczbą, ile razy.

Myślę, że to działa: jeśli nie ma duplikatów, masz listę 244k. W najgorszym przypadku widzisz każdą liczbę dwa razy (jeśli zobaczysz jedną liczbę trzy razy, skraca to resztę listy), co oznacza, że ​​widziałeś 50 000 więcej niż jeden raz i widziałeś 950 000 przedmiotów 0 lub 1 razy.

50 000 * 27 + 950 000 * 2 = 396,7 tys.

Możesz wprowadzić dalsze ulepszenia, jeśli użyjesz następującego kodowania:

0 oznacza, że ​​nie widziałeś liczby 10 oznacza, że ​​widziałeś ją raz 11 to sposób na liczenie

Co spowoduje średnio 280,7 tys. Pamięci.

EDYCJA: moja matematyka w niedzielę rano była błędna.

W najgorszym przypadku widzimy dwa razy 500 000 liczb, więc matematyka staje się:

500 000 * 27 + 500 000 * 2 = 1,77 mln

Alternatywne kodowanie powoduje średnie przechowywanie

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

: (

Istnieje jedno rozwiązanie tego problemu dla wszystkich możliwych danych wejściowych. Oszukać.

1. Czytaj m wartości przez TCP, gdzie m jest bliskie maksimum, które można posortować w pamięci, może n / 4.
2. Posortuj 250 000 (lub tak) liczb i wyślij je.
3. Powtórz dla pozostałych 3 kwartałów.
4. Pozwól odbiorcy scalić 4 listy liczb, które otrzymał, kiedy je przetwarza. (Nie jest to dużo wolniejsze niż używanie pojedynczej listy.)

Spróbowałbym drzewa Radix . Jeśli możesz zapisać dane w drzewie, możesz wykonać ruch w kolejności, aby przesłać dane.

Nie jestem pewien, czy zmieścisz to w 1 MB, ale myślę, że warto spróbować.

Z jakiego komputera korzystasz? Może nie mieć innej „normalnej” lokalnej pamięci, ale czy na przykład ma wideo RAM? 1 megapiksel x 32 bity na piksel (powiedzmy) jest dość zbliżony do wymaganego rozmiaru danych wejściowych.

(W dużej mierze pytam w pamięci starego komputera Acorn RISC , który mógłby „pożyczyć” VRAM, aby rozszerzyć dostępną systemową pamięć RAM, jeśli wybrałeś tryb ekranu o niskiej rozdzielczości lub niskiej głębi kolorów!). Przydało się to raczej na komputerze z zaledwie kilkoma MB normalnej pamięci RAM.

Reprezentacja drzewa radix byłaby bliska rozwiązania tego problemu, ponieważ drzewo radix korzysta z „kompresji prefiksu”. Trudno jednak wyobrazić sobie reprezentację drzewa radix, która mogłaby reprezentować pojedynczy węzeł w jednym bajcie - dwa są prawdopodobnie na granicy.

Ale niezależnie od tego, w jaki sposób dane są reprezentowane, po ich posortowaniu można je zapisać w postaci skompresowanej przedrostkiem, gdzie liczby 10, 11 i 12 byłyby reprezentowane przez, powiedzmy, 001b, 001b, 001b, co oznacza przyrost o 1 z poprzedniego numeru. Być może zatem 10101b reprezentuje przyrost o wartości 5, 1101001b o przyrost o wartości 9 itd.

Istnieje 10 ^ 6 wartości w zakresie 10 ^ 8, więc średnio jest jedna wartość na sto punktów kodowych. Zapisz odległość od N-tego punktu do (N + 1) tys. Zduplikowane wartości mają pomijanie 0. Oznacza to, że pomijanie potrzebuje średnio nieco mniej niż 7 bitów do przechowywania, więc milion z nich z przyjemnością zmieści się w naszych 8 milionach bitów pamięci.

Pomiń te muszą być zakodowane w strumieniu bitów, powiedzmy przez kodowanie Huffmana. Wstawianie polega na iterowaniu przez strumień bitów i przepisywaniu po nowej wartości. Dane wyjściowe poprzez iterację i zapisywanie wartości domyślnych. Ze względów praktycznych prawdopodobnie chce się tego dokonać, powiedzmy, 10 list 4 obejmujących 10 ^ 4 punktów kodowych (i średnio 100 wartości) każda.

Dobre drzewo Huffmana dla danych losowych można zbudować a priori, zakładając rozkład Poissona (średnia = wariancja = 100) na długości pominięć, ale rzeczywiste statystyki mogą być przechowywane na wejściu i wykorzystane do wygenerowania optymalnego drzewa, z którym można sobie poradzić przypadki patologiczne.

Mam komputer z 1 MB pamięci RAM i bez innych lokalnych pamięci

Inny sposób oszukiwania: możesz zamiast tego użyć nielokalnej (sieciowej) pamięci masowej (twoje pytanie nie wyklucza tego) i wezwać usługę sieciową, która mogłaby użyć bezpośredniego połączenia dyskowego (lub wystarczającej ilości pamięci RAM do sortowania w pamięci, ponieważ wystarczy zaakceptować liczby 1M), bez potrzeby korzystania z (co prawda niezwykle pomysłowych) już podanych rozwiązań.

To może być oszustwo, ale nie jest jasne, czy szukasz rozwiązania rzeczywistego problemu, czy łamigłówki, która zachęca do zginania reguł ... jeśli to drugie, to proste oszustwo może uzyskać lepsze wyniki niż złożony ale „oryginalne” rozwiązanie (które, jak zauważyli inni, może działać tylko w przypadku wejść ściśliwych).

Myślę, że rozwiązaniem jest połączenie technik z kodowania wideo, a mianowicie dyskretnej transformacji cosinus. W cyfrowym wideo, raczej rejestrując zmianę jasności lub koloru wideo jako regularne wartości, takie jak 110 112 115 116, każdy jest odejmowany od ostatniego (podobnie jak w przypadku kodowania długości przebiegu). 110 112 115 116 staje się 110 2 3 1. Wartości 2 3 1 wymagają mniej bitów niż oryginały.

Załóżmy więc, że tworzymy listę wartości wejściowych, gdy docierają do gniazda. Przechowujemy w każdym elemencie, nie w wartości, ale w przesunięciu w stosunku do poprzedniego. Sortujemy na bieżąco, więc przesunięcia będą tylko pozytywne. Ale przesunięcie może mieć szerokość 8 cyfr dziesiętnych, co mieści się w 3 bajtach. Każdy element nie może mieć 3 bajtów, więc musimy je spakować. Możemy użyć górnego bitu każdego bajtu jako „bitu kontynuacji”, co wskazuje, że następny bajt jest częścią liczby i 7 dolnych bitów każdego bajtu należy połączyć. zero jest ważne dla duplikatów.

Gdy lista się zapełni, liczby powinny być coraz bliżej siebie, co oznacza, że ​​średnio tylko 1 bajt służy do określenia odległości do następnej wartości. 7 bitów wartości i 1 bit przesunięcia, jeśli jest to dogodne, ale może być słaby punkt, który wymaga mniej niż 8 bitów dla wartości „kontynuuj”.

W każdym razie przeprowadziłem eksperyment. Używam generatora liczb losowych i mogę zmieścić milion posortowanych 8 cyfr po przecinku w około 1279000 bajtów. Średnia przestrzeń między każdą liczbą wynosi konsekwentnie 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);
    }
}

Możemy zagrać w stos sieciowy, aby wysłać liczby w posortowanej kolejności, zanim będziemy mieli wszystkie liczby. Jeśli wyślesz 1 mln danych, TCP / IP podzieli je na pakiety 1500 bajtów i przesyła strumieniowo w celu osiągnięcia celu. Każdy pakiet otrzyma numer sekwencyjny.

Możemy to zrobić ręcznie. Tuż przed zapełnieniem pamięci RAM możemy posortować to, co mamy i wysłać listę do celu, ale pozostawić dziury w sekwencji wokół każdej liczby. Następnie przetworz drugą 1/2 liczby w ten sam sposób, używając tych otworów w sekwencji.

Stos sieciowy na drugim końcu zgromadzi wynikowy strumień danych w kolejności sekwencji przed przekazaniem go do aplikacji.

Korzysta z sieci do sortowania scalającego. Jest to całkowity hack, ale zainspirował mnie inny hack sieciowy wymieniony wcześniej.

Google „s (złe) podejście z HN wątku. Przechowuj liczniki w stylu RLE.

Twoja początkowa struktura danych to „99999999: 0” (wszystkie zera, nie widziałem żadnych liczb), a następnie powiedzmy, że widzisz liczbę 3 866 344, więc twoja struktura danych staje się „3866343: 0,1: 1,96133654: 0” widzę, że liczby zawsze będą się zmieniać na przemian między liczbą bitów zerowych a liczbą bitów „1”, więc możesz założyć, że liczby nieparzyste reprezentują 0 bitów, a liczby parzyste 1 bit. Staje się (3866343,1,96133654)

Ich problem nie obejmuje duplikatów, ale powiedzmy, że używają „0: 1” dla duplikatów.

Duży problem nr 1: wstawianie liczb całkowitych 1M zajęłoby wieki .

Duży problem # 2: podobnie jak wszystkie rozwiązania do kodowania zwykłej delty, niektóre dystrybucje nie mogą być uwzględnione w ten sposób. Na przykład 1 m liczb całkowitych z odległościami 0:99 (np. +99 każdy). Teraz pomyśl tak samo, ale z losową odległością w zakresie 0:99 . (Uwaga: 99999999/1000000 = 99,99)

Podejście Google jest zarówno niegodne (powolne), jak i nieprawidłowe. Ale w ich obronie ich problem mógł być nieco inny.

Aby przedstawić posortowaną tablicę, można po prostu zapisać pierwszy element i różnicę między sąsiednimi elementami. W ten sposób zajmujemy się kodowaniem 10 ^ 6 elementów, których suma może wynosić maksymalnie 10 ^ 8. Nazwijmy to D . Do kodowania elementów D można użyć kodu Huffmana . Słownik kodu Huffmana można tworzyć w ruchu, a tablica aktualizowana za każdym razem, gdy nowy element jest wstawiany do posortowanej tablicy (sortowanie wstawiania). Zauważ, że gdy słownik zmienia się z powodu nowego elementu, cała tablica powinna zostać zaktualizowana, aby pasowała do nowego kodowania.

Średnia liczba bitów do kodowania każdego elementu D jest zmaksymalizowana, jeśli mamy taką samą liczbę każdego unikalnego elementu. Powiedzmy, że elementy d1 , d2 , ..., dN w D pojawiają się F razy. W takim przypadku (w najgorszym przypadku mamy zarówno 0, jak i 10 ^ 8 w sekwencji wejściowej) mamy

suma (1 < i <= N ), M . di = 10 ^ 8

gdzie

suma (1 <= i <= N ) F = 10 ^ 6 lub F = 10 ^ 6 / N, a znormalizowana częstotliwość będzie wynosić p = F / 10 ^ = 1 / N

Średnia liczba bitów będzie wynosić -log2 (1 / P ) = log2 ( N ). W tych okolicznościach powinniśmy znaleźć przypadek, który maksymalizuje N . Dzieje się tak, jeśli mamy kolejne liczby dla di zaczynające się od 0 lub , zatem , di = i -1

10 ^ 8 = suma (1 < i <= N ), M . di = suma (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2

to znaczy

N <= 201. W tym przypadku średnia liczba bitów wynosi log2 (201) = 7,6511, co oznacza, że ​​potrzebujemy około 1 bajta na element wejściowy do zapisania posortowanej tablicy. Pamiętaj, że nie oznacza to, że D nie może mieć więcej niż 201 elementów. Po prostu sieje, że jeśli elementy D są równomiernie rozmieszczone, nie może mieć więcej niż 201 unikalnych wartości.

Wykorzystałbym zachowanie retransmisji TCP.

1. Spraw, aby komponent TCP utworzył duże okno odbioru.
2. Odbierz pewną liczbę pakietów bez wysyłania dla nich ACK.
   • Przetwarzaj te w przejściach, tworząc pewną (skompresowaną) strukturę danych
   • Wyślij duplikat potwierdzenia dla ostatniego niepotrzebnego pakietu / poczekaj na przekroczenie limitu czasu retransmisji
   • Idź 2
3. Wszystkie pakiety zostały zaakceptowane

Zakłada to pewną korzyść z wiader lub wielokrotnych przejść.

Prawdopodobnie przez sortowanie partii / wiader i łączenie ich. -> drzewa radix

Użyj tej techniki, aby zaakceptować i posortować pierwsze 80%, a następnie przeczytaj ostatnie 20%, sprawdź, czy ostatnie 20% nie zawiera liczb, które wylądowałyby w pierwszych 20% najniższych liczb. Następnie wyślij 20% najniższych liczb, usuń z pamięci, zaakceptuj pozostałe 20% nowych numerów i połącz. **

Oto ogólne rozwiązanie tego rodzaju problemu:

Generalna procedura

Podjęte podejście jest następujące. Algorytm działa na pojedynczym buforze 32-bitowych słów. Wykonuje następującą procedurę w pętli:

• Zaczynamy od bufora wypełnionego skompresowanymi danymi z ostatniej iteracji. Bufor wygląda następująco

  |compressed sorted|empty|

• Oblicz maksymalną liczbę liczb, które mogą być przechowywane w tym buforze, zarówno skompresowanym, jak i nieskompresowanym. Podziel bufor na te dwie sekcje, zaczynając od miejsca na skompresowane dane, a kończąc na nieskompresowanych danych. Bufor wygląda

  |compressed sorted|empty|empty|

• Wypełnij nieskompresowaną sekcję liczbami do posortowania. Bufor wygląda

  |compressed sorted|empty|uncompressed unsorted|

• Posortuj nowe liczby za pomocą sortowania na miejscu. Bufor wygląda

  |compressed sorted|empty|uncompressed sorted|

• Wyrównaj do prawej wszystkie już skompresowane dane z poprzedniej iteracji w sekcji skompresowanej. W tym momencie bufor jest dzielony na partycje

  |empty|compressed sorted|uncompressed sorted|

• Wykonaj dekompresję-dekompresję strumieniową w sekcji skompresowanej, scalając posortowane dane w sekcji nieskompresowanej. Stara sekcja skompresowana jest zużywana w miarę wzrostu nowej sekcji skompresowanej. Bufor wygląda

  |compressed sorted|empty|

Ta procedura jest wykonywana do momentu posortowania wszystkich liczb.

Kompresja

Ten algorytm działa oczywiście tylko wtedy, gdy możliwe jest obliczenie ostatecznego rozmiaru skompresowanego nowego bufora sortującego, zanim faktycznie wiadomo, co zostanie skompresowane. Oprócz tego algorytm kompresji musi być wystarczająco dobry, aby rozwiązać rzeczywisty problem.

Zastosowane podejście składa się z trzech etapów. Po pierwsze, algorytm zawsze przechowuje posortowane sekwencje, dlatego zamiast tego możemy przechowywać wyłącznie różnice między kolejnymi wpisami. Każda różnica mieści się w zakresie [0, 99999999].

Różnice te są następnie kodowane jako jednoargumentowy strumień bitów. Wartość 1 w tym strumieniu oznacza „Dodaj 1 do akumulatora, wartość 0 oznacza„ Emituj akumulator jako wpis i zresetuj ”. Zatem różnica N będzie reprezentowana przez N 1 i jeden 0.

Suma wszystkich różnic zbliży się do maksymalnej wartości obsługiwanej przez algorytm, a liczba wszystkich różnic zbliży się do liczby wartości wstawionych do algorytmu. Oznacza to, że oczekujemy, że strumień na końcu będzie zawierał maksymalną wartość 1 i zlicza 0. To pozwala nam obliczyć oczekiwane prawdopodobieństwo 0 i 1 w strumieniu. Mianowicie prawdopodobieństwo 0 jest, count/(count+maxval)a prawdopodobieństwo 1 jest maxval/(count+maxval).

Używamy tych prawdopodobieństw do zdefiniowania arytmetycznego modelu kodowania w tym strumieniu bitów. Ten kod arytmetyczny zakoduje dokładnie te wartości 1 i 0 w optymalnej przestrzeni. Możemy obliczyć ilość miejsca zajmowanego przez ten model dla każdego pośredniego strumień jako: bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount). Aby obliczyć całkowitą wymaganą przestrzeń dla algorytmu, ustaw wartość encodedrówną ilości.

Aby nie wymagać absurdalnej liczby iteracji, do bufora można dodać niewielki narzut. Zapewni to, że algorytm będzie działał co najmniej na liczbie liczb, która mieści się w tym narzutu, ponieważ zdecydowanie największym kosztem algorytmu w czasie jest kompresja i dekompresja kodowania arytmetycznego w każdym cyklu.

Oprócz tego niezbędne są pewne koszty ogólne do przechowywania danych księgowych i obsługi niewielkich niedokładności w przybliżeniu stałego punktu algorytmu arytmetycznego kodowania, ale w sumie algorytm jest w stanie zmieścić się w 1 MB przestrzeni, nawet z dodatkowym buforem, który może zawierać 8000 liczb, w sumie 1043916 bajtów miejsca.

Optymalność

Poza zmniejszeniem (małego) obciążenia algorytmu teoretycznie uzyskanie mniejszego wyniku powinno być teoretycznie niemożliwe. Aby po prostu zawierać entropię wyniku końcowego, konieczne byłoby 1011717 bajtów. Jeśli odejmiemy dodatkowy bufor dodany dla wydajności, algorytm użył 1011916 bajtów do przechowywania wyniku końcowego + narzutu.

Gdyby strumień wejściowy można było odebrać kilka razy, byłoby to znacznie łatwiejsze (brak informacji na ten temat, pomysłu i problemu z wydajnością czasową).

Następnie moglibyśmy policzyć wartości dziesiętne. Przy zliczonych wartościach łatwo byłoby utworzyć strumień wyjściowy. Kompresuj, zliczając wartości. To zależy, co będzie w strumieniu wejściowym.

Gdyby strumień wejściowy mógł zostać odebrany kilka razy, byłoby to znacznie łatwiejsze (brak informacji na ten temat, pomysł i problem z wydajnością czasową). Następnie moglibyśmy policzyć wartości dziesiętne. Przy zliczonych wartościach łatwo byłoby utworzyć strumień wyjściowy. Kompresuj, zliczając wartości. To zależy, co będzie w strumieniu wejściowym.

Sortowanie jest tutaj drugorzędnym problemem. Jak inni powiedzieli, samo przechowywanie liczb całkowitych jest trudne i nie może działać na wszystkich wejściach , ponieważ konieczne byłoby 27 bitów na liczbę.

Podejrzewam, że: przechowuj tylko różnice między kolejnymi (posortowanymi) liczbami całkowitymi, ponieważ najprawdopodobniej będą one małe. Następnie użyj schematu kompresji, np. Z 2 dodatkowymi bitami na liczbę wejściową, aby zakodować, ile bitów jest przechowywanych. Coś jak:

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

Powinno być możliwe przechowywanie sporej liczby możliwych list danych wejściowych w ramach danego ograniczenia pamięci. Matematyka, jak wybrać schemat kompresji, aby działał na maksymalnej liczbie wejść, jest poza mną.

Mam nadzieję, że będziesz w stanie wykorzystać specyficzną dla domeny wiedzę na temat swoich danych wejściowych, aby znaleźć wystarczająco dobry schemat kompresji liczb całkowitych na tej podstawie.

Aha, a następnie robisz sortowanie wstawiania na tej posortowanej liście, gdy otrzymujesz dane.

Teraz dążymy do rzeczywistego rozwiązania, obejmującego wszystkie możliwe przypadki wprowadzania danych w zakresie 8 cyfr z zaledwie 1 MB pamięci RAM. UWAGA: prace w toku, jutro będzie kontynuowane. Stosując kodowanie arytmetyczne delt posortowanych liczb całkowitych, najgorszy przypadek dla liczb wewnętrznych 1M posortowanych kosztowałby około 7 bitów na wpis (od 99999999/1000000 to 99, a log2 (99) to prawie 7 bitów).

Ale potrzebujesz posortowanych liczb całkowitych 1m, aby uzyskać 7 lub 8 bitów! Krótsze serie miałyby większe delty, a więc więcej bitów na element.

Pracuję nad tym, aby wziąć jak najwięcej i kompresować (prawie) w miejscu. Pierwsza partia prawie 250K int potrzebowałaby co najwyżej około 9 bitów. Tak więc wynik zajmie około 275 KB. Powtórz kilka razy z pozostałą wolną pamięcią. Następnie rozpakuj-scal-w-miejscu-skompresuj te skompresowane fragmenty. To dość trudne , ale możliwe. Myślę.

Połączone listy będą coraz bliżej 7-bitowego celu na liczbę całkowitą. Ale nie wiem, ile iteracji zajmie pętla scalania. Być może 3.

Jednak niedokładność implementacji kodowania arytmetycznego może to uniemożliwić. Jeśli ten problem jest w ogóle możliwy, byłby wyjątkowo ciasny.

Jacyś wolontariusze?

Musisz tylko zapisać różnice między liczbami w sekwencji i użyć kodowania, aby skompresować te numery sekwencyjne. Mamy 2 ^ 23 bity. Podzielimy go na 6-bitowe fragmenty i pozwólmy, aby ostatni bit wskazał, czy liczba rozciąga się na kolejne 6 bitów (5 bitów plus fragment rozszerzający).

Zatem 000010 to 1, a 000100 to 2. 000001100000 to 128. Teraz uważamy, że najgorszy rzut reprezentuje różnice w sekwencji liczb do 10 000 000. Może być 10 000 000/2 ^ 5 różnic większych niż 2 ^ 5, 10 000 000/2 ^ 10 różnic większych niż 2 ^ 10 i 10 000 000/2 ^ 15 różnic większych niż 2 ^ 15 itp.

Dodajemy więc, ile bitów zajmie reprezentacja naszej sekwencji. Mamy 1 000 000 * 6 + zaokrąglenie (10 000 000/2 ^ 5) * 6 + zaokrąglenie (10 000 000/2 ^ 10) * 6 + zaokrąglenie (10 000 000/2 ^ 15) * 6 + zaokrąglenie (10 000 000/2 ^ 20) * 4 = 7935479.

2 ^ 24 = 8388608. Od 8388608> 7935479 powinniśmy z łatwością mieć wystarczającą ilość pamięci. Prawdopodobnie będziemy potrzebować kolejnej odrobiny pamięci do przechowywania sumy miejsc, gdy wstawimy nowe liczby. Następnie przechodzimy przez sekwencję i znajdujemy, gdzie wstawić nasz nowy numer, w razie potrzeby zmniejszyć kolejną różnicę i przesunąć wszystko po niej.

Jeśli nic nie wiemy o tych liczbach, ograniczają nas następujące ograniczenia:

• musimy załadować wszystkie liczby, zanim będziemy mogli je posortować,
• zbiór liczb nie jest ściśliwy.

Jeśli te założenia się utrzymają, nie ma możliwości wykonania zadania, ponieważ będziesz potrzebował co najmniej 26 545 425 bitów pamięci (3 321 929 bajtów).

Co możesz nam powiedzieć o swoich danych?

Sztuką jest reprezentowanie stanu algorytmów, który jest całkowitym zestawem liczb całkowitych, jako skompresowany strumień „licznika przyrostów” = „+” i „licznika wyjściowego” = „!” postacie. Na przykład zestaw {0,3,3,4} byłby reprezentowany jako „! +++ !! +!”, Po którym następuje dowolna liczba znaków „+”. Aby zmodyfikować zestaw wielokrotny, wysyłasz znaki strumieniowo, utrzymując tylko stałą ilość zdekompresowaną na raz, i wprowadzasz zmiany w miejscu przed przesłaniem ich z powrotem w skompresowanej formie.

Detale

Wiemy, że w ostatecznym zestawie jest dokładnie 10 ^ 6 liczb, więc jest ich najwyżej 10 ^ 6 "!" postacie. Wiemy również, że nasz zakres ma rozmiar 10 ^ 8, co oznacza, że ​​maksymalnie 10 ^ 8 znaków „+”. Liczba sposobów, w jakie możemy rozmieścić 10 ^ 6 "!" Wśród 10 ^ 8 "+" s (10^8 + 10^6) choose 10^6, a więc określenie konkretnego układu zajmuje ~ 0,965 MiB `danych. To będzie ciasno.

Możemy traktować każdą postać jako niezależną bez przekraczania naszego limitu. Istnieje dokładnie 100 razy więcej znaków „+” niż „!” znaków, co upraszcza do 100: 1, że każda postać jest „+”, jeśli zapomnimy, że są one zależne. Szanse 100: 101 odpowiadają ~ 0,08 bitów na znak , co daje prawie identyczną sumę ~ 0,965 MiB ( w tym przypadku ignorowanie zależności kosztuje tylko ~ 12 bitów !).

Najprostszą techniką przechowywania niezależnych znaków o znanym wcześniejszym prawdopodobieństwie jest kodowanie Huffmana . Zauważ, że potrzebujemy niepraktycznie dużego drzewa (drzewo huffmana dla bloków 10 znaków ma średni koszt bloku około 2,4 bity, w sumie ~ 2,9 Mib. Drzewo huffmana dla bloków 20 znaków ma średni koszt bloku około 3 bitów, co daje w sumie ~ 1,8 MiB. Prawdopodobnie będziemy potrzebować bloku wielkości rzędu stu, co oznacza więcej węzłów w naszym drzewie, niż może pomieścić cały istniejący sprzęt komputerowy. ). Jednak ROM jest technicznie „darmowy” w zależności od problemu, a praktyczne rozwiązania wykorzystujące prawidłowość drzewa będą wyglądały zasadniczo tak samo.

Pseudo kod

• Mają wystarczająco duże drzewo huffmana (lub podobne dane kompresji blok po bloku) przechowywane w pamięci ROM
• Zacznij od skompresowanego ciągu 10 ^ 8 znaków „+”.
• Aby wstawić liczbę N, przesyłaj strumieniowo skompresowany ciąg znaków, aż miną znaki „+”, a następnie wstaw znak „!”. Przesyłaj strumieniowo ponownie skompresowany ciąg znaków z powrotem na poprzedni, zachowując stałą liczbę buforowanych bloków, aby uniknąć przekroczeń / przekroczeń.
• Powtórz milion razy: [wejście, dekompresja strumienia> wstaw> skompresuj], a następnie dekompresuj do wyjścia

Mamy 1 MB - 3 KB RAM = 2 ^ 23 - 3 * 2 ^ 13 bitów = 8388608 - 24576 = 8364032 bitów dostępnych.

Otrzymujemy 10 ^ 6 liczb w zakresie 10 ^ 8. Daje to średnią lukę ~ 100 <2 ^ 7 = 128

Rozważmy najpierw prostszy problem z dość równomiernie rozmieszczonymi liczbami, gdy wszystkie odstępy są mniejsze niż 128. Jest to łatwe. Wystarczy zapisać pierwszy numer i 7-bitowe luki:

(27 bitów) + 10 ^ 6 7-bitowych liczb przerwy = wymagane 7000027 bitów

Uwaga: powtarzające się liczby mają odstępy 0.

Ale co, jeśli mamy luki większe niż 127?

OK, powiedzmy, że wielkość przerwy <127 jest reprezentowana bezpośrednio, ale po wielkości przerwy 127 następuje ciągłe 8-bitowe kodowanie rzeczywistej długości przerwy:

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

itp.

Zauważ, że ta reprezentacja liczb opisuje własną długość, dzięki czemu wiemy, kiedy zaczyna się następny numer przerwy.

Przy niewielkich odstępach <127 nadal wymaga 7000027 bitów.

Może być do (10 ^ 8) / (2 ^ 7) = 781250 23-bitowy numer przerwy, wymagający dodatkowych 16 * 781,250 = 12 500 000 bitów, co jest zbyt dużo. Potrzebujemy bardziej zwartej i powoli rosnącej reprezentacji luk.

Średni rozmiar luki wynosi 100, więc jeśli zmienimy ich kolejność na [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] i zindeksujemy to z gęstym dwójkowym kodowaniem bazowym Fibonacciego bez par zer (na przykład 11011 = 8 + 5 + 2 + 1 = 16) z liczbami ograniczonymi przez „00”, więc myślę, że możemy utrzymać wystarczająco krótką reprezentację odstępu, ale potrzebuje więcej analiz.

Podczas odbierania strumienia wykonaj następujące kroki.

1. ustawić rozsądny rozmiar porcji

Idea pseudokodu:

1. Pierwszym krokiem byłoby znalezienie wszystkich duplikatów i umieszczenie ich w słowniku wraz z ich liczbą oraz usunięcie ich.
2. Trzecim krokiem byłoby umieszczenie liczby, która istnieje w sekwencji ich kroków algorytmicznych i umieszczenie ich w licznikach specjalnych słownikach z pierwszą liczbą i ich krokiem, takich jak n, n + 1 ..., n + 2, 2n, 2n + 1, 2n + 2 ...
3. Rozpocznij kompresowanie w porcjach niektórych rozsądnych zakresów liczb, takich jak co 1000 lub kiedykolwiek 10000, a pozostałe liczby, które wydają się rzadziej powtarzać.
4. Rozpakuj ten zakres, jeśli zostanie znaleziony numer, dodaj go do zakresu i pozostaw na jakiś czas nieskompresowany.
5. W przeciwnym razie po prostu dodaj ten numer do bajtu [chunkSize]

Kontynuuj pierwsze 4 kroki podczas odbierania strumienia. Ostatnim krokiem byłoby niepowodzenie w przypadku przekroczenia pamięci lub rozpoczęcie generowania wyniku po zebraniu wszystkich danych, zaczynając sortować zakresy i wypluwać wyniki w kolejności oraz dekompresując te, które wymagają rozpakowania i sortować, gdy dojdziesz do nich.