Комментарии 29
Великолепно!
«В поисках идеальной сортировки» ))))
Интересно видеть насколько Вы продвинулись по сравнению с прошлыми наработками! Жаль, что Вы не описывали промежуточные этапы (объём кода ж таки со 100 строк вырос во все 400) — очень увлекательно бы понаблюдать как рождаются алгоритмы.
Интересно видеть насколько Вы продвинулись по сравнению с прошлыми наработками! Жаль, что Вы не описывали промежуточные этапы (объём кода ж таки со 100 строк вырос во все 400) — очень увлекательно бы понаблюдать как рождаются алгоритмы.
С тех пор у меня была ещё одна реализация in-place merge сортировки, которая процентов на 20-30 обгоняла quicksort, но в ней использовался небольшой дополнительный массив, и я решил, что незачем её показывать.
А идея там была очень простая. Если в массиве длины N есть отсортированные куски длиной X и (N-X)/2, то мы их можем слить за N сравнений и обменов, используя оставшиеся (N-X)/2 элементов в качестве буфера. В результате длина неотсортированного куска уменьшится вдвое. Сортируем его половину и повторяем процесс :) Максимальное число сравнений — 2*N*log(N), что вдвое хуже чистого MergeSort и сравнимо с QuickSort. Если последние 256 элементов сортировать с помощью дополнительного массива, то мы выигрываем 8*N операций, и на достижимых размерах массивов QuickSort отдыхает…
Была ещё реализация RadixSort для 96-битных чисел, которая обгоняла QuickSort в 6 раз, но там тоже ничего особо интересного — те, кого алгоритмы интересуют, легко бы нашли её сами. А остальные и не поймут, зачем гнаться за константой :)
А идея там была очень простая. Если в массиве длины N есть отсортированные куски длиной X и (N-X)/2, то мы их можем слить за N сравнений и обменов, используя оставшиеся (N-X)/2 элементов в качестве буфера. В результате длина неотсортированного куска уменьшится вдвое. Сортируем его половину и повторяем процесс :) Максимальное число сравнений — 2*N*log(N), что вдвое хуже чистого MergeSort и сравнимо с QuickSort. Если последние 256 элементов сортировать с помощью дополнительного массива, то мы выигрываем 8*N операций, и на достижимых размерах массивов QuickSort отдыхает…
Была ещё реализация RadixSort для 96-битных чисел, которая обгоняла QuickSort в 6 раз, но там тоже ничего особо интересного — те, кого алгоритмы интересуют, легко бы нашли её сами. А остальные и не поймут, зачем гнаться за константой :)
Дык это, randomized quicksort, не? Вроде как
O(n*log(n)) ожидаемое время.
Для quicksort это среднее время. У алгоритма, который нашел автор, n*log(n) — худшее время.
Среднее для классического quicksort. Для тюнингованного quicksort, который я привел,
n*log(n) — worst-case expected-time bound. Поправьте, если ошибаюсь. 
Так в вашем же документе написано, что именно среднее время — n*log(n). И что это эквивалентно случайному перемешиванию массива и выдаче этого в обычный quicksort.
Насколько я понял, это среднее время для любого (даже самого неудачного) входного массива. Quicksort можно написать так, что он даст в среднем n*log(n) для любого массива с попарно различными элементами, но свалится в n^2, если все элементы окажутся одинаковыми. Для такой реализации worst-case expected-time окажется n^2, хотя в среднем, по всем массивам, время по-прежнему будет n*log(n).
А как вы его сделаете устойчивым? Даже среднее время n*log(n) для устойчивого алгоритма без дополнительной памяти было бы интересным результатом.
Но максимальное-то у randomized quicksort все равно n2…
Интересная штука, спасибо!
Вы чувствуете это?
www.youtube.com/user/AlgoRythmics?feature=watch
Внезапное желание станцевать алгоритм!
www.youtube.com/user/AlgoRythmics?feature=watch
Внезапное желание станцевать алгоритм!
Почему вы не хотите выложить исходники на GitHub или хотя бы Bitbucket, Codeplex, SourceForge?
Думаю, следует указать источник 1-ой картинки, а то не все читатели могут знать: www.coursera.org/course/algs4partI или algs4.cs.princeton.edu/home/
фактически, он написан на C — надо только перенести описания переменных в начало функцийОбъявления переменных где попало, в том числе в инициализации цикла for, ещё в C99 разрешили. Другой вопрос, что Microsoft этот стандарт игнорирует.
Описание сражений с документацией напомнило, как я в студенческие годы успешно решил задачу коммивояжёра алгоритмом за N^3 итераций.
К счастью, в некоторых более поздних работах удалось найти способ, позволяющий обойти эту неприятность
Не могли бы вы дать ссылку на работу, в которой описан «чистый» вариант?
Спасибо!
Там хитрая ситуация. В последующих работах решают задачу устойчивого слияния двух фрагментов за линейное время. Понятно, что из возможности такого слияния следует возможность сортировки, но не факт, что такой путь будет самым простым.
Я поискал ссылки на статью о сортировке, в надежде, что кто-нибудь увидел в ней ошибку. Таких не обнаружил, но наткнулся на вот эту работу:
Viliam Geffert; Jyrki Katajainen, Tomi Pasanen, Asymptotically efficient in-place merging, Theoretical Computer Science 237 (2000) 159–181
www.sciencedirect.com/science/article/pii/S0304397598001625
Алгоритм у них сложный и запутанный, поэтому я просматривал его только чтобы понять, пользуются ли они сортировкой блоков, и как различают блоки из первого и второго фрагментов. Ну, и увидел, что они в одной из веток набирают столько ключей, чтобы хватило и на буфер обмена, и на метки блоков. А большего мне и не надо было :)
Я поискал ссылки на статью о сортировке, в надежде, что кто-нибудь увидел в ней ошибку. Таких не обнаружил, но наткнулся на вот эту работу:
Viliam Geffert; Jyrki Katajainen, Tomi Pasanen, Asymptotically efficient in-place merging, Theoretical Computer Science 237 (2000) 159–181
www.sciencedirect.com/science/article/pii/S0304397598001625
Алгоритм у них сложный и запутанный, поэтому я просматривал его только чтобы понять, пользуются ли они сортировкой блоков, и как различают блоки из первого и второго фрагментов. Ну, и увидел, что они в одной из веток набирают столько ключей, чтобы хватило и на буфер обмена, и на метки блоков. А большего мне и не надо было :)
Спасибо!
Ошибку, возможно, не обнаружили, потому что алгоритм не практичный. Наверное, никто особо не хотел его реализовывать.
А может, обнаружили, но забили. Дыры в алгоритмах иногда проще найти практику, нежели теоретику. Но практики не сильно заинтересованы в публикациях.
У меня коллеги как-то реализовывали алгоритм (точнее, целый комплекс алгоритмов) из одной очень продвинутой и котируемой американской диссертации.
В результате применения этих наработок в рамках большого промышленного проекта, выяснилось, что в диссертации огромная дырень, из-за которой вся диссертация должна лететь в трубу. Опровержения они не выпустили. Наверное, потому, что не было конструктива: как латать дыру, никто не знал. Писали автору, но он проигнорировал их письма :)
Ошибку, возможно, не обнаружили, потому что алгоритм не практичный. Наверное, никто особо не хотел его реализовывать.
А может, обнаружили, но забили. Дыры в алгоритмах иногда проще найти практику, нежели теоретику. Но практики не сильно заинтересованы в публикациях.
У меня коллеги как-то реализовывали алгоритм (точнее, целый комплекс алгоритмов) из одной очень продвинутой и котируемой американской диссертации.
В результате применения этих наработок в рамках большого промышленного проекта, выяснилось, что в диссертации огромная дырень, из-за которой вся диссертация должна лететь в трубу. Опровержения они не выпустили. Наверное, потому, что не было конструктива: как латать дыру, никто не знал. Писали автору, но он проигнорировал их письма :)
Этап B2 можно сильно ускорить. Пока число G достаточно мало, может случиться так, что (K/2)^2>=2*G. В этом случае мы можем разделить множество ключей пополам, и половину использовать в качестве буфера обмена (а вторую половину — как ключи), и сливать фрагменты с помощью более быстрого метода из A2. А на обмены без буфера перейти в самом конце, когда G приблизится к размеру массива.
Чем больше у нас разных ключей, тем дольше работает слияние без буфера, но и тем дольше мы можем обойтись без него.
Эксперименты показывают, что в самом неблагоприятном случае из тех, что я проверял, алгоритму требуется не больше, чем 1.7*N*log2N сравнений и 2.2*N*log2N обменов (при N>1000000, на случайных данных с заранее заданным числом различных ключей). Хотя я ещё поищу случай похуже (например, 2^k-1 различных ключей — там алгоритму будет очень плохо).
Чем больше у нас разных ключей, тем дольше работает слияние без буфера, но и тем дольше мы можем обойтись без него.
Эксперименты показывают, что в самом неблагоприятном случае из тех, что я проверял, алгоритму требуется не больше, чем 1.7*N*log2N сравнений и 2.2*N*log2N обменов (при N>1000000, на случайных данных с заранее заданным числом различных ключей). Хотя я ещё поищу случай похуже (например, 2^k-1 различных ключей — там алгоритму будет очень плохо).
В Вики появился алгоритм «BlockSort», основанный на той же самой идее: en.wikipedia.org/wiki/Block_sort
И его версия на GitHub: github.com/BonzaiThePenguin/WikiSort
Автор ссылается на статью 2008 года.
И его версия на GitHub: github.com/BonzaiThePenguin/WikiSort
Автор ссылается на статью 2008 года.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрая, экономная, устойчивая…