Previous Entry Share Next Entry
2016-01

о сортировках

уважаемые товарищи!

а почему все считают, что сортировка произвольных данных inplace может выполняться за N log(N), если с 1985 1978 года у нас есть модификация бинарного поиска, работающая за log(log(N))?

ведь тогда, даже если взять банальную сортировку вставкой, асимптотика должна быть N*log(log(N)), или я чего-то недопонимаю?

UPD: блин, сортировка вставкой ведь еще двигать элементы должна, а в связном списке interpolation search невозможен.. надо сделать вариант Library sort и померять.

UPD2: а вот и N log log N сортировка от Yijie Han – yijie.han-loglogn-sort.pdf, спасибо 184467440737095 за наводку. Надо бы реализовать и потестить))


  • 1
slobin June 18th, 2010
Потому что первое -- оценка в худшем случае, а второе -- в среднем.

... Спой, Мэглор-скиталец, балладу мне ...


wizzard0 June 18th, 2010
Ну, у quicksort worst case N^2, если уж на то пошло.

slobin June 18th, 2010
Существует метод с гарантированным n*log(n) (метод пирамиды).

... noi ja'orgau ke'a lenu ke'a zekri te relsmu ...


wizzard0 June 18th, 2010
В общем, да, я уже понял обе своих ошибки (про асимптотику и про то что insertion sort в чистом виде не ускоряется). Хотя, по идее, можно попробовать таким способом еще pivot у квиксорта выбирать.

wizzard0 June 18th, 2010
ой. про пивот - совсем фигню сказал, тьфу)))

the_aaa13 June 18th, 2010
Не то, чтобы в среднем, так как вероятностное распределение не заданно. Просто при (разумном) предположении эквидистантности. Зато в худшем случае можно и N^2 в сортировке заработать, что уж совсем не комильфо.

slobin June 18th, 2010
В статье по ссылке распределение как раз задано: оно должно быть равномерным. Я очень сильно подозреваю (почти уверен), что для множества всех промежуточных результатов при методе вставки оно не соблюдается (даже если предположить, что таковым был исходный массив). Ну была же здесь уже аналогичная задачка... Проклятый эклер! :-(

... Identical to supernatural ...


wizzard0 June 18th, 2010
Для совсем равномерного распределения, кстати, получается поиск за константное время. Индексирование массива, собственно)

slobin June 18th, 2010
Хорошее наблюдение, да! А если мы априори знаем, что входной массив состоит из целых чисел от 1 до 10, то и результат сортировки можно просто взять и выписать. ;-)

... Одним движением бесшумно скользящего рычага ...


wizzard0 June 18th, 2010
Собственно, да.. Энтропия уменьшается - обработка упрощается...

slobin June 18th, 2010
Хотя, если спросить "почему в среднем не получается"... Кажется, в этом же журнале уже был очень похожий вопрос, собрал довольно большую дискуссию. Там даже вычислительный эксперимент провели. Но формулировку вопроса я забыл. ;-) Сейчас, попробую сочинить иллюстрацию.

... cilre fo lo se srera ...


bik_top June 18th, 2010
Сомножитель log(log(N)) — это поиск места вставки. Сама же вставка предполагает сдвиг части отсортированных элементов вправо, а это есть N.

wizzard0 June 18th, 2010
Блин, точно. *facepalm*

А если Library sort ( http://en.wikipedia.org/wiki/Library_sort ) поюзать?

Хотя да, асимптотика будет уже гораздо ближе к N log N все равно...

slobin June 18th, 2010
О! Точно! Я это осознал, спутав термины: перепутал Radix Sort и Library Sort. ;-) Radix Sort вообще работает за линейное время, но у него основная операция -- НЕ сравнение, а выделение и сравнение отдельных цифр. Может быть, я был не прав, и на самом деле при условии равномерности распределения входных данных (то есть, грубо говоря, мы априори знаем, что примерно половина чисел лежит в интервале [0.0;0.5], а половина в [0.5;1.0]) тот же самый трюк сработает и на сравнениях.

... У Краггаша нет ни единого шанса! ...


wizzard0 June 18th, 2010
Но радикс, кажись, не inplace? (пошел смотреть википедию)

slobin June 18th, 2010
Он, увы, не линейный. Ну то есть он линейный по размеру массива и линейный по длине элементов массива в битах, так что получается то же n*log(n). Я неаккуратно употребил слово в предыдущем комментарии.

... Transiit, quasi dolor, nox ...


thedeemon June 19th, 2010
> то же n*log(n)

Если n - число элементов, то с их размером оно не связано. Откуда здесь логарифм?

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

thedeemon June 19th, 2010
Враки.

wizzard0 June 19th, 2010
Покажите, как можно сделать массив из 2^50 разных 32битных интегеров?

wizzard0 June 19th, 2010
Ну или как сравнивать big интегеры за constant time.

thedeemon June 19th, 2010
Предположение, что все элементы массива различны, и что массив содержит все возможные элементы, безосновательно. А без такого предположения связи между размером элементов и их числом нет.
Давайте будем сортировать строки, например.

slobin June 19th, 2010
Больше -- не меньше. Если я знаю, что весь массив состоит только из нулей и единиц, я сортирую его за линейное время.

... Сундук в паутине лихой голосил ...


thedeemon June 19th, 2010
Правильно, и никакого логарифма там не будет.

wizzard0 June 19th, 2010
Вот поэтому мы и говорим, что в массиве есть примерно равномерно распределенная выборка элементов из пространства возможных элементов.

wizzard0 June 19th, 2010
>> и что массив содержит все возможные элементы

Я этого не говорил.

>> Давайте будем сортировать строки, например.

Строка в данном случае от big integera ничем не отличается.

slobin June 18th, 2010
Нет, не может, чушь порю. Стандартное доказательство того, что в худшем случае требуется не менее n*log(n) сравнений: элементы исходного массива могут быть переставлены n! (эн факториал) разными способами. Чтобы узнать, какой их этих способов правильный, мы должны задать не менее log_2(n!) бинарных вопросов. Из оценок для факториала (формула Стирлинга) получаем как раз n*log(n). Так что зря я на чудо понадеялся. ;-)

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

... Октябрьский эль моделируется вином из одуванчиков ...


slobin June 18th, 2010
Ну и, с учётом выше (но позже!) сказанного, почему равномерность распределения всё-таки может помочь: если мы заведомо знаем, что элемент 0.99 не может оказаться в первой половине массива, то возможных перестановок сразу становится меньше.

... Я очень уважаю Леонида Андреевича ...


wizzard0 June 18th, 2010
Прошу заметить, что я не предлагал искать в неотсортированном, я предлагал оптимизировать операцию вставки.

Только вот структура данных, в которую можно вставлять и искать за менее чем log N, мне чегото не припоминается...

slobin June 19th, 2010
Всё, сплю на ходу. В рамках этой дискуссии я насчитал уже, кажется, три (или больше?) существенно разных постановки задачи. И я сам их периодически путаю, пытаясь применить к одной результаты от другой. Получается чушь. :-( Прошу прощения, пошёл спать.

... Поймите меня хотя бы неправильно ...


slobin June 18th, 2010
Нет. Формальная "академическая" постановка задачи изменяет именно число сравнений, игнорируя все служебные операции. И я сильно подозреваю, что всё равно ничего хорошего не получится.

... Intrat et exit ut nil supra ...


bik_top June 18th, 2010
Проверил: у Кнута и у Кормена-Лейзерсона-Ривеста «нормальный» рассчёт асимптотики, а не «академический».

slobin June 18th, 2010
В данном случае не важно: я утверждаю, что даже сравнений (игнорируя пересылки) потребуется не менее n*log(n) в худшем случае. Учёт пересылок может только ухудшить оценку. Это называется "энтропийная оценка": чтобы отсортировать массив, нам нужно добыть откуда-то не менее n*log(n) бит информации. Если единственным источником информации является сравнение на больше-меньше, то вот столько их и будет. Если разрешены другие источники информации (например, выделение отдельных битов из данных), то будет вот столько обращений к этим другим источникам.

... Какой я математик? Я флюктуация. ...


nicka_startcev June 19th, 2010
(цинично) Существует метод с гарантированным o(N), но у него есть ряд неприятных особенностей.

wizzard0 June 19th, 2010
Э не. У него это самое N зависит от диапазона значений ключей уже.

nicka_startcev June 19th, 2010
А это у всех методов зависит.

Если диапазон сравнительно небольшой, а элементов сравнительно много, то o(A)+o(B) будет намного быстрее, чем o(log(A))+o(A). (A - число элементов, B - диапазон).

kodt_rsdn June 19th, 2010
Потому что NlogN - для любых абстрактных данных, над которыми определена операция сравнения.
А если мы знаем что-то большее, - например, что это целые числа, - то можем найти и более эффективные решения. Тот же радикс или подсчёт.

wizzard0 June 19th, 2010
Да, спасибо..

184467440737095 June 19th, 2010
а еще как-то вот так можно.
http://portal.acm.org/citation.cfm?id=509993

wizzard0 June 19th, 2010
О! Читаю.

  • 1
?

Log in

No account? Create an account