Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 67
судя по описанию алгоритма, они ничем не отличается от обычной сортировки слиянием, кроме месторасположения буфера обмена.
Буфер обмена находится в том же массиве, в котором находятся данные. И, соответственно, содержит часть этих данных. При этом никакие данные при сортировке не теряются (все операции — обмены элементов), и, в конечном итоге, содержимое «буфера обмена» оказывается всортированным в общий массив.
Не используйте qsort(), разве что когда пишете на чистом Си. Используя qsort() вместо std::sort() вы препятствуете инлайнингу и методично отбрасываете всю ту информацию о типах, которая изначально была.
С таким quick sort сравните.
Мой код примерно вдвое медленнее.
UPD. После небольшой оптимизации разрыв сократился до 1.3 раза. У vector.sort алгоритм теперь выигрывает 1.6-1.7 раза по времени.
Странно быстрый какой-то алгоритм Ваш. Колдовство. Надо будет разобраться, может это новый лидер?)
Лидер среди кого? Гарантированных O(N*log(N)) с не более, чем log(N) дополнительной памяти? Не знаю, я давно за прогрессом не следил. Думаю, что на «почти отсортированных массивах» мой алгоритм проиграет. Обогнать базовый merge (с N/2 дополнительной памяти) и хорошо написанный QuickSort (по среднему времени) практически нереально. Ну, и неизвестно, что будет на других типах (не на int) и при передаче функции сравнения параметром.
Когда я пытался разобраться в первом из этих алгоритмов, мне показалось, что он квадратичный по времени. Возможно, я ошибаюсь — надо будет проверить их на скорость. Но в комментариях ничего не говорится про число операций.
Что касается «структур с последовательным доступом» — имеются в виду связанные списки? Так с ними все ясно — для них сортировка слиянием пишется легко, за log(N) памяти. На этом основано, в частности, перемножение разреженных многочленов за M*N*log(min(M,N)) операций, где M и N — число мономов в операндах.
Что касается «структур с последовательным доступом» — имеются в виду связанные списки? Так с ними все ясно — для них сортировка слиянием пишется легко, за log(N) памяти. На этом основано, в частности, перемножение разреженных многочленов за M*N*log(min(M,N)) операций, где M и N — число мономов в операндах.
Первый алгоритм интересный. Чтобы слить две отсортированные части массива, они делят длинную часть пополам (на части A1 и A2), потом короткую часть B делят на две части B1 и B2 так, чтобы max(B1)<=min(A2), min(B2)>=max(A1). Потом переставляют фрагменты A2 и B1, и сливают A1 c B1, а A2 с B2.
Как вы думаете? Это гарантированное N*log(N)? Если да, то константа довольно большая — в среднем он в 6-7 раз медленнее, чем msort (экспериментальный результат).
Как вы думаете? Это гарантированное N*log(N)? Если да, то константа довольно большая — в среднем он в 6-7 раз медленнее, чем msort (экспериментальный результат).
Нет, N*log(N) — только на merge. На всю сортировку N*log(N)^2. Оно и видно.
а если вместо слияния A1 с B1 и A2 с B2 задать рекурсию, которая будет разбивать на части и переставлять до массива из двух переменных?
Так ведь «слияние» — это и есть рекурсия. Которая переставляет части, разбивает их на более мелкие куски, снова переставляет… Проблема в том, что на каждом уровне глубины рекурсии приходится переставлять примерно N/2 элементов — в итоге мы получаем O(N*log(N)) обменов.
я уже говорю про ту часть, когда у нас есть два отсортированных подмассива, и надо слить в один, для этого использовать другую рекурсию, где сначала создаются A1 A2 B1 B2, B1 и A2 меняются местами и эта же операция выполняется для A1 B1 и A2 B2
В итоге эта рекурсия в худшем случае займёт дополнительно N*log(N) операций
В итоге эта рекурсия в худшем случае займёт дополнительно N*log(N) операций
Правильно, так и делается. Merge проходит за N*log(N) операций. А для полной сортировки массива его надо вызвать на log(N) уровнях, и на каждом он потребует N*log(K) операций, где K — длина фрагментов, которые мы сливаем на этом уровне (сначала по 2, потом по 4 элемента и т.д.). В сумме выйдет O(N*log(N)^2) обменов на всю сортировку.
Тот код на плюсах написан, а у автора — чистый С, что иногда бывает очень даже нужно.
Там заменить template на #define — и будет еще более чистый C. Даже все переменные в начале описаны.
Объясните про «Здесь нам нужно использовать алгоритм, линейный по числу обменов. Подходит сортировка выбором минимального элемента.» Имеется ввиду, что К заранее известно, является небольшим числом и сортировка проходит «в ручную» заранее запрограммированной сортирующей сетью? — тогда там не линейный алгоритм со сложностью O(n*log(n)). Если К заранее неизвестно, то сложность сортировки выбором минимального элемента — O(n^2)
Нет, K неизвестно. И число сравнений при сортировке может быть O(K^2). Но вот число реальных перемещений данных должно быть O(K). В самом деле, каждый блок занимает S элементов, и даже если мы выберем алгоритм, работающий за O(K*log(K)) сравнений и O(K*log(K)) обменов, то полное время работы этапа алгоритма будет O(N*log(K)) (где N=S*K) — сравнение двух блоков идет за O(1), а обмен за O(S) — а это слишком много. Поэтому, берется алгоритм со сложностью O(K) обменов и O(K^2) сравнений. Если S>=sqrt(N), то сложность сортировки блоков будет O(N).
github.com/swenson/sort — Shell sort, Binary insertion sort, Heap sort, Quick sort, Merge sort, Bubble sort (ugh), Tim sort в виде макросов.
Особенно рекомендую попробовать Tim sort.
Особенно рекомендую попробовать Tim sort.
Заставить его работать под Visual Studio толком не удалось. Кое-как добился, что он компилируется, но в итоге tim_sort, хоть и запустился, стал выдавать неправильные результаты. И тратить на это в 1.4 раза больше времени, чем мой алгоритм.
Хм. Интересно, как вам это удалось… У меня конкретно этот код работает под хорошей такой нагрузкой последние три месяца.
Правда, никакого Visual Studio — только Linux, только хардкор ©.
Правда, никакого Visual Studio — только Linux, только хардкор ©.
Удалось легко — я забыл закомментарить строчку
#define SORT_CMP(x, y) (x — y)
В результате сравнение стало нетранзитивным. После исправления алгоритм заработал. На большинстве тестов он в 1.8 раза медленнее, чем мой, но один раз (на массиве размером 12.5 млн) выдал время 27 секунд против 1.6 (т.е. проиграл 17 раз).
#define SORT_CMP(x, y) (x — y)
В результате сравнение стало нетранзитивным. После исправления алгоритм заработал. На большинстве тестов он в 1.8 раза медленнее, чем мой, но один раз (на массиве размером 12.5 млн) выдал время 27 секунд против 1.6 (т.е. проиграл 17 раз).
Пересобрал под x64. Разрыв скорости сократился до 15%.
Ок, вы меня заинтересовали =) Как собрать ваш пример?
Споткнулся на этом:
mmerge.cpp: In function ‘void msort(int*, int)’:
mmerge.cpp:105:15: error: ‘s’ was not declared in this scope
Споткнулся на этом:
mmerge.cpp: In function ‘void msort(int*, int)’:
mmerge.cpp:105:15: error: ‘s’ was not declared in this scope
Странно. Переменная s описана в предыдущей строчке. Возможно, я где-то не до конца соблюдаю стандарт языка: на C++ я пишу в среднем 2 раза в год, так что многое мог забыть или вообще не знать.
Там почему-то была 'a', а не 's'. Ну да бог с ним, не важно.
Действительно, на рандомных данных tim sort выходит процентов на 12-15 медленнее, чем этот алгоритм. Любопытно.
Я только не совсем понял — как этот подвид merge sort называется? merge sort with extra memory? А где тут extra memory?
Действительно, на рандомных данных tim sort выходит процентов на 12-15 медленнее, чем этот алгоритм. Любопытно.
Я только не совсем понял — как этот подвид merge sort называется? merge sort with extra memory? А где тут extra memory?
Он называется «In-Place Merge Sort». Выше уже были комментарии об этом. Как называется подвид, работающий за N*log(N), и выделяется ли он вообще в отдельный класс — не знаю.
Не возражаете, если я его сюда github.com/swenson/sort добавлю?
(и что написать в копирайте?)
(и что написать в копирайте?)
В алгоритме есть логическая ошибка. Поэтому пока отправлять не стоит :) Надеюсь, что я ее смогу быстро исправить.
Ошибку исправил, файл выгрузил на astr73.narod.ru/Files/msort.cpp
Так что можно добавлять. Копирайт там внутри поставлен, © Andrey Astrelin.
Так что можно добавлять. Копирайт там внутри поставлен, © Andrey Astrelin.
Ok, here you go: github.com/tony2001/sort/
Комментарии приветствуются.
Можно просто собрать и прогнать тесты.
demo на 100000 даёт такой результат:
Running tests
stdlib qsort time: 13593.00 us per iteration
quick sort time: 7162.00 us per iteration
bubble sort time: 16568472.00 us per iteration
merge sort time: 9386.00 us per iteration
binary insertion sort time: 1676846.00 us per iteration
heap sort time: 11884.00 us per iteration
shell sort time: 12984.00 us per iteration
tim sort time: 10967.00 us per iteration
in-place merge sort time: 8215.00 us per iteration < — NB
Комментарии приветствуются.
Можно просто собрать и прогнать тесты.
demo на 100000 даёт такой результат:
Running tests
stdlib qsort time: 13593.00 us per iteration
quick sort time: 7162.00 us per iteration
bubble sort time: 16568472.00 us per iteration
merge sort time: 9386.00 us per iteration
binary insertion sort time: 1676846.00 us per iteration
heap sort time: 11884.00 us per iteration
shell sort time: 12984.00 us per iteration
tim sort time: 10967.00 us per iteration
in-place merge sort time: 8215.00 us per iteration < — NB
Ну так тестировать то надо не на случайных данных.
на случайных данных тимсорт примерно 10-15 процентов и проигрывает стандартному мерджсорту
а вот если взять упорядоченный массив и слегка его «попортить» перестановками, то тим сорт раза в 2 уже выигрывает
на случайных данных тимсорт примерно 10-15 процентов и проигрывает стандартному мерджсорту
а вот если взять упорядоченный массив и слегка его «попортить» перестановками, то тим сорт раза в 2 уже выигрывает
Сравнил msort, std::sort и timsort в разных ситуациях (правда, msort пришлось слегка подправить, чтобы он не портил уже отсортированные участки).
Длина массива была одинаковой — N=10^8 элементов.
В первом тесте массив заполнялся случайными целыми числами.
В втором и третьем тестах числа брались из ограниченного диапазона — от 0 до 19 и от 0 до 999 соответственно (т.е. было много одинаковых элементов).
В следующих трех тестах массив состоял из отсортированных блоков (длиной 7, 97 и 9997 элементов соответственно).
В двух последних тестах брался отсортированный массив в нем делалось несколько случайных транспозиций — N/2 и N/8 соответственно (т.е. примерно 0.36*N элементов в первом случае и 0.78*N — во втором оставались на местах).
Результаты (время — в миллисекундах):
Random
msort: Ok, time=21044
std::sort: Ok, time=22027
TimSort: Ok, time=30030
20 different values
msort: Ok, time=13416
std::sort: Ok, time=3260
TimSort: Ok, time=21341
1000 different values
msort: Ok, time=15896
std::sort: Ok, time=7894
TimSort: Ok, time=24804
sorted blocks of length 7
msort: Ok, time=20598
std::sort: Ok, time=22090
TimSort: Ok, time=29703
sorted blocks of length 97
msort: Ok, time=18657
std::sort: Ok, time=20919
TimSort: Ok, time=21356
sorted blocks of length 9997
msort: Ok, time=14399
std::sort: Ok, time=18751
TimSort: Ok, time=14851
swapped N/2 pairs
msort: Ok, time=17924
std::sort: Ok, time=20904
TimSort: Ok, time=25849
swapped N/8 pairs
msort: Ok, time=13519
std::sort: Ok, time=16520
TimSort: Ok, time=20545
Длина массива была одинаковой — N=10^8 элементов.
В первом тесте массив заполнялся случайными целыми числами.
В втором и третьем тестах числа брались из ограниченного диапазона — от 0 до 19 и от 0 до 999 соответственно (т.е. было много одинаковых элементов).
В следующих трех тестах массив состоял из отсортированных блоков (длиной 7, 97 и 9997 элементов соответственно).
В двух последних тестах брался отсортированный массив в нем делалось несколько случайных транспозиций — N/2 и N/8 соответственно (т.е. примерно 0.36*N элементов в первом случае и 0.78*N — во втором оставались на местах).
Результаты (время — в миллисекундах):
Random
msort: Ok, time=21044
std::sort: Ok, time=22027
TimSort: Ok, time=30030
20 different values
msort: Ok, time=13416
std::sort: Ok, time=3260
TimSort: Ok, time=21341
1000 different values
msort: Ok, time=15896
std::sort: Ok, time=7894
TimSort: Ok, time=24804
sorted blocks of length 7
msort: Ok, time=20598
std::sort: Ok, time=22090
TimSort: Ok, time=29703
sorted blocks of length 97
msort: Ok, time=18657
std::sort: Ok, time=20919
TimSort: Ok, time=21356
sorted blocks of length 9997
msort: Ok, time=14399
std::sort: Ok, time=18751
TimSort: Ok, time=14851
swapped N/2 pairs
msort: Ok, time=17924
std::sort: Ok, time=20904
TimSort: Ok, time=25849
swapped N/8 pairs
msort: Ok, time=13519
std::sort: Ok, time=16520
TimSort: Ok, time=20545
О, а есть код этих тестов?
Я бы прогнал их на алгоритмах из sort.h чисто любопытства ради.
Я бы прогнал их на алгоритмах из sort.h чисто любопытства ради.
Выгрузил свежую версию алгоритма вместе с кодом тестов туда же: astr73.narod.ru/Files/msort.cpp
ок, добавил.
результаты тестов тут: pastebin.com/v0PcruiR
результаты тестов тут: pastebin.com/v0PcruiR
Спасибо. Это на какой длине массива?
там тысяча прогонов с рандомной длиной массива от 0 до 25600.
размеры массивов генерятся 1 раз для всех тестов.
размеры массивов генерятся 1 раз для всех тестов.
Жесткие условия…
Автор sort.h спрашивает — вы согласны законтрибутить код под лицензией MIT?
Думаю, да. А что ему показалось похожим на tim sort? Если алгоритм в целом — то у них почти ничего общего (кроме слова merge)
Не знаю. Но думаю, что вряд ли можно понять алгоритм за несколько минут =)
Да, особенно нерекурсивный merge sort, основанный на двоичном разложении индекса :D
Попробую еще добавить эффективную сортировку четверок последовательных элементов. Может быть, чего-нибудь выиграю.
Кстати, merge sort с дополнительным буфером, написанный в том же стиле, быстрее, чем msort, всего на 10-15%.
Попробую еще добавить эффективную сортировку четверок последовательных элементов. Может быть, чего-нибудь выиграю.
Кстати, merge sort с дополнительным буфером, написанный в том же стиле, быстрее, чем msort, всего на 10-15%.
А про CLZ пишут, что она только для архитектуры ARM :(
И где он увидел in-place merge в tim sort? Строчка
TIM_SORT_RESIZE(store, MIN(A, B));
показывает, что он совсем не in-place, а использует дополнительную память.
TIM_SORT_RESIZE(store, MIN(A, B));
показывает, что он совсем не in-place, а использует дополнительную память.
Интересно, что простой merge стал сильно лучше, чем в тесте на 100000.
Похоже, что критически важным для данного теста является отстутствие встраиваимости сравнения в std::sort. После того, как вместо указателя на функцию передан функциональный объект (lambda), или используется сравнение по-умолчанию, std::sort ускоряется почти в 2 раза.
Немного скорректировал тест:
— Убрал инициализацию вектора (по ошибке время его создания учитывалось для теста std::sort)
— Сортировка отлично работает для массивов, вообще убрал std::vector (но это не думаю, что важно)
— Убрал подсчёт сравнений из всех тестов, и передал функциональный объект (lambda). Попробовал без собственного компаратора. Использование указателя на функцию как параметр std::sort не желателен, так как сравнение не встраивается (inline). lambda отлично встраивается. В вашей сортировке компилятор, думаю, встраивает сравнения:
Времена (Visual Studio 2010, Release). std::sort быстрее примерно процентов на 10 (не важно с lambda или без):
N=195312
result: Ok, ncmp=0, time=28
std::sort: Ok, ncmp=0, time=24
std::sort (slow, no inlining): Ok, ncmp=0, time=41
…
N=3124995
result: Ok, ncmp=0, time=556
std::sort: Ok, ncmp=0, time=489
std::sort (slow, no inlining): Ok, ncmp=0, time=894
…
N=99999847
result: Ok, ncmp=0, time=21389
std::sort: Ok, ncmp=0, time=19002
std::sort (slow, no inlining): Ok, ncmp=0, time=32529
Немного скорректировал тест:
— Убрал инициализацию вектора (по ошибке время его создания учитывалось для теста std::sort)
— Сортировка отлично работает для массивов, вообще убрал std::vector (но это не думаю, что важно)
— Убрал подсчёт сравнений из всех тестов, и передал функциональный объект (lambda). Попробовал без собственного компаратора. Использование указателя на функцию как параметр std::sort не желателен, так как сравнение не встраивается (inline). lambda отлично встраивается. В вашей сортировке компилятор, думаю, встраивает сравнения:
bool myfunction (int i,int j) { return (i<j); }
...
t1=clock();
// sort (A, A+N, myfunction ); => slower then next 2 lines by 1.7x
// sort (A, A+N, []( int i, int j) { return i<j; } );
sort (A, A+N );
t2=clock();
Времена (Visual Studio 2010, Release). std::sort быстрее примерно процентов на 10 (не важно с lambda или без):
N=195312
result: Ok, ncmp=0, time=28
std::sort: Ok, ncmp=0, time=24
std::sort (slow, no inlining): Ok, ncmp=0, time=41
…
N=3124995
result: Ok, ncmp=0, time=556
std::sort: Ok, ncmp=0, time=489
std::sort (slow, no inlining): Ok, ncmp=0, time=894
…
N=99999847
result: Ok, ncmp=0, time=21389
std::sort: Ok, ncmp=0, time=19002
std::sort (slow, no inlining): Ok, ncmp=0, time=32529
Заметил, что, если использовать для сравнения макрос iGT(a,b) (*(a)>*(b)), то ваша сортировка идёт вровень с std::sort. Мне кажется, что это очень достойный результат с учётом того, что std::sort использует другую сортировку на малых размерах и, возможно, ещё какие-нибудь оптимизации.
Я попробовал наоборот:
— добавил в свой код функциональный объект;
— тоже применил std::sort к массиву.
Получилось:
N=195312
mmsort: Ok, time=16
std::sort: Ok, time=15
…
N=3124995
mmsort: Ok, time=422
std::sort: Ok, time=437
…
N=49999923
mmsort: Ok, time=7738
std::sort: Ok, time=8456
N=99999847
mmsort: Ok, time=16551
std::sort: Ok, time=17455
std::sort медленнее процентов на 5. Возможно, повлияло то, что все функции, кроме msort, при переделке получились inline.
— добавил в свой код функциональный объект;
— тоже применил std::sort к массиву.
Получилось:
N=195312
mmsort: Ok, time=16
std::sort: Ok, time=15
…
N=3124995
mmsort: Ok, time=422
std::sort: Ok, time=437
…
N=49999923
mmsort: Ok, time=7738
std::sort: Ok, time=8456
N=99999847
mmsort: Ok, time=16551
std::sort: Ok, time=17455
std::sort медленнее процентов на 5. Возможно, повлияло то, что все функции, кроме msort, при переделке получились inline.
На типе double мой алгоритм проиграл вчистую — std::sort там в 1.3 раза быстрее :(
Рискну предположить, что производительность msort сильно зависит от соотношения стоимостей операции swap и операции сравнения. Видимо он делает меньше сравнений, но больше перестановок.
То есть, std::string — благоприятный тип: дешёвый предсказуемый swap, сравнение дороже
А вот int[100] будет неудобен: swap — дорогой, а сравнение дешёвое.
То есть, std::string — благоприятный тип: дешёвый предсказуемый swap, сравнение дороже
А вот int[100] будет неудобен: swap — дорогой, а сравнение дешёвое.
>Сортируем буфер обмена: в нем были и остались R младших элементов массива
Почему это? Это же неправда, взять хотя бы тест 1 2 3 4 5 -5 -4 -3 -2 -1
Почему это? Это же неправда, взять хотя бы тест 1 2 3 4 5 -5 -4 -3 -2 -1
Разумеется. В предыдущем пункте («Ищем на стыке предыдущего и следующего пунктов ошибку в алгоритме...») и в самом конце статьи как раз об этом и говорится :)
Вообще-то в тесте нет одинаковых элементов
Вам может быть интересно: github.com/BonzaiThePenguin/WikiSort (идея та же самая)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка слиянием без использования дополнительной памяти