Sleep sort

[jayrandom]

И я считаю, что Sleep sort - гениальный алгоритм для сортировки.

Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду.

Самое важное в этом примере - принцип замены измерения пространства измерением времени.
Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом.

Comments

[chip33.livejournal.com]

Хе-хе, забавная идея.

[livelight]

Надеюсь, вы таки шутите.

Хотел сказать, что комментаторы жгут, и разве что на брейнфаке не написали [хоть какой-то] алгоритм - но оказалось, что написали :)

[jayrandom.livejournal.com]

В каком месте шучу?

Вообще, конкретная реализация (язык, платформа) - совершенно не важна. Важен принцип взаимопреобразования времени и пространства (памяти), который здесь совершенно шикарно использован.

[livelight]

Вся теория сложности, в рамках которой обычно выводятся оценки вида O(n*log(n)), построена для случая _одного_ вычислителя. Для построения класса алгоритмов NP (известного по NP-полным задачам) вводится специфическое псевдо-распараллеливание с очень ограниченной функциональностью.

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

[jayrandom.livejournal.com]

;-)

В реальной жизни у нас не бесконечное количество, а, допустим, m. И важно, как именно для каждого алгоритма это m в формулу впишется.

[livelight]

В реальной жизни у нас не бесконечная память, а, скажем, 4ГБ, позволенные 32-битной архитектурой. А значит, любой массив, какой только может вообразить себе 32-битный компьютер, можно отсортировать за О(1) операций. Это прорыв через жестокое O(nlogn), которое так тяготело над компьютерсаенсом ;)

[jayrandom.livejournal.com]

я оговорился, назвав жизнь реальной :) Имеется в виду та самая мат.модельная реальность, в которой параметр n имеет значение. В ней же, когда обсуждается многопоточность, принято учитывать ограниченное число вычислителей m.

[a_p]

вообще-то отсортировать целые числа за О(наибольшее значение + эн) можно, просто построив гистограмму.

[jayrandom.livejournal.com]

Правильно, это и есть в некотором роде "гистограмма". Но для хранения гистограммы нужно место (плюс структуры для манипуляции), а тут гистограмма (или процесс её построения) погружён во время.

[a_p]

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

[rapitosov.livejournal.com]

идея классная, но во время прохода по аргументам таймер на месте не стоит - есть возможность промахнуться