Сортировка (программистское)

[olg2002]

Можно ли честно в двух мегабайтах памяти отсортировать миллион целых чисел (32 бита)? (числа вводятся через int get() и выводятся через put(int) ).
Вопрос с бородой (если кто знает, откуда она растет, - было бы любопытно), но без убедительного ответа.

[AndreyT]

Не понимаю вопроса. Что значит "честно"? Миллион 4-хбайтных чисел заведомо не поместится в 2 мегабайта памяти одновременно. Следовательно, придется исхитряться и работать с числами в памяти по частям, храня числа где-то еще.

Получается, что вопрос о том, можно ли в принципе как-то отсортировать миллион хранимых внешне 4-хбайтных чисел, пользуясь только 2-мя мегабайтами памяти. Ответ: ну разумеется можно.

Или вопрос о том, как это сделать не "храня числа где-то еще"? Ответ на это вопрос очевиден: нет, ибо в общем случае невозможно начать выдачу результата до того, как стало известным последнее входное число.

[olg2002]

Честно - значит "не храня числа где-то еще". Если можно пользоваться внешней памятью, то это совершенно другая задача - так можно сколько угодно отсортировать, что там миллион.

[Y+A=LOVE]

Только чесно а куда етот put(int) выводит числа?

[AndreyT]

Честно - значит "не храня числа где-то еще". Если можно пользоваться внешней памятью, то это совершенно другая задача - так можно сколько угодно отсортировать, что там миллион.

Ну то есть числа приходят от "одноразового оракула" get и результат должен быть отправлен в "нечитаемую бездонную пропасть" put, так?

В такой ситуации могу лишь повторить свой аргумент: в общем случае невозможно начать вывод результата, не зная последнего входного числа. Т.е. в общем случае в какой-то момент времени весь вход должен храниться в какой-то форме в этих 2Мб. Это невозможно, ибо, опять же в общем случае, невозможно "упаковать" 4Гб данных в 2Гб памяти.

Какие на это могут быть возражения?

Хотя вижу, что возражения есть. Невозможно упаковать 4Гб произвольных данных в 2Мб памяти. Но вполне возможно, что запросто можно упаковать 4Гб отсортированных чисел в 2Мб памяти. Т.е. храним числа в виде "первое число, и последовательность дельт от предыдущего числа к следующему". Нельзя ли так хитро все организовать, что в каждый момент времени пиковое потребление памяти гарантированно не будет превышать 2Мб? Мне уже кажется, что можно.

[AndreyT]

Нависидку, если примитивно закодировать дельты как последовательность из 5 бит (N - длина дельты) и затем N-бит (сама дельта), то, похоже, пиковое потребление памяти не должно превысить 2Гб. Т.е. ответ будет - да можно.

[olg2002]

Ну, что-то все перемешалось. Еще раз: чисел - 1000000(миллион), разрядность - 32 бита (тридцать два), памяти - 2МБ (два мегабайта).
"5 бит на длину + само число" в 2MБ не влезут. Контрпример: миллион раз по 4096 = 1000000 * ( 5 + 13 ) = 18000000 > 2МБ.

[AndreyT]

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

[vaduz]

названная мною возможность правильная (как возможность) и единственная.

+1

[venco]

Теоретически, количество информации в отсортированном списке миллиона 32-битных чисел - log2(C(2^32,1000000)) ~= 1688868 байт.
Т.е. теоретически задача решаема. Вопрос в том, реализуемо ли это на практике.

Если взять за основу дельта кодирование, то, для начала, надо стелать диапазоны дельт непересекающимися:
0: [0,0]
1: [1,2]
2: [3,6]
...
k: [2^k-1,2^2k-2]
...
12: [4095,8190]
...
Теперь надо прикинуть, насколько уменьшает энтропию каждый диапазон, и закодировать его Хаффманом. Возможно, такое простое кодирование будет достаточным.

В результате вычислительная сложность алгоритма будет O(n^2), где n=1000000.

[vaduz]

передумал

[olg2002]

Подтянулись тяжеловесы - очень рад!

Т.е. теоретически задача решаема. Вопрос в том, реализуемо ли это на практике.

"Теоретически, разница между теорией и практикой не существенна, но на практике, конечно же, дело обстоит совсем иначе".

Теперь надо прикинуть, насколько уменьшает энтропию каждый диапазон, и закодировать его Хаффманом.

Одна проблема с Хафманом в том, что он работает с вероятностями (частотами, энтропией). У нас же нет никаких вероятностей как таковых: может быть миллион нулей, а может быть миллион 4294 (правда, миллиона миллионов быть уже не может). Задача должна быть решена, если она может быть решена, в "худшем случае", а не только "в среднем". Если же рассматривать Хафмана как prefix-free код, то да - без него, наверное, не обойтись.

В результате вычислительная сложность алгоритма будет O(n^2), где n=1000000.

Об этом мы еще поговорим.

[vaduz]

миллиона миллионов быть уже не может

А можно об этом поподробнее, почему миллионов быть не может?

[olg2002]

А можно об этом поподробнее, почему миллионов быть не может?

Речь уже о дельтах в упорядоченной последовательности. Во входной последовательности может быть что угодно.

[vaduz]

Теоретически, количество информации в отсортированном списке миллиона 32-битных чисел - log2(C(2^32,1000000)) ~= 1688868 байт.

Все-таки спрошу: откуда получается эта формула?

[venco]

Теоретически, количество информации в отсортированном списке миллиона 32-битных чисел - log2(C(2^32,1000000)) ~= 1688868 байт.

Все-таки спрошу: откуда получается эта формула?

На самом деле я чуть-чуть ошибся. Вышеприведённая формула - для случая, когда все числа разные. Если же могут быть совпадения, то log2(C(2^32+1000000-1,1000000)), что на 42 байта больше.
Первый вариант выводится легко, если понять, что на выходе просто выборка 1000000 значений из 2^32 возможных.

[vaduz]

Первый вариант выводится легко, если понять, что на выходе просто выборка 1000000 значений из 2^32 возможных.

А, все понятно, нумеруем все возможные выборки.
Тогда есть тривиальный ( но медленный ) алгоритм, который может уложиться в 2Мб.

Типа, делаем массив на 1,700,000 байт для дельта значений (дельты могут иметь разное количество бит), и массив на 312500 байт для размеров дельт.
Дельты могут быть 1..32 разрядными, т.е. надо 5 бит на каждую дельту. Поскольку памяти маловато, то храним размер для двух дельт подряд.

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

По идее можно показать, что размер массива данных не превысит 1,7 млн.
Потому как при вставке числа получаются две дельты с меньшим размером.
Точнее размер двух новых дельт максимум = 2*(размер старой) - 2

[Dweller]

Первый вариант выводится легко, если понять, что на выходе просто выборка 1000000 значений из 2^32 возможных.

А, все понятно, нумеруем все возможные выборки.
Тогда есть тривиальный ( но медленный ) алгоритм, который может уложиться в 2Мб.

Типа, делаем массив на 1,700,000 байт для дельта значений (дельты могут иметь разное количество бит), и массив на 312500 байт для размеров дельт.
Дельты могут быть 1..32 разрядными, т.е. надо 5 бит на каждую дельту. Поскольку памяти маловато, то храним размер для двух дельт подряд.

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

По идее можно показать, что размер массива данных не превысит 1,7 млн.
Потому как при вставке числа получаются две дельты с меньшим размером.
Точнее размер двух новых дельт максимум = 2*(размер старой) - 2

Тут уже приводился контрпример что 1,000,000 * (13 + 5) > 2Мб
На размер дельты надо меньше 5 бит выделять.
Тут скорее всего надо где-то хранить и пересчитывать статистику размеров дельт так чтобы наиболее употребимые размеры занимали меньше чем 5 бит. Т.е. размер дельты (число от 1 до 32) должно кодироваться как код меньший по размеру чем 5 бит.
Скажем, в случае контрпримера от olg2002: все дельты равны 4096, значит их размеры 13 бит, надо закодировать 13й размер битом 0 и прописать это в таблице плавающих кодов. Тогда каждая дельта будет занимать всего 14 битов и 14*1,000,000 < 2Mb
Каждый раз, когда новое число уже не будет помещаться в массиве 2Мб, весь массив надо будет пересчитывать и назначать наиболее короткие коды размеров дельт на наиболее употребимые размеры. Т.е. таблица кодов может выглядеть так:
13 бит - 200,000 дельт, присваиваем код 0
12 бит - 140,000 дельт, присваиваем код 10
15 бит - ...., код 110
и т.д.
Размер самого кода пусть будет неограничен. За счет небольшой частоты употребления он будет занимать в итоге не много места.

[vaduz]

А может и влезет, мне надо в худшем случае 2,062,500 (массив данных таки 1,750,000)
2Mb = 2,097,152

[olg2002]

Схема vaduz-а сработает. Можно даже доказать:
Пусть W(d) - длина битового представления числа d>=0. Тогда W(n) <= 1+log(d+1). d+1 - чтобы для 0 тоже работало.
Для n чисел по предложенной схеме потребуется:
5*(n/2) + SUM[i=1..n] W(di) <= 2.5n+2*SUM[i=1..n/2] (1+log(di+1)) = 3.5n +2*SUM[i=1..n/2] log(di+1) = 3.5n + 2*log( MUL[i=1..n/2] (di+1)
Воспользуемся известным неравенством между средним геометрическим и средним арифметическим:
3.5n + 2*log( MUL[i=1..n/2] (di+1) <= 3.5n + 2*(n/2)*log( 2/n*SUM[i=1..n/2] (di+1) ) = 3.5n + n*log( 1 + 2/n*SUM[i=1..n/2] di ) < 3.5n + n*log( 1 + 2/n*2^32),
что при n=1000000 меньше чем 16600000 бит < 2МБ.
Результат можно улучшить, если не хранить лидирующую единицу в битовом представлении дельт (но тогда нужно специально позаботиться о представлении нуля).
Мое решение чуть проще в представлении (особенно если нужно реально кодировать) и доказательстве, но я приведу его позже.

Осталось обратить внимание на то, что сортировка вставкой миллиона чисел займет довольно долгое время, и если мы заменим миллион на n, то, как справедливо указал venco, сложность такого алгоритма будет O(n^2). Можно ли быстрее?

[venco]

Если кодировать дельты [0,2^11) как "0"+11bit
[2^11,2^12) - "10"+11bit
[2^12,2^13) - "110"+12bit
[2^13,2^14) - "1110"+13bit
и так далее.
В результате, если я не ошибся, потребуется не больше чем 15100000 бит или 1887500 байт.
В оставшиеся 200KB влезет код программы.

[olg2002]

venco - зачет! Оставшихся 200КБ хватит и под программу и под стек!
Мой грубый, но надежный метод дает близкую оценку <15146000 бит, так что если ошибка и есть, то не существенная.

Осталось O(n^2).

[vm__]

venco - зачет!

+1
Память - дешёвая, диски - дешёвые, процессорных циклов неиспользованных - как грязи!
Если не хватает того, что есть, для конкретной сегодняшней задачи - дык купим больше!
Нафик всякие алгоритмы-фигоритмы-шмагоритмы!
Brute force - rulez!
А то, глядишь, вообще кто-то что-то аналитически решит - и нафик этот компьютер окажется не нужен...

[Flash-04]

если кто знает, откуда она растет, - было бы любопытно

вы про это?
http://moderator.appspot.com/#16/e=c9

Ask a Google engineer
This is your chance to interview us! Feel free to ask anything from "How many cafeterias are there?" to "How would you sort 1 million 32-bit integers in 2MB of RAM?"

на самом деле подобную задачу мне давали ещё в 1993 году, но правда внешнюю память использовать можно было

[vaduz]

В результате, если я не ошибся, потребуется не больше чем 15100000 бит или 1887500 байт.

15500000 бит или 1937500 байт в случае 500 тыс дельт=0 и 500 тыс дельт=8589