У меня есть компьютер с 1 МБ ОЗУ и нет другого локального хранилища. Я должен использовать его, чтобы принять 1 миллион 8-значных десятичных чисел через TCP-соединение, отсортировать их, а затем отправить отсортированный список через другое TCP-соединение.

Список номеров может содержать дубликаты, которые я не должен отбрасывать. Код будет помещен в ПЗУ, поэтому мне не нужно вычитать размер моего кода из 1 МБ. У меня уже есть код для управления портом Ethernet и обработки соединений TCP / IP, и для его данных о состоянии требуется 2 КБ, включая буфер 1 КБ, через который код будет считывать и записывать данные. Есть ли решение этой проблемы?

Источники Вопроса и Ответа:

slashdot.org

cleaton.net

Есть один довольно хитрый трюк, который здесь не упомянут. Мы предполагаем, что у вас нет дополнительного способа хранения данных, но это не совсем так.

Одним из способов решения этой проблемы является выполнение следующего ужасного действия, которое никто не должен пытаться ни при каких обстоятельствах: использовать сетевой трафик для хранения данных. И нет, я не имею в виду NAS.

Вы можете отсортировать числа только с несколькими байтами оперативной памяти следующим образом:

• Сначала возьмите 2 переменные: COUNTERи VALUE.
• Сначала установите все регистры в 0;
• Каждый раз, когда вы получаете целое число I, увеличивается COUNTERи устанавливается VALUEна max(VALUE, I);
• Затем отправьте пакет эхо-запроса ICMP с данными, установленными Iна маршрутизаторе. Сотри Iи повтори.
• Каждый раз, когда вы получаете возвращенный ICMP-пакет, вы просто извлекаете целое число и отправляете его снова в другом эхо-запросе. Это приводит к огромному количеству ICMP-запросов, перемещающихся назад и вперед, содержащих целые числа.

По COUNTERдостижении 1000000все значения хранятся в непрерывном потоке ICMP-запросов и VALUEтеперь содержат максимальное целое число. Выберите немного threshold T >> 1000000. Установить COUNTERна ноль. Каждый раз, когда вы получаете пакет ICMP, увеличиваете COUNTERи отправляете содержащееся в нем целое число Iобратно в другом эхо-запросе, если только I=VALUEв этом случае не передаете его в место назначения для отсортированных целых чисел. Один раз COUNTER=Tуменьшите VALUEна 1, COUNTERобнулите и повторите. Достигнув VALUEнуля, вы должны были передать все целые числа в порядке от наибольшего до наименьшего к месту назначения и использовать только около 47 бит ОЗУ для двух постоянных переменных (и любое небольшое количество, необходимое для временных значений).

Я знаю, что это ужасно, и я знаю, что могут быть всевозможные практические проблемы, но я подумал, что это может рассмешить некоторых или хотя бы ужаснуть вас.

Вот некоторый рабочий код C ++, который решает проблему.

Доказательство того, что ограничения памяти выполнены:

Редактор: нет никаких доказательств максимальных требований к памяти, предложенных автором ни в этом посте, ни в его блогах. Поскольку количество битов, необходимых для кодирования значения, зависит от ранее закодированных значений, такое доказательство, скорее всего, нетривиально. Автор отмечает, что наибольшим кодированным размером, на который он мог наткнуться эмпирически, был 1011732, и выбрал размер буфера 1013000произвольно.

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

    ...

Вместе эти два массива занимают 1045000 байт памяти. Это оставляет 1048576 - 1045000 - 2 × 1024 = 1528 байт для оставшихся переменных и стекового пространства.

На моем Xeon W3520 он работает примерно за 23 секунды. Вы можете убедиться, что программа работает, используя следующий скрипт Python, при условии, что имя программы - 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!')

Подробное объяснение алгоритма можно найти в следующих сериях постов:

• Объяснение сортировки 1 МБ
• Арифметическое кодирование и проблема сортировки 1 МБ
• Арифметическое кодирование с использованием математики с фиксированной точкой

Пожалуйста, смотрите первый правильный ответ или более поздний ответ с арифметической кодировкой . Ниже вы можете найти забавное, но не 100% пуленепробиваемое решение.

Это довольно интересная задача, и вот другое решение. Я надеюсь, что кто-нибудь найдет результат полезным (или хотя бы интересным).

Этап 1: исходная структура данных, метод грубого сжатия, основные результаты

Давайте сделаем простую математику: у нас есть 1M (1048576 байт) оперативной памяти, изначально доступной для хранения десяти ^ 8-значных десятичных чисел. [0; 99999999]. Таким образом, для хранения одного числа необходимо 27 бит (при условии, что будут использоваться числа без знака). Таким образом, для хранения необработанного потока потребуется около 3,5 МБ ОЗУ. Кто-то уже сказал, что это не представляется возможным, но я бы сказал, что задача может быть решена, если ввод «достаточно хорош». По сути, идея заключается в сжатии входных данных с коэффициентом сжатия 0,29 или выше и правильной сортировке.

Давайте сначала решим проблему сжатия. Уже есть несколько соответствующих тестов:

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

«Я выполнил тест, чтобы сжать миллион последовательных целых чисел, используя различные формы сжатия. Результаты следующие:»

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Похоже, что LZMA ( цепной алгоритм Лемпеля – Зива – Маркова ) - хороший выбор для продолжения. Я подготовил простой PoC, но есть еще некоторые детали, которые должны быть выделены:

1. Память ограничена, поэтому идея состоит в том, чтобы предварительно отсортировать числа и использовать сжатые сегменты (динамический размер) в качестве временного хранилища.
2. С предварительно отсортированными данными легче добиться лучшего коэффициента сжатия, поэтому для каждого сегмента имеется статический буфер (числа из буфера должны быть отсортированы до LZMA)
3. Каждое ведро содержит определенный диапазон, поэтому окончательная сортировка может быть выполнена для каждого ведра в отдельности.
4. Размер сегмента может быть правильно установлен, поэтому будет достаточно памяти для распаковки сохраненных данных и выполнения окончательной сортировки для каждого сегмента отдельно.

Обратите внимание, что прикрепленный код является POC , его нельзя использовать в качестве окончательного решения, он просто демонстрирует идею использования нескольких меньших буферов для хранения предварительно отсортированных чисел некоторым оптимальным способом (возможно, сжатым). LZMA не предлагается в качестве окончательного решения. Он используется как самый быстрый способ ввести сжатие в этот PoC.

Посмотрите код PoC ниже (обратите внимание, что это просто демонстрация, для его компиляции потребуется 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);
}
}

Со случайными числами это производит следующее:

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

Для простой последовательности по возрастанию (используется одно ведро) он производит:

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

РЕДАКТИРОВАТЬ

Вывод:

1. Не пытайся обмануть Природу
2. Используйте более простое сжатие с меньшим объемом памяти
3. Некоторые дополнительные подсказки действительно необходимы. Общее пуленепробиваемое решение не представляется возможным.

Этап 2: улучшенное сжатие, окончательное заключение

Как уже упоминалось в предыдущем разделе, можно использовать любой подходящий метод сжатия. Итак, давайте избавимся от LZMA в пользу более простого и лучшего (если возможно) подхода. Есть много хороших решений, включая арифметическое кодирование , дерево Radix и т. Д.

В любом случае, простая, но полезная схема кодирования будет более наглядной, чем еще одна внешняя библиотека, предоставляющая некоторый изящный алгоритм. Реальное решение довольно простое: поскольку есть сегменты с частично отсортированными данными, вместо чисел можно использовать дельты.

Тест случайного ввода показывает немного лучшие результаты:

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

Образец кода

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

Обратите внимание, этот подход:

1. не потребляет много памяти
2. работает с потоками
3. дает не очень плохие результаты

Полный код можно найти здесь , реализации BinaryInput и BinaryOutput можно найти здесь

Окончательный вывод

Нет окончательного заключения :) Иногда очень полезно подняться на один уровень вверх и пересмотреть задачу с точки зрения метауровня .

Было весело провести некоторое время с этой задачей. Кстати, есть много интересных ответов ниже. Спасибо за внимание и удачной кодировки.

Решение возможно только из-за разницы между 1 мегабайтом и 1 миллионом байтов. Существует около 2-х вариантов для 8093729,5 различных способов выбора 1 миллиона 8-значных чисел с разрешенными дубликатами и упорядочением неважно, поэтому на машине с только 1 миллионом байтов ОЗУ недостаточно состояний, чтобы представить все возможности. Но 1М (меньше 2К для TCP / IP) составляет 1022 * 1024 * 8 = 8372224 бит, поэтому решение возможно.

Часть 1, первоначальное решение

Этот подход требует чуть больше 1М, я уточню его, чтобы вписать в 1М позже.

Я буду хранить компактный отсортированный список чисел в диапазоне от 0 до 99999999 как последовательность подсписков 7-битных чисел. Первый подсписок содержит числа от 0 до 127, второй подсписок содержит числа от 128 до 255 и т. Д. 100000000/128 - это точно 781250, поэтому потребуется 781250 таких подсписков.

Каждый подсписок состоит из 2-битного заголовка подсписка, за которым следует тело подсписка. Тело подсписка занимает 7 бит на запись подсписка. Все подсписки объединяются вместе, и формат позволяет определить, где заканчивается один подсписок и начинается следующий. Общий объем памяти, требуемый для полностью заполненного списка, составляет 2 * 781250 + 7 * 1000000 = 8562500 битов, что составляет около 1,021 МБ.

4 возможных значения заголовка подсписка:

00 Пустой подсписок, ничего не следует.

01 Singleton, в подсписке есть только одна запись, и следующие 7 бит содержат ее.

10 Подсписок содержит как минимум 2 разных числа. Записи хранятся в неубывающем порядке, за исключением того, что последняя запись меньше или равна первой. Это позволяет идентифицировать конец подсписка. Например, числа 2,4,6 будут храниться как (4,6,2). Числа 2,2,3,4,4 будут сохранены как (2,3,4,4,2).

11 Подсписок содержит 2 или более повторений одного числа. Следующие 7 бит дают номер. Затем идут ноль или более 7-битных записей со значением 1, за которыми следует 7-битная запись со значением 0. Длина тела подсписка определяет количество повторений. Например, числа 12,12 будут сохранены как (12,0), числа 12,12,12 будут сохранены как (12,1,0), 12,12,12,12 будут (12,1) 1,0) и так далее.

Я начинаю с пустого списка, читаю группу чисел и сохраняю их как 32-битные целые числа, сортирую новые числа на месте (возможно, используя heapsort), а затем объединяю их в новый компактный отсортированный список. Повторяйте до тех пор, пока не останется чисел для чтения, затем еще раз просмотрите компактный список, чтобы сгенерировать вывод.

Строка ниже представляет память непосредственно перед началом операции объединения списков. «O» - это область, в которой хранятся отсортированные 32-битные целые числа. «X» - это область, которая содержит старый компактный список. Знаки «=» - это комната расширения для компактного списка, 7 бит для каждого целого числа в «O». «Z» - это другие случайные издержки.

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

Процедура слияния начинает чтение с самого левого «O» и с самого левого «X», и начинает писать с самого левого «=». Указатель записи не перехватывает указатель чтения компактного списка до тех пор, пока все новые целые числа не будут объединены, поскольку оба указателя передвигают 2 бита для каждого подсписка и 7 битов для каждой записи в старом компактном списке, и для этого достаточно места для 7-битные записи для новых номеров.

Часть 2, втискивая его в 1М

Чтобы сжать решение выше в 1M, мне нужно сделать формат компактного списка немного более компактным. Я избавлюсь от одного из типов подсписков, так что будет только 3 различных возможных значения заголовка подсписка. Затем я могу использовать «00», «01» и «1» в качестве значений заголовка подсписка и сохранить несколько битов. Типы подсписков:

Пустой подсписок, ничего не следует.

B Singleton, в подсписке есть только одна запись, и следующие 7 битов содержат ее.

C Подсписок содержит как минимум 2 разных числа. Записи хранятся в неубывающем порядке, за исключением того, что последняя запись меньше или равна первой. Это позволяет идентифицировать конец подсписка. Например, числа 2,4,6 будут храниться как (4,6,2). Числа 2,2,3,4,4 будут сохранены как (2,3,4,4,2).

D Подсписок состоит из 2 или более повторений одного номера.

Мои 3 значения заголовка подсписка будут «A», «B» и «C», поэтому мне нужен способ представления подсписков D-типа.

Предположим, у меня есть заголовок подсписка типа C, за которым следуют 3 записи, такие как «C [17] [101] [58]». Он не может быть частью действительного подсписка C-типа, как описано выше, поскольку третья запись меньше второй, но больше первой. Я могу использовать этот тип конструкции для представления подсписка D-типа. В двух словах, где бы у меня ни было "C {00 ?????} {1 ??????} {01 ?????}", это невозможный подсписок типа C. Я буду использовать это для представления подсписка, состоящего из 3 или более повторений одного числа. Первые два 7-битных слова кодируют число («N» битов ниже), за которым следуют ноль или более {0100001} слов, за которыми следует {0100000} слово.

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

Это просто оставляет списки, которые содержат ровно 2 повторения одного числа. Я представлю те с другим невозможным шаблоном подсписка типа C: «C {0 ??????} {11 ?????} {10 ?????}». В первых двух словах достаточно места для 7 битов числа, но этот шаблон длиннее, чем представленный в нем подсписок, что несколько усложняет ситуацию. Пять знаков вопроса в конце можно считать не частью шаблона, поэтому я имею в качестве: «C {0NNNNNN} {11N ????} 10» в качестве шаблона, с числом, которое будет повторяться, сохраненным в «N» «S. Это 2 бита слишком долго.

Мне придется взять 2 бита и вернуть их из 4 неиспользованных битов в этом шаблоне. При чтении при обнаружении «C {0NNNNNN} {11N00AB} 10» выведите 2 экземпляра числа в «N», перезапишите «10» в конце битами A и B и перемотайте указатель чтения на 2 биты. Деструктивное чтение подходит для этого алгоритма, поскольку каждый компактный список просматривается только один раз.

При записи подсписка из 2 повторений одного числа запишите «C {0NNNNNN} 11N00» и установите счетчик заимствованных битов равным 2. При каждой записи, где счетчик заимствованных битов не равен нулю, он уменьшается для каждого записанного бита и «10» записывается, когда счетчик достигает нуля. Таким образом, следующие 2 записанных бита войдут в слоты A и B, а затем цифра «10» опустится в конец.

С 3 значениями заголовка подсписка, представленными «00», «01» и «1», я могу присвоить «1» наиболее популярному типу подсписка. Мне понадобится небольшая таблица для сопоставления значений заголовка подсписка с типами подсписка, и мне понадобится счетчик вхождений для каждого типа подсписка, чтобы я знал, каково лучшее отображение заголовка подсписка.

В худшем случае минимальное представление полностью заполненного компактного списка происходит, когда все типы подсписков одинаково популярны. В этом случае я сохраняю 1 бит для каждых 3 заголовков подсписка, поэтому размер списка составляет 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083,3 бит. Округление до границы слова 32 бита, то есть 8302112 бит или 1037764 байта.

1M минус 2k для состояния TCP / IP и буферов составляет 1022 * 1024 = 1046528 байт, оставляя мне 8764 байта для игры.

Но как насчет процесса изменения отображения заголовка подсписка? На приведенной ниже карте памяти «Z» - это случайные издержки, «=» - свободное место, «X» - компактный список.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Начните читать с самого левого «X» и начните писать с самого левого «=» и работайте направо. Когда это будет сделано, компактный список будет немного короче, и он будет не в том конце памяти:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Тогда мне нужно будет шунтировать вправо:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

В процессе изменения отображения заголовка до 1/3 заголовков подсписка будет изменяться с 1-битного на 2-битный. В худшем случае все они будут в начале списка, поэтому мне потребуется как минимум 781250/3 бита свободного места перед запуском, что возвращает меня к требованиям к памяти предыдущей версии компактного списка: (

Чтобы обойти это, я разделю 781250 подсписков на 10 групп подсписков по 78125 подсписков в каждой. Каждая группа имеет свое собственное независимое отображение заголовка подсписка. Используя буквы от A до J для групп:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Каждая группа подсписков уменьшается или остается неизменной во время изменения отображения заголовка подсписка:

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

Наихудшее временное расширение группы подсписков во время изменения отображения составляет 78125/3 = 26042 бит, меньше 4k. Если я позволю 4k плюс 1037764 байта для полностью заполненного компактного списка, то мне останется 8764 - 4096 = 4668 байтов для "Z" в карте памяти.

Этого должно быть достаточно для 10 таблиц отображения заголовков подсписков, 30 вхождений заголовков подсписков и других нескольких счетчиков, указателей и небольших буферов, которые мне понадобятся, и пространства, которое я использовал, не замечая, например, места в стеке для адресов возврата вызовов функций и локальные переменные.

Часть 3, сколько времени потребуется, чтобы бежать?

При пустом компактном списке 1-битный заголовок списка будет использоваться для пустого подсписка, а начальный размер списка будет 781250 битов. В худшем случае список увеличивается на 8 бит для каждого добавленного числа, поэтому 32 + 8 = 40 бит свободного места необходимы для каждого из 32-битных чисел, которые должны быть размещены в верхней части буфера списка, а затем отсортированы и объединены. В худшем случае изменение отображения заголовка подсписка приводит к использованию пространства в 2 * 781250 + 7 * записей - 781250/3 битов.

С политикой изменения сопоставления заголовка подсписка после каждого пятого слияния, когда в списке есть по крайней мере 800000 номеров, запуск наихудшего случая будет включать в себя около 30M операций чтения и записи компактного списка.

Источник:

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

Ответ Гильманова очень ошибочен в своих предположениях. Он начинает спекулировать, основываясь на бессмысленной оценке миллиона последовательных целых чисел. Это означает, что нет пробелов. Эти случайные промежутки, пусть и небольшие, действительно делают это плохой идеей.

Попробуй сам. Получите 1 миллион случайных 27-битных целых чисел, отсортируйте их, сожмите с 7-Zip , xz, любым LZMA, который вы хотите. Результат более 1,5 МБ. Предпосылка сверху - сжатие последовательных чисел. Даже дельта - кодирование этого является более 1,1 МБ . И не важно, что для сжатия используется более 100 МБ ОЗУ. Таким образом, даже сжатые целые числа не соответствуют проблеме и не берут в голову использование оперативной памяти .

Меня огорчает, что люди просто отдают предпочтение красивой графике и рационализации.

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

}

Теперь сожмите ints.bin с 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

Я думаю, что один из способов думать об этом с точки зрения комбинаторики: сколько возможных комбинаций отсортированных порядков номеров? Если мы дадим комбинацию 0,0,0, ...., 0 с кодом 0, и 0,0,0, ..., 1 с кодом 1, и 99999999, 99999999, ... 99999999 с кодом N, что такое N? Другими словами, насколько велико пространство результатов?

Что ж, один из способов думать об этом - заметить, что это биекция проблемы нахождения количества монотонных путей в сетке N x M, где N = 1 000 000, а M = 100 000 000. Другими словами, если у вас есть сетка шириной 1 000 000 и высотой 100 000 000, сколько кратчайших путей от нижнего левого до верхнего правого? Кратчайшие пути, конечно, требуют, чтобы вы двигались только вправо или вверх (если бы вы двигались вниз или влево, вы бы отменили достигнутый ранее прогресс). Чтобы увидеть, как это является биекцией нашей проблемы сортировки чисел, обратите внимание на следующее:

Вы можете представить любую горизонтальную ветвь на нашем пути в виде числа в нашем порядке, где Y-позиция ветки представляет значение.

Таким образом, если путь просто перемещается вправо до самого конца, то прыгает до самого верха, что эквивалентно порядку 0,0,0, ..., 0. если вместо этого он начинается с прыжка до вершины, а затем перемещается вправо 1 000 000 раз, что эквивалентно 99999999,99999999, ..., 99999999. Путь, по которому он перемещается вправо один раз, затем вверх один раз, затем вправо , затем один раз и т. д. до самого конца (затем обязательно прыгает до самого верха), эквивалентно 0,1,2,3, ..., 999999.

К счастью для нас, эта проблема уже решена, такая сетка имеет (N + M) Выбрать (M) путей:

(1 000 000 + 100 000 000) Выберите (100 000 000) ~ = 2,27 * 10 ^ 2436455

Таким образом, N равно 2,27 * 10 ^ 2436455, и поэтому код 0 представляет 0,0,0, ..., 0 и код 2,27 * 10 ^ 2436455, а некоторое изменение представляет 99999999,99999999, ..., 99999999.

Чтобы сохранить все числа от 0 до 2,27 * 10 ^ 2436455, вам нужно lg2 (2,27 * 10 ^ 2436455) = 8,0937 * 10 ^ 6 бит.

1 мегабайт = 8388608 бит> 8093700 бит

Получается, что у нас, по крайней мере, достаточно места для сохранения результата! Теперь, конечно, интересный бит выполняет сортировку по потоку чисел. Не уверен, что лучший подход к этому дан, поскольку у нас осталось 294908 бит. Я полагаю, что интересным методом было бы в каждой точке предположить, что это весь порядок, найти код для этого порядка, а затем, когда вы получите новый номер, вернуться назад и обновить предыдущий код. Ручная волна ручная волна.

Мои предложения во многом обязаны решению Дэна

Прежде всего я предполагаю, что решение должно обрабатывать все возможные списки ввода. Я думаю, что популярные ответы не делают этого предположения (что IMO является огромной ошибкой).

Известно, что никакая форма сжатия без потерь не уменьшит размер всех входных данных.

Все популярные ответы предполагают, что они смогут применять сжатие достаточно эффективно, чтобы предоставить им дополнительное пространство. Фактически, кусок дополнительного пространства достаточно большой, чтобы держать некоторую часть своего частично заполненного списка в несжатом виде и позволить им выполнять свои операции сортировки. Это просто плохое предположение.

Для такого решения любой, кто знает, как они выполняют свое сжатие, сможет спроектировать некоторые входные данные, которые не будут хорошо сжиматься для этой схемы, и «решение», скорее всего, тогда сломается из-за нехватки места.

Вместо этого я использую математический подход. Наши возможные выходные данные - это списки длины LEN, состоящие из элементов в диапазоне 0..MAX. Здесь LEN составляет 1 000 000, а наш MAX - 100 000 000.

Для произвольных LEN и MAX количество битов, необходимых для кодирования этого состояния:

Log2 (MAX Multichoose LEN)

Таким образом, для наших чисел, как только мы закончим получение и сортировку, нам понадобится как минимум Log2 (100 000 000 MC 1 000 000) битов, чтобы сохранить наш результат таким образом, чтобы можно было однозначно различать все возможные выходные данные.

Это ~ = 988kb . Таким образом, у нас действительно есть достаточно места, чтобы держать наш результат. С этой точки зрения это возможно.

[Удалено бессмысленное бродяжничество теперь, когда существуют лучшие примеры ...]

Лучший ответ здесь .

Другой хороший ответ здесь и в основном использует сортировку вставкой как функцию, чтобы расширить список на один элемент (буферизует несколько элементов и выполняет предварительную сортировку, чтобы позволить вставку более чем одного за раз, экономит немного времени). также использует красивое компактное кодирование состояний, сегменты из семи битов

Предположим, эта задача возможна. Непосредственно перед выводом в память будет отображено миллион отсортированных чисел. Сколько существует таких разных представлений? Так как могут быть повторяющиеся числа, мы не можем использовать nCr (выбор), но есть операция под названием multichoose, которая работает на мультимножествах .

• Есть 2.2e2436455 способов выбрать миллион чисел в диапазоне 0 ... 99 999 999.
• Для этого требуется 8 093 730 бит для представления каждой возможной комбинации или 1 011 717 байт.

Так что теоретически это может быть возможно, если вы можете придумать разумное (достаточное) представление отсортированного списка чисел. Например, для безумного представления может потребоваться таблица поиска размером 10 МБ или тысячи строк кода.

Однако, если «1M RAM» означает один миллион байтов, тогда явно недостаточно места. Тот факт, что на 5% больше памяти делает это теоретически возможным, подсказывает мне, что представление должно быть ОЧЕНЬ эффективным и, вероятно, не нормальным.

(Мой первоначальный ответ был неправильным, извините за плохую математику, см. Ниже перерыв.)

Как насчет этого?

Первые 27 бит хранят наименьшее число, которое вы видели, затем разность к следующему увиденному числу, закодированному следующим образом: 5 бит для хранения количества битов, использованных при сохранении разности, затем разность. Используйте 00000, чтобы указать, что вы видели этот номер снова.

Это работает потому, что по мере добавления большего числа чисел средняя разница между числами уменьшается, поэтому вы используете меньше битов для сохранения разницы при добавлении большего числа чисел. Я считаю, что это называется дельта-список.

Худший случай, о котором я могу подумать, - это все числа, равномерно распределенные (на 100), например, если предположить, что 0 - это первое число:

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

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

Reddit на помощь!

Если бы все, что вам нужно было сделать, это отсортировать их, эта проблема была бы легкой. Требуется 122 000 бит (1 миллион бит), чтобы запомнить, какие числа вы видели (0-й бит включен, если 0 был замечен, 2300-й бит включен, если был замечен 2300 и т. Д.

Вы читаете числа, сохраняете их в битовом поле, а затем сдвигаете биты, сохраняя счет.

НО, вы должны помнить, сколько вы видели. Я был вдохновлен ответом подсписка выше, чтобы придумать эту схему:

Вместо использования одного бита используйте 2 или 27 бит:

• 00 означает, что вы не видели номер.
• 01 означает, что вы видели это однажды
• 1 означает, что вы видели это, и следующие 26 битов - это количество раз.

Я думаю, что это работает: если нет дубликатов, у вас есть список 244 КБ. В худшем случае вы видите каждое число дважды (если вы видите одно число три раза, оно сокращает остальную часть списка для вас), это означает, что вы видели 50 000 больше, чем один раз, и вы видели 950 000 элементов 0 или 1 раз.

50 000 * 27 + 950 000 * 2 = 396,7 тыс.

Вы можете внести дополнительные улучшения, если используете следующую кодировку:

0 означает, что вы не видели число 10 означает, что вы видели его один раз 11, как вы держите счет

Что, в среднем, приведет к 280,7 КБ памяти.

РЕДАКТИРОВАТЬ: моя воскресная утренняя математика была неправильной.

В худшем случае мы видим 500 000 чисел дважды, поэтому математика становится:

500 000 * 27 + 500 000 * 2 = 1,77 млн.

Альтернативное кодирование приводит к среднему хранилищу

500 000 * 27 + 500 000 = 1,70 млн.

: (

Существует одно решение этой проблемы во всех возможных входах. Чит.

1. Считайте значения m по TCP, где m близко к максимальному значению, которое можно отсортировать в памяти, возможно, n / 4.
2. Отсортируйте 250 000 (или около того) чисел и выведите их.
3. Повторите для остальных 3 четвертей.
4. Пусть получатель объединит 4 списка номеров, которые он получил, обрабатывая их. (Это не намного медленнее, чем использование одного списка.)

Я бы попробовал Radix Tree . Если бы вы могли хранить данные в дереве, вы могли бы затем выполнить обход по порядку для передачи данных.

Я не уверен, что вы могли бы вписать это в 1 МБ, но я думаю, что стоит попробовать.

Какой компьютер вы используете? Возможно, у него нет другого «нормального» локального хранилища, но есть ли у него видеопамять, например? 1 мегапиксель x 32 бита на пиксель (скажем) очень близок к требуемому размеру ввода данных.

(Я в основном спрашиваю в памяти старого ПК Acorn RISC , который мог «позаимствовать» VRAM для расширения доступной оперативной памяти системы, если вы выбрали режим экрана с низким разрешением или низкой глубиной цвета!). Это было довольно полезно на машине с несколькими МБ нормальной оперативной памяти.

Представление радикального дерева близко подошло бы к решению этой проблемы, поскольку основополагающее дерево использует преимущество «сжатия префиксов». Но трудно представить представление радикального дерева, которое могло бы представлять один узел в одном байте - два, вероятно, о пределе.

Но независимо от того, как представлены данные, после их сортировки они могут быть сохранены в сжатом префиксе, где числа 10, 11 и 12 будут представлены, скажем, 001b, 001b, 001b, указывая на приращение 1 из предыдущего номера. Возможно, тогда 10101b будет представлять приращение 5, 1101001b - приращение 9 и т. Д.

Есть 10 ^ 6 значений в диапазоне 10 ^ 8, так что в среднем одно значение на сто кодовых точек. Сохраните расстояние от N-й точки до (N + 1) -го. Дублирующие значения имеют пропуск 0. Это означает, что для хранения требуется в среднем чуть менее 7 битов, поэтому миллион из них с удовольствием поместится в наши 8 миллионов бит хранилищ.

Эти пропуски должны быть закодированы в поток битов, скажем, кодированием Хаффмана. Вставка выполняется путем итерации по потоку битов и переписывания после нового значения. Вывод, повторяя и записывая подразумеваемые значения. Для практичности, вероятно, это нужно сделать, скажем, из 10 ^ 4 списков, охватывающих 10 ^ 4 кодовых пункта (и в среднем 100 значений) каждый.

Хорошее дерево Хаффмана для случайных данных можно построить априори, предполагая распределение Пуассона (среднее = дисперсия = 100) по длине пропусков, но реальная статистика может храниться на входе и использоваться для генерации оптимального дерева для работы с патологические случаи.

У меня есть компьютер с 1М оперативной памяти и нет других локальных хранилищ

Другой способ обмана: вы можете вместо этого использовать нелокальное (сетевое) хранилище (ваш вопрос не исключает этого) и вызвать сетевой сервис, который может использовать прямую дисковую сортировку слиянием (или просто достаточно ОЗУ для сортировки в памяти, поскольку вы нужно только принять номера 1М), без необходимости (по общему признанию, гениального) решения, которое уже дано.

Это может быть обманом, но неясно, ищете ли вы решение реальной проблемы или загадку, которая предполагает изменение правил ... если последнее, то простой чит может получить лучшие результаты, чем сложный но «подлинное» решение (которое, как отмечали другие, может работать только для сжимаемых входов).

Я думаю, что решение состоит в том, чтобы объединить методы кодирования видео, а именно дискретное косинусное преобразование. В цифровом видео, а не запись изменения яркости или цвета видео в виде регулярных значений, таких как 110 112 115 116, каждое вычитается из последнего (аналогично кодированию длины серии). 110 112 115 116 становится 110 2 3 1. Значения 2 3 1 требуют меньше битов, чем оригиналы.

Допустим, мы создаем список входных значений по мере их поступления в сокет. Мы храним в каждом элементе не значение, а смещение предыдущего элемента. Мы сортируем по ходу дела, поэтому смещения будут только положительными. Но смещение может составлять 8 десятичных цифр, что соответствует 3 байта. Каждый элемент не может быть 3 байта, поэтому нам нужно упаковать их. Мы могли бы использовать старший бит каждого байта в качестве «бита продолжения», указывая, что следующий байт является частью числа, а младшие 7 бит каждого байта должны быть объединены. ноль действителен для дубликатов.

Когда список заполняется, числа должны сближаться, то есть в среднем только 1 байт используется для определения расстояния до следующего значения. 7 битов значения и 1 бит смещения, если это удобно, но может быть приятное место, которое требует менее 8 битов для значения «продолжить».

Во всяком случае, я провел некоторый эксперимент. Я использую генератор случайных чисел, и я могу уместить миллион отсортированных 8-значных десятичных чисел примерно в 1279000 байт. Среднее расстояние между каждым числом последовательно 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);
    }
}

Мы могли бы поиграть с сетевым стеком, чтобы отправить числа в отсортированном порядке, прежде чем мы получим все числа. Если вы отправляете 1M данных, TCP / IP разбивает их на 1500-байтовые пакеты и передает их в поток к цели. Каждому пакету будет присвоен порядковый номер.

Мы можем сделать это вручную. Непосредственно перед тем, как заполнить нашу оперативную память, мы можем отсортировать то, что у нас есть, и отправить список нашей цели, но оставить пробелы в нашей последовательности вокруг каждого числа. Затем обработайте вторую половину чисел таким же образом, используя эти отверстия в последовательности.

Сетевой стек на дальнем конце будет собирать результирующий поток данных в порядке последовательности перед передачей его приложению.

Он использует сеть для выполнения сортировки слиянием. Это полный взлом, но я был вдохновлен другим сетевым взломом, перечисленным ранее.

Подход Google (плохой) из потока HN. Хранить RLE-стиль подсчета.

Ваша исходная структура данных - «99999999: 0» (все нули, не видели ни одного числа), а затем предположим, что вы видите число 3 866 344, поэтому ваша структура данных становится «3866343: 0,1: 1 96133654: 0» по мере того, как вы можно видеть, что числа всегда будут чередоваться между числом нулевых битов и числом битов «1», поэтому можно просто предположить, что нечетные числа представляют 0 битов, а четные числа - 1 бит. Это становится (3866343,1,96133654)

Кажется, что их проблема не распространяется на дубликаты, но давайте предположим, что они используют «0: 1» для дубликатов.

Большая проблема № 1: вставка для 1M целых чисел займет много лет .

Большая проблема # 2: как и все простые решения с дельта-кодированием, некоторые дистрибутивы не могут быть покрыты таким образом. Например, 1м целые числа с расстояниями 0:99 (например, +99 каждый). Теперь думаю то же самое, но с случайным расстоянием в диапазоне 0:99 . (Примечание: 99999999/1000000 = 99,99)

Подход Google является недостойным (медленным) и неправильным. Но в их защиту, их проблема могла бы быть немного другой.

Для представления отсортированного массива можно просто сохранить первый элемент и разницу между соседними элементами. Таким образом, мы занимаемся кодированием 10 ^ 6 элементов, которые могут суммировать до 10 ^ 8. Давайте назовем это D . Для кодирования элементов D можно использовать код Хаффмана . Словарь для кода Хаффмана может быть создан на ходу, и массив обновляется каждый раз, когда новый элемент вставляется в отсортированный массив (сортировка вставкой). Обратите внимание, что когда словарь изменяется из-за нового элемента, весь массив должен обновляться в соответствии с новой кодировкой.

Среднее количество битов для кодирования каждого элемента D максимизируется, если мы имеем равное количество каждого уникального элемента. Скажем, элементы d1 , d2 , ..., dN в D кажутся F раз. В этом случае (в худшем случае мы имеем 0 и 10 ^ 8 во входной последовательности) мы имеем

сумма (1 <= я <= N ) F . ди = 10 ^ 8

где

сумма (1 <= i <= N ) F = 10 ^ 6 или F = 10 ^ 6 / N, а нормализованная частота будет равна p = F / 10 ^ = 1 / N

Среднее число битов будет -log2 (1 / P ) = log2 ( N ). В этих условиях мы должны найти случай , который максимизирует N . Это происходит, если у нас есть последовательные числа для ди, начиная с 0, или, ди = я -1, поэтому

10 ^ 8 = сумма (1 <= я <= N ) F . di = сумма (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2

т.е.

N <= 201. И для этого случая среднее число битов составляет log2 (201) = 7,6511, что означает, что нам потребуется около 1 байта на элемент ввода для сохранения отсортированного массива. Обратите внимание, что это не означает, что D в общем случае не может иметь более 201 элемента. Он просто показывает, что если элементы D распределены равномерно, он не может иметь более 201 уникальных значений.

Я бы использовал поведение повторной передачи TCP.

1. Заставьте компонент TCP создать большое окно приема.
2. Получите некоторое количество пакетов без отправки ACK для них.
   • Обработайте проходы, создав некоторую (префиксную) структуру сжатых данных
   • Отправка дубликата подтверждения для последнего пакета, который больше не нужен / ожидание тайм-аута повторной передачи
   • Goto 2
3. Все пакеты были приняты

Это предполагает какую-то выгоду от ведер или нескольких проходов.

Вероятно, сортируя партии / ведра и объединяя их. -> осевые деревья

Используйте эту технику, чтобы принять и отсортировать первые 80%, затем прочитать последние 20%, убедиться, что последние 20% не содержат чисел, которые попадают в первые 20% наименьших чисел. Затем отправьте наименьшие 20% номеров, удалите из памяти, примите оставшиеся 20% новых номеров и объедините. **

Вот обобщенное решение этой проблемы:

Общая процедура

Принятый подход заключается в следующем. Алгоритм работает на одном буфере из 32-битных слов. Он выполняет следующую процедуру в цикле:

• Мы начнем с буфера, заполненного сжатыми данными из последней итерации. Буфер выглядит так

  |compressed sorted|empty|

• Вычислите максимальное количество чисел, которые могут быть сохранены в этом буфере, как сжатые, так и несжатые. Разделите буфер на эти два раздела, начиная с места для сжатых данных и заканчивая несжатыми данными. Буфер выглядит так

  |compressed sorted|empty|empty|

• Заполните несжатый раздел номерами для сортировки. Буфер выглядит так

  |compressed sorted|empty|uncompressed unsorted|

• Сортировка новых номеров с сортировкой по месту. Буфер выглядит так

  |compressed sorted|empty|uncompressed sorted|

• Выровняйте вправо любые уже сжатые данные из предыдущей итерации в сжатом разделе. В этот момент буфер разделен

  |empty|compressed sorted|uncompressed sorted|

• Выполните потоковую декомпрессию-повторную компрессию в сжатой секции, объединяя отсортированные данные в несжатой секции. Старый сжатый раздел используется по мере роста нового сжатого раздела. Буфер выглядит так

  |compressed sorted|empty|

Эта процедура выполняется, пока все номера не будут отсортированы.

компрессия

Этот алгоритм, конечно, работает только тогда, когда можно рассчитать окончательный сжатый размер нового буфера сортировки, прежде чем на самом деле узнать, что будет на самом деле сжато. Кроме того, алгоритм сжатия должен быть достаточно хорошим, чтобы решить актуальную проблему.

Используемый подход использует три шага. Во-первых, алгоритм всегда будет хранить отсортированные последовательности, поэтому мы можем вместо этого хранить только различия между последовательными записями. Каждое различие находится в диапазоне [0, 99999999].

Эти различия затем кодируются как унарный поток битов. «1» в этом потоке означает «Добавить 1 к аккумулятору», «0» означает «Извлечь аккумулятор как вход и сбросить». Таким образом, разница N будет представлена ​​N 1 и одним 0.

Сумма всех разностей приблизится к максимальному значению, поддерживаемому алгоритмом, а количество всех различий приблизится к количеству значений, вставленных в алгоритм. Это означает, что мы ожидаем, что поток в конце будет содержать максимальное значение 1 и считать 0. Это позволяет нам рассчитать ожидаемую вероятность 0 и 1 в потоке. А именно, вероятность 0 равна, count/(count+maxval)а вероятность 1 равнаmaxval/(count+maxval) .

Мы используем эти вероятности, чтобы определить модель арифметического кодирования для этого потока битов. Этот арифметический код будет кодировать именно это количество 1 и 0 в оптимальном пространстве. Мы можем вычислить пространство , используемое этой модели для любого промежуточного битового потока , как: bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount). Чтобы рассчитать общее требуемое пространство для алгоритма, установите значение encodedравно сумме.

Чтобы не требовать смешного количества итераций, в буфер могут быть добавлены небольшие накладные расходы. Это будет гарантировать, что алгоритм будет, по крайней мере, работать с количеством чисел, которые вписываются в эту служебную информацию, поскольку наибольшими временными затратами алгоритма являются сжатие и декомпрессия арифметического кодирования в каждом цикле.

Кроме того, некоторые накладные расходы необходимы для хранения бухгалтерских данных и для обработки небольших неточностей в приближении с фиксированной запятой алгоритма арифметического кодирования, но в целом алгоритм способен умещаться в 1 МБ пространства даже при наличии дополнительного буфера, который может содержать 8000 чисел, в общей сложности 1043916 байт пространства.

Оптимальность

Помимо уменьшения (небольших) издержек алгоритма теоретически невозможно получить меньший результат. Чтобы просто содержать энтропию конечного результата, потребуется 1011717 байт. Если мы вычтем дополнительный буфер, добавленный для эффективности, этот алгоритм использовал 1011916 байт для хранения конечного результата + накладные расходы.

Если бы входной поток мог быть получен несколько раз, это было бы намного проще (никакой информации об этом, идея и проблема времени-производительности).

Затем мы могли бы посчитать десятичные значения. С подсчитанными значениями было бы легко создать выходной поток. Сжатие путем подсчета значений. Это зависит от того, что будет во входном потоке.

Если бы входной поток мог быть получен несколько раз, это было бы намного проще (нет информации об этом, идея и проблема времени-производительности). Затем мы могли бы посчитать десятичные значения. С подсчитанными значениями было бы легко создать выходной поток. Сжатие путем подсчета значений. Это зависит от того, что будет во входном потоке.

Сортировка является вторичной проблемой здесь. Как уже говорилось, просто хранить целые числа сложно, и они не могут работать на всех входах , поскольку потребуется 27 бит на число.

Мое предположение заключается в следующем: хранить только различия между последовательными (отсортированными) целыми числами, поскольку они, скорее всего, будут небольшими. Затем используйте схему сжатия, например, с 2 дополнительными битами на входное число, чтобы кодировать, сколько битов хранится в этом числе. Что-то вроде:

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

Должно быть возможно хранить достаточное количество возможных входных списков в пределах данного ограничения памяти. Математика о том, как выбрать схему сжатия, чтобы она работала на максимальном количестве входов, мне не подходит.

Я надеюсь, что вы, возможно, сможете использовать специфичные для предметной области знания своего ввода, чтобы найти достаточно хорошую целочисленную схему сжатия, основанную на этом.

О, а затем вы делаете сортировку вставки в этом отсортированном списке по мере получения данных.

Теперь мы стремимся к реальному решению, охватывающему все возможные случаи ввода в 8-значном диапазоне только с 1 МБ ОЗУ. ПРИМЕЧАНИЕ: работа продолжается, завтра продолжится. При использовании арифметического кодирования дельт отсортированных целых чисел наихудший случай для сортированных целых 1М будет стоить около 7 бит на запись (поскольку 99999999/1000000 равен 99, а log2 (99) составляет почти 7 бит).

Но вам нужно отсортировать целые числа 1м, чтобы получить 7 или 8 бит! У более коротких серий были бы большие дельты, поэтому больше битов на элемент.

Я работаю над тем, чтобы взять как можно больше и сжать (почти) на месте. Первая партия, близкая к 250К, должна в лучшем случае иметь по 9 бит каждая. Таким образом, результат займет около 275 КБ. Повторите с оставшейся свободной памятью несколько раз. Затем распакуйте, объедините и сожмите эти сжатые фрагменты. Это довольно сложно , но возможно. Я думаю.

Объединенные списки будут становиться все ближе и ближе к цели 7 бит на целое число. Но я не знаю, сколько итераций потребуется для цикла слияния. Возможно 3.

Но неточность реализации арифметического кодирования может сделать это невозможным. Если эта проблема вообще возможна, она будет чрезвычайно жесткой.

Есть добровольцы?

Вам просто нужно сохранить различия между номерами в последовательности и использовать кодировку для сжатия этих номеров последовательности. У нас есть 2 ^ 23 бит. Мы разделим его на 6-битные порции, и пусть последний бит укажет, распространяется ли число еще на 6 бит (5 бит плюс расширяющийся фрагмент).

Таким образом, 000010 - это 1, а 000100 - это 2. 000001100000 - это 128. Теперь мы рассмотрим наихудший бросок при представлении различий в последовательности чисел до 10 000 000. Может быть 10 000 000/2 ^ 5 различий, превышающих 2 ^ 5, 10 000 000/2 ^ 10 различий, превышающих 2 ^ 10, и 10 000 000/2 ^ 15 различий, превышающих 2 ^ 15, и т. Д.

Итак, мы добавляем, сколько бит потребуется для представления нашей последовательности. У нас есть 1 000 000 * 6 + сводка (10 000 000/2 ^ 5) * 6 + сводка (10 000 000/2 ^ 10) * 6 + сводка (10 000 000/2 ^ 15) * 6 + сводка (10 000 000/2 ^ 20) * 4 = 7935479.

2 ^ 24 = 8388608. Поскольку 8388608> 7935479, у нас должно быть достаточно памяти. Вероятно, нам понадобится еще немного памяти для хранения суммы, где находятся, когда мы вставляем новые числа. Затем мы проходим последовательность и находим, куда вставить наш новый номер, уменьшаем следующую разницу, если необходимо, и сдвигаем все после него вправо.

Если мы ничего не знаем об этих числах, мы ограничены следующими ограничениями:

• нам нужно загрузить все числа, прежде чем мы сможем их отсортировать,
• набор чисел не сжимается.

Если эти предположения верны, выполнение вашей задачи невозможно, так как вам потребуется как минимум 26 575 425 бит памяти (3 321 929 байт).

Что вы можете рассказать нам о своих данных?

Хитрость заключается в том, чтобы представить состояние алгоритмов, которое является целочисленным множеством, в виде сжатого потока "счетчик приращения" = "+" и "счетчик вывода" = "!" персонажи. Например, набор {0,3,3,4} будет представлен как «! +++ !! +!», За которым следует любое количество символов «+». Чтобы изменить множественный набор, вы выводите символы, сохраняя только постоянную величину, распакованную за раз, и вносите изменения на месте, прежде чем передавать их обратно в сжатой форме.

подробности

Мы знаем, что в финальном наборе ровно 10 ^ 6 чисел, поэтому самое большее 10 ^ 6 "!" персонажи. Мы также знаем, что наш диапазон имеет размер 10 ^ 8, то есть максимум 10 ^ 8 "+" символов. Число способов, которыми мы можем расположить 10 ^ 6 "!" Среди 10 ^ 8 "+", составляет (10^8 + 10^6) choose 10^6, поэтому указание некоторого конкретного расположения занимает ~ 0,965 МиБ. `данных. Это будет плотно.

Мы можем рассматривать каждого персонажа как независимого без превышения нашей квоты. "+" Символов ровно в 100 раз больше, чем "!" символы, что упрощает до 100: 1 шансы каждого символа быть «+», если мы забываем, что они зависимы. Коэффициенты, равные 100: 101, соответствуют ~ 0,08 битам на символ для почти идентичной общей суммы ~ 0,965 МБ (игнорирование зависимости в этом случае обходится всего в ~ 12 бит !).

Самым простым способом хранения независимых символов с известной априорной вероятностью является кодирование Хаффмана. . Обратите внимание, что нам нужно непрактично большое дерево. (Дерево Хаффмана для блоков из 10 символов имеет среднюю стоимость за блок около 2,4 битов, в общей сложности ~ 2,9 Мб. Дерево Хаффмана для блоков из 20 символов имеет среднюю стоимость за блок около 3 битов, что составляет в общей сложности ~ 1,8 МБ. Вероятно, нам понадобится блок размером порядка ста, что подразумевает больше узлов в нашем дереве, чем может хранить все когда-либо существующее компьютерное оборудование. ). Тем не менее, ПЗУ технически «свободен» в зависимости от проблемы, и практические решения, использующие преимущества регулярности в дереве, будут выглядеть практически одинаково.

Псевдо-код

• Иметь достаточно большое дерево Хаффмана (или аналогичные блочные данные сжатия), хранящиеся в ПЗУ
• Начните со сжатой строки из 10 ^ 8 "+" символов.
• Чтобы вставить число N, выведите сжатую строку, пока не пройдут N символов «+», затем вставьте «!». Поток повторно сжатой строки обратно по сравнению с предыдущей, сохраняя постоянное количество буферизованных блоков, чтобы избежать чрезмерного / недостаточного выполнения.
• Повторите миллион раз: [вход, распаковка потока> вставка> сжатие], затем распакуйте в выходной файл

У нас есть 1 МБ - 3 КБ ОЗУ = 2 ^ 23 - 3 * 2 ^ 13 битов = 8388608 - 24576 = 8364032 битов.

Нам дано 10 ^ 6 чисел в диапазоне 10 ^ 8. Это дает средний разрыв ~ 100 <2 ^ 7 = 128

Давайте сначала рассмотрим более простую проблему относительно равномерно распределенных чисел, когда все пробелы <128. Это легко. Просто сохраните первый номер и 7-битные пробелы:

(27 бит) + 10 ^ 6 7-битных чисел = 7000027 бит требуется

Обратите внимание, что повторяющиеся числа имеют пробелы 0.

Но что, если у нас будут пробелы больше 127?

Хорошо, скажем, размер промежутка <127 представлен непосредственно, но за размером промежутка 127 следует непрерывное 8-битное кодирование для фактической длины промежутка:

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

и т.п.

Обратите внимание, что это представление числа описывает его собственную длину, поэтому мы знаем, когда начинается следующий номер разрыва.

С небольшими пробелами <127 это все еще требует 7000027 бит.

Может быть до (10 ^ 8) / (2 ^ 7) = 781250 23-разрядного числа пробелов, что требует дополнительных 16 * 781 250 = 12 500 000 бит, что слишком много. Нам нужно более компактное и медленно увеличивающееся представление пробелов.

Средний размер зазора равен 100, поэтому, если мы изменим их порядок на [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] и внесем в индекс это с плотной двоичной базовой кодировкой Фибоначчи без пар нулей (например, 11011 = 8 + 5 + 2 + 1 = 16) с числами, разделенными '00', тогда я думаю, что мы можем сохранить представление гэпа достаточно коротким, но это требует больше анализа.

При получении потока выполните следующие действия.

1-й набор некоторого разумного размера куска

Идея псевдокода:

1. Первым шагом было бы найти все дубликаты и вставить их в словарь с их количеством и удалить их.
2. Третий шаг - поместить числа, существующие в последовательности их алгоритмических шагов, и поместить их в счетчики в специальных словарях с первым номером и их шагом, например, n, n + 1 ..., n + 2, 2n, 2n + 1, 2n + 2 ...
3. Начните сжимать кусками некоторые разумные диапазоны чисел, такие как каждые 1000 или 10000 оставшихся чисел, которые появляются реже, чтобы повторяться.
4. Распакуйте этот диапазон, если число найдено, и добавьте его в диапазон и оставьте его без сжатия на некоторое время.
5. В противном случае просто добавьте это число к байту [chunkSize]

Продолжайте первые 4 шага при получении потока. Последним шагом будет либо сбой, если вы превысили объем памяти, либо начните выводить результат, как только все данные собраны, начиная сортировку диапазонов и выплевывая результаты по порядку и распаковывая те, которые нужно распаковать, и сортировать их, когда Вы добираетесь до них.