вторник, октября 30, 2012

Статья про сортировку 1 миллиона чисел с ограничением по памяти

На Stack Overflow кто-то сформулировал следующую задачу: по сети приходят восьмизначные числа. Их приходит миллион штук, их надо отсортировать и переслать дальше. Проблема в том, что устройство, на которое они приходят - это компьютер с 1 Мб оперативной памяти. И это вся память что есть, жесткого диска нет. Короче говоря, реализовать сортировку по-тупому не получится, ибо не лезет.

Вот здесь описано решение этой задачи 1MB Sorting Explained. Подход выбран следующий: числа накапливать и сортировать кусками. Отсортированную последовательность хранить в пожатом виде.

13 коммент.:

le_cha_sever комментирует...

Странное решение.
Создаём массив из 256 элементов, в каждом из элементов 3 байта. В элементе хранится максимальная позиция, которую занимает байт со значением, равным индексу массива, ну или 0xFFFFFF - если такого элемента ещё нет. Для примера будет приходит милион чисел от 0 до 3 (лень мне больше рисовать). Пришло уже 999999, из низ 40 единиц, остальные - тройки. Имеем:
Индекс Значение
0 0xFFFFFF
1 0x000027
2 0xFFFFFF
3 0x0F423E
Пусть пришёл последним 0. Имеем
Индекс Значение
0 0x000000
1 0x000028
2 0xFFFFFF
3 0x0F423F
Пусть пришла последней 1. Имеем
Индекс Значение
0 0xFFFFFF
1 0x000028
2 0xFFFFFF
3 0x0F423F
Пусть пришла последней 2. Имеем
Индекс Значение
0 0xFFFFFF
1 0x000027
2 0x000028
3 0x0F423F
Пусть пришла последней 3. Имеем
Индекс Значение
0 0xFFFFFF
1 0x000027
2 0xFFFFFF
3 0x0F423F
Надеюсь суть ясна. И на хранение всего для исходной задачи надо 768 байт - и восьмибитный микроконтроллер справится

Alena комментирует...

Создаём массив из 256 элементов,

Там по условию приходят восьмизначные числа - это восемь цифр.

Андрей Костягин комментирует...

Ну да, восьмизначные десятичные, не двоичные приходят.
Решение красивое, особенно порадовал трюк с кольцевым буфером, и строгая оценка длины закодированной последовательности.
Можно ещё немного улучшить - пока чисел накоплено мало - часть свободного места в кольцевом буфере использовать для сортировки.

Alexander Shmadchenko комментирует...

le_cha_sever, я не совсем точно уловил вашу идею, не могли бы вы меня поправить?
По условию приходит миллион восьмизначных чисел, то есть в худшем из доступных раскладов мы получим миллион уникальных чисел. Таким образом, если брать ваш вариант решения задачи нам понадобится массив из миллиона элементов. А если учесть, что размер каждого элемента уже 3 байта, то по памяти мы уже не укладываемся.

le_cha_sever комментирует...

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

soonts комментирует...

Пока не прочитал решение, был убеждён что это невозможно, т.к. памяти не хватит.

Когда прочитал, понял что работать конечно будет, но адски медленно. С учётом того сколько щас стоит RAM, решение не имеет ни малейшей практической пользы.

Покликал по ссылкам - и точно: задача c собеседования в google.

Arkady Shapkin комментирует...

На ClosedCircles (http://blog.gamedeff.com/?p=386) говорят что эту задачку дают в Гугле на интервью.

DJm00n комментирует...

Странно, что никто не написал еще. Дональд Кнут в книге "Искусство программирования. Том 3. Сортировка и поиск" - прекрасно описывает что, почему и как. Подобные алгоритмы называются там "Внешняя сортировка". Также описание есть в Википедии. http://ru.wikipedia.org/wiki/Внешняя_сортировка
Проблема известная и "скандал" раздут, ИМХО.

Alena комментирует...

DJm00n

Странно, что никто не написал еще.
...
Подобные алгоритмы называются там "Внешняя сортировка".


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

DJm00n комментирует...

Что-то вы путаете. Перечитайте википедию. Речь идет какраз только о оперативной памяти. Когда возникла эта проблема, была только оперативная память и очень медленные магнитные диски.

Stebanoid комментирует...

Это задачка описывается первой в книге Programming perls.
в одном мегабайте больше бит, чем вариантов восьмизначных чисел, поэтому мы каждому биту назначаем своё число. Нулевому биту 00000000, первому 00000001 и т.д. Зануляем масив бит. Потом, когда приходит очередное число, устанавливаем соответствующий бит в 1. после прихода всех чисел будем иметь массив, который начиная с начала можно проходить бит за битом и натыкаясь на установленный бит печатать его номер. Всё. Задача решена за линейное время.

Alena комментирует...

Stebanoid

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

Тут по условию задачи последовательность может содержать дубликаты. Одного бита на число мало.

vors комментирует...

Stebanoid


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


100000000 > 8388608 = 8 * 1024 * 1024