На Stack Overflow кто-то сформулировал следующую задачу: по сети приходят восьмизначные числа. Их приходит миллион штук, их надо отсортировать и переслать дальше. Проблема в том, что устройство, на которое они приходят - это компьютер с 1 Мб оперативной памяти. И это вся память что есть, жесткого диска нет. Короче говоря, реализовать сортировку по-тупому не получится, ибо не лезет.
Вот здесь описано решение этой задачи 1MB Sorting Explained. Подход выбран следующий: числа накапливать и сортировать кусками. Отсортированную последовательность хранить в пожатом виде.
вторник, октября 30, 2012
Статья про сортировку 1 миллиона чисел с ограничением по памяти
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
13 коммент.:
Странное решение.
Создаём массив из 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 байт - и восьмибитный микроконтроллер справится
Создаём массив из 256 элементов,
Там по условию приходят восьмизначные числа - это восемь цифр.
Ну да, восьмизначные десятичные, не двоичные приходят.
Решение красивое, особенно порадовал трюк с кольцевым буфером, и строгая оценка длины закодированной последовательности.
Можно ещё немного улучшить - пока чисел накоплено мало - часть свободного места в кольцевом буфере использовать для сортировки.
le_cha_sever, я не совсем точно уловил вашу идею, не могли бы вы меня поправить?
По условию приходит миллион восьмизначных чисел, то есть в худшем из доступных раскладов мы получим миллион уникальных чисел. Таким образом, если брать ваш вариант решения задачи нам понадобится массив из миллиона элементов. А если учесть, что размер каждого элемента уже 3 байта, то по памяти мы уже не укладываемся.
Виноват, вместо восьмизначные прочитал восьмибитные... Тогда да, проблема ясна
Пока не прочитал решение, был убеждён что это невозможно, т.к. памяти не хватит.
Когда прочитал, понял что работать конечно будет, но адски медленно. С учётом того сколько щас стоит RAM, решение не имеет ни малейшей практической пользы.
Покликал по ссылкам - и точно: задача c собеседования в google.
На ClosedCircles (http://blog.gamedeff.com/?p=386) говорят что эту задачку дают в Гугле на интервью.
Странно, что никто не написал еще. Дональд Кнут в книге "Искусство программирования. Том 3. Сортировка и поиск" - прекрасно описывает что, почему и как. Подобные алгоритмы называются там "Внешняя сортировка". Также описание есть в Википедии. http://ru.wikipedia.org/wiki/Внешняя_сортировка
Проблема известная и "скандал" раздут, ИМХО.
DJm00n
Странно, что никто не написал еще.
...
Подобные алгоритмы называются там "Внешняя сортировка".
Классическая внешняя сортровка подразумевает наличие жесткого диска. Задача как раз о том, как сделать нечто аналогичное внешней сортировке, но без жесткого диска.
Что-то вы путаете. Перечитайте википедию. Речь идет какраз только о оперативной памяти. Когда возникла эта проблема, была только оперативная память и очень медленные магнитные диски.
Это задачка описывается первой в книге Programming perls.
в одном мегабайте больше бит, чем вариантов восьмизначных чисел, поэтому мы каждому биту назначаем своё число. Нулевому биту 00000000, первому 00000001 и т.д. Зануляем масив бит. Потом, когда приходит очередное число, устанавливаем соответствующий бит в 1. после прихода всех чисел будем иметь массив, который начиная с начала можно проходить бит за битом и натыкаясь на установленный бит печатать его номер. Всё. Задача решена за линейное время.
Stebanoid
в одном мегабайте больше бит, чем вариантов восьмизначных чисел, поэтому мы каждому биту назначаем своё число.
Тут по условию задачи последовательность может содержать дубликаты. Одного бита на число мало.
Stebanoid
в одном мегабайте больше бит, чем вариантов восьмизначных чисел, поэтому мы каждому биту назначаем своё число.
100000000 > 8388608 = 8 * 1024 * 1024
Отправить комментарий