Заводчик кардиганов
0,0
рейтинг
14 февраля 2012 в 00:37

Разработка → Сортировка слиянием без использования дополнительной памяти

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.



Слияние за линейное время



Идея алгоритма довольно простая. Все, что нам нужно – это слить две упорядоченные части одного массива за O(N) сравнений и обменов элементов. Делается это так:
  • Выбираем число S≈sqrt(N)
  • Делим массив на K кусков длины S. Остаток, не попавший ни в один из кусков, пока не трогаем
  • Кусок, в который попала граница между упорядоченными фрагментами, меняем с последним куском. Это будет наш буфер обмена
  • Сортируем K-1 оставшийся кусок по возрастанию первых элементов. Здесь нам нужно использовать алгоритм, линейный по числу обменов. Подходит сортировка выбором минимального элемента.
  • Замечаем две важные вещи. Во-первых, если у нас есть два поряд идущих отсортированных фрагмента длиной A и B и буфер обмена, длина которого не меньше min(A,B), то мы можем слить эти фрагменты, затратив не более A+B сравнений и A+B+min(A,B) обменов. Порядок элементов в буфере обмена при этом может измениться. Во-вторых, при сортировке полученного на предыдущем шаге массива из (K-1)*S элементов, каждый элемент может сдвинуться не более, чем на S позиций влево, т.е. никогда не окажется левее предыдущего «куска».
  • Пользуясь буфером обмена, последовательно сливаем пары соседних кусков – [0..S-1] и [S,2*S-1], потом [S,2*S-1] и [2*S,3*S-1], и т.д. Из предыдущего пункта следует, что в результате мы получим отсортированный массив из M=S*(K-1) элементов
  • Сортируем последние R=N-M элементов исходного массива (буфер обмена+остаток) любым алгоритмом. Они рекомендуют какой-нибудь квадратичный алгоритм (для чистоты идеи, чтобы избежать рекурсии), но с практической точки зрения, рекурсивный вызов сортировки не хуже.
  • Сливаем отсортированные фрагменты массива [R..N-R-1] и [N-R..N-1], используя фрагмент [0..R-1] как буфер обмена
  • Ищем на стыке предыдущего и следующего пунктов ошибку в алгоритме. Если не найдете – она объясняется в конце статьи
  • Сортируем буфер обмена: в нем были и остались R младших элементов массива, и после сортировки они окажутся на месте

Описание довольно длинное, но понять можно. Число обменов на одно слияние – примерно 5*N, число сравнений – около 6*N (оно зависит от длины остатка). Для полной сортировки эти числа умножаются на log(N), и получается много.

Адаптация алгоритма для сортировки



Чтобы нам было попроще, а алгоритм работал эффективнее, заметим следующее.
  • Вся возня с буфером обмена и его последующее слияние с массивом нужны только если в массиве в самом деле не было свободного места. Если мы сливаем фрагменты длиной A и B, а после них есть еще хотя бы S ячеек неотсортированного пространства, то нам достаточно разбить массивы на куски, отсортировать их и слить. Особенно эффективно это будет работать, если S=A=B.
  • Надо постараться, чтобы длина остатка была нулевой, а граница между отсортированными фрагментами попала точно на границу кусков длины S. Проще всего этого добиться, если выбрать S равным степени двойки, а A и B заставить делиться на него.
  • Сортировка кусков массивов требует ((A+B)/S)2/2 сравнений. Последующая сортировка буфера обмена – O(S*log( S )) сравнений. Поэтому выбирать S близким к sqrt(N) не обязательно, можно увеличить его, например, до N/log(N).


Вооружившись этими мыслями, пишем программу (пока только для массива типа int[]). Сначала сортируем и сливаем фрагменты с длинами, равными степени двойки, причем идем строго слева направо, чтобы правее было свободное место. Когда дойдем до буфера обмена, сливаем неслитые, но отсортированные фрагменты. Сортируем буфер обмена+остаток, сливаем результат с остальной частью массива, сортируем вновь получившийся буфер обмена — и массив отсортирован. Получается алгоритм примерно в сотню строк. Правду сказали, что он громоздкий. А как насчет эффективности?

Честно говоря, я надеялся, что он проиграет стандарному qsort не более 3 раз. Но сравнение в реальных условиях (на массивах длиной до 108) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от 1.2 до 1.3 раз! Возможно, это связано с тем, что функция icmp (сравнение двух целых чисел по данным адресам) подставляется inline – но код, который вставляется, получается довольно ужасным (я проверял).

В целом, все не так плохо, как говорили.

А что же за ошибка была в описании алгоритма? Дело в том, что если в буфер обмена или в остаток попал элемент, который после сортировки должен находиться в одной из первых R позиций, то в итоге он на место никак не попадет. Для исправления приходится следить, на какое место попал при последнем слиянии элемент, находившийся в ячейке с индексом R, и финальную сортировку делать начальному фрагменту до этого места (его длина может быть несколько больше чем R).

UPD: В алгоритме, как я его здесь описал, обнаружилась еще одна ошибка, относящаяся к «сортировке кусков массива». В случае, если в исходном массиве много одинаковых элементов, у разных кусков из одного фрагмента массива могут оказаться одинаковые первые элементы. И если порядок, в котором идут эти куски, при сортировке будет нарушен, то результат сортировки всего массива может оказаться неверным.

Для борьбы с этим эффектом при сортировке надо сравнивать первые элементы кусков, а если они одинаковы — сравнить последние элементы. И сортировать куски лексикографически по этим парам элементов.
Андрей @Mrrl
карма
346,7
рейтинг 0,0
Заводчик кардиганов
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (67)

  • 0
    судя по описанию алгоритма, они ничем не отличается от обычной сортировки слиянием, кроме месторасположения буфера обмена.
  • +2
    Буфер обмена находится в том же массиве, в котором находятся данные. И, соответственно, содержит часть этих данных. При этом никакие данные при сортировке не теряются (все операции — обмены элементов), и, в конечном итоге, содержимое «буфера обмена» оказывается всортированным в общий массив.
  • 0
    Не используйте qsort(), разве что когда пишете на чистом Си. Используя qsort() вместо std::sort() вы препятствуете инлайнингу и методично отбрасываете всю ту информацию о типах, которая изначально была.
    • +2
      Попробую. Заодно вспомню, как с этим работать.
    • +2
      Попробовал. Выигрыш по времени сократился до 10%, а по числу сравнений — увеличился до 1.5 раз.
  • +1
    С таким quick sort сравните.
    • 0
      Мой код примерно вдвое медленнее.
      • 0
        UPD. После небольшой оптимизации разрыв сократился до 1.3 раза. У vector.sort алгоритм теперь выигрывает 1.6-1.7 раза по времени.
        • 0
          Странно быстрый какой-то алгоритм Ваш. Колдовство. Надо будет разобраться, может это новый лидер?)
          • 0
            Лидер среди кого? Гарантированных O(N*log(N)) с не более, чем log(N) дополнительной памяти? Не знаю, я давно за прогрессом не следил. Думаю, что на «почти отсортированных массивах» мой алгоритм проиграет. Обогнать базовый merge (с N/2 дополнительной памяти) и хорошо написанный QuickSort (по среднему времени) практически нереально. Ну, и неизвестно, что будет на других типах (не на int) и при передаче функции сравнения параметром.
            • 0
              Насколько я понял, предложенная сортировка есть In-Place Merge Sort, неплохо гуглится (например вот или вот. В англ. вики отметили, что сортровка слиянием является эффективней быстрой сортировки на структурах с последовательным доступом.
              • 0
                Когда я пытался разобраться в первом из этих алгоритмов, мне показалось, что он квадратичный по времени. Возможно, я ошибаюсь — надо будет проверить их на скорость. Но в комментариях ничего не говорится про число операций.
                Что касается «структур с последовательным доступом» — имеются в виду связанные списки? Так с ними все ясно — для них сортировка слиянием пишется легко, за log(N) памяти. На этом основано, в частности, перемножение разреженных многочленов за M*N*log(min(M,N)) операций, где M и N — число мономов в операндах.
              • 0
                Первый алгоритм интересный. Чтобы слить две отсортированные части массива, они делят длинную часть пополам (на части 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 (экспериментальный результат).
                • 0
                  Нет, N*log(N) — только на merge. На всю сортировку N*log(N)^2. Оно и видно.
                • +1
                  а если вместо слияния A1 с B1 и A2 с B2 задать рекурсию, которая будет разбивать на части и переставлять до массива из двух переменных?
                  • 0
                    Так ведь «слияние» — это и есть рекурсия. Которая переставляет части, разбивает их на более мелкие куски, снова переставляет… Проблема в том, что на каждом уровне глубины рекурсии приходится переставлять примерно N/2 элементов — в итоге мы получаем O(N*log(N)) обменов.
                    • 0
                      я уже говорю про ту часть, когда у нас есть два отсортированных подмассива, и надо слить в один, для этого использовать другую рекурсию, где сначала создаются A1 A2 B1 B2, B1 и A2 меняются местами и эта же операция выполняется для A1 B1 и A2 B2
                      В итоге эта рекурсия в худшем случае займёт дополнительно N*log(N) операций
                      • 0
                        Правильно, так и делается. Merge проходит за N*log(N) операций. А для полной сортировки массива его надо вызвать на log(N) уровнях, и на каждом он потребует N*log(K) операций, где K — длина фрагментов, которые мы сливаем на этом уровне (сначала по 2, потом по 4 элемента и т.д.). В сумме выйдет O(N*log(N)^2) обменов на всю сортировку.
                        • 0
                          Согласен.
    • 0
      Тот код на плюсах написан, а у автора — чистый С, что иногда бывает очень даже нужно.
      • 0
        Там заменить template на #define — и будет еще более чистый C. Даже все переменные в начале описаны.
        • 0
          Лучше, наверное, будет не #define делать, а просто сделать свою функцию сортировки для каждого типа данных (sortf, sortd, sorti и т.п.), как это, по сути, и реализуется в плюсах после разворачивания компилятором кода с шаблоном.
          • +1
            Да. И чтобы не дублировать код, сделать это как-нибудь так:
            #define T int
            #define ___sort sorti
            #include «quicki.c»
            #undef ___sort
            #undef T

            #define T float
            #define ___sort sortf
            #include «quicki.c»
            #undef ___sort
            #undef T

            и так далее. Наверное, можно как-нибудь красивее, но лень искать.
  • 0
    Объясните про «Здесь нам нужно использовать алгоритм, линейный по числу обменов. Подходит сортировка выбором минимального элемента.» Имеется ввиду, что К заранее известно, является небольшим числом и сортировка проходит «в ручную» заранее запрограммированной сортирующей сетью? — тогда там не линейный алгоритм со сложностью O(n*log(n)). Если К заранее неизвестно, то сложность сортировки выбором минимального элемента — O(n^2)
  • 0
    Нет, 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).
  • 0
    github.com/swenson/sort — Shell sort, Binary insertion sort, Heap sort, Quick sort, Merge sort, Bubble sort (ugh), Tim sort в виде макросов.
    Особенно рекомендую попробовать Tim sort.
    • 0
      Заставить его работать под Visual Studio толком не удалось. Кое-как добился, что он компилируется, но в итоге tim_sort, хоть и запустился, стал выдавать неправильные результаты. И тратить на это в 1.4 раза больше времени, чем мой алгоритм.
      • 0
        Хм. Интересно, как вам это удалось… У меня конкретно этот код работает под хорошей такой нагрузкой последние три месяца.
        Правда, никакого Visual Studio — только Linux, только хардкор ©.
        • 0
          Удалось легко — я забыл закомментарить строчку
          #define SORT_CMP(x, y) (x — y)
          В результате сравнение стало нетранзитивным. После исправления алгоритм заработал. На большинстве тестов он в 1.8 раза медленнее, чем мой, но один раз (на массиве размером 12.5 млн) выдал время 27 секунд против 1.6 (т.е. проиграл 17 раз).
          • 0
            Пересобрал под x64. Разрыв скорости сократился до 15%.
            • 0
              Ок, вы меня заинтересовали =) Как собрать ваш пример?
              Споткнулся на этом:
              mmerge.cpp: In function ‘void msort(int*, int)’:
              mmerge.cpp:105:15: error: ‘s’ was not declared in this scope
              • 0
                Странно. Переменная s описана в предыдущей строчке. Возможно, я где-то не до конца соблюдаю стандарт языка: на C++ я пишу в среднем 2 раза в год, так что многое мог забыть или вообще не знать.
                • 0
                  Там почему-то была 'a', а не 's'. Ну да бог с ним, не важно.

                  Действительно, на рандомных данных tim sort выходит процентов на 12-15 медленнее, чем этот алгоритм. Любопытно.

                  Я только не совсем понял — как этот подвид merge sort называется? merge sort with extra memory? А где тут extra memory?
                  • 0
                    Он называется «In-Place Merge Sort». Выше уже были комментарии об этом. Как называется подвид, работающий за N*log(N), и выделяется ли он вообще в отдельный класс — не знаю.
                    • 0
                      Не возражаете, если я его сюда github.com/swenson/sort добавлю?
                      (и что написать в копирайте?)
                      • 0
                        В алгоритме есть логическая ошибка. Поэтому пока отправлять не стоит :) Надеюсь, что я ее смогу быстро исправить.
                      • 0
                        Ошибку исправил, файл выгрузил на astr73.narod.ru/Files/msort.cpp
                        Так что можно добавлять. Копирайт там внутри поставлен, © Andrey Astrelin.
                        • +1
                          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
            • 0
              Ну так тестировать то надо не на случайных данных.
              на случайных данных тимсорт примерно 10-15 процентов и проигрывает стандартному мерджсорту

              а вот если взять упорядоченный массив и слегка его «попортить» перестановками, то тим сорт раза в 2 уже выигрывает
              • 0
                Сравнил 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
                • 0
                  О, а есть код этих тестов?
                  Я бы прогнал их на алгоритмах из sort.h чисто любопытства ради.
                  • 0
                    Выгрузил свежую версию алгоритма вместе с кодом тестов туда же: astr73.narod.ru/Files/msort.cpp
                    • +1
                      ок, добавил.
                      результаты тестов тут: pastebin.com/v0PcruiR
                      • 0
                        Спасибо. Это на какой длине массива?
                        • 0
                          там тысяча прогонов с рандомной длиной массива от 0 до 25600.
                          размеры массивов генерятся 1 раз для всех тестов.
                          • 0
                            Жесткие условия…

                            image
                            • 0
                              Автор sort.h спрашивает — вы согласны законтрибутить код под лицензией MIT?
                              • 0
                                Думаю, да. А что ему показалось похожим на tim sort? Если алгоритм в целом — то у них почти ничего общего (кроме слова merge)
                                • 0
                                  Не знаю. Но думаю, что вряд ли можно понять алгоритм за несколько минут =)
                                  • 0
                                    Да, особенно нерекурсивный merge sort, основанный на двоичном разложении индекса :D
                                    Попробую еще добавить эффективную сортировку четверок последовательных элементов. Может быть, чего-нибудь выиграю.
                                    Кстати, merge sort с дополнительным буфером, написанный в том же стиле, быстрее, чем msort, всего на 10-15%.
                              • 0
                                А про CLZ пишут, что она только для архитектуры ARM :(
                                • 0
                                  у него там рядом своя имплементация, с этим проблем нет.
                              • 0
                                И где он увидел in-place merge в tim sort? Строчка
                                TIM_SORT_RESIZE(store, MIN(A, B));
                                показывает, что он совсем не in-place, а использует дополнительную память.
                      • 0
                        Интересно, что простой merge стал сильно лучше, чем в тесте на 100000.
  • +2
    Похоже, что критически важным для данного теста является отстутствие встраиваимости сравнения в std::sort. После того, как вместо указателя на функцию передан функциональный объект (lambda), или используется сравнение по-умолчанию, std::sort ускоряется почти в 2 раза.

    Немного скорректировал тест:
    — Убрал инициализацию вектора (по ошибке время его создания учитывалось для теста 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
    • +2
      Заметил, что, если использовать для сравнения макрос iGT(a,b) (*(a)>*(b)), то ваша сортировка идёт вровень с std::sort. Мне кажется, что это очень достойный результат с учётом того, что std::sort использует другую сортировку на малых размерах и, возможно, ещё какие-нибудь оптимизации.
      • 0
        Спасибо. И я думаю, что std::sort писали больше, чем полдня.
    • 0
      Я попробовал наоборот:
      — добавил в свой код функциональный объект;
      — тоже применил 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.
  • 0
    На типе double мой алгоритм проиграл вчистую — std::sort там в 1.3 раза быстрее :(
    • 0
      Рискну предположить, что производительность msort сильно зависит от соотношения стоимостей операции swap и операции сравнения. Видимо он делает меньше сравнений, но больше перестановок.

      То есть, std::string — благоприятный тип: дешёвый предсказуемый swap, сравнение дороже
      А вот int[100] будет неудобен: swap — дорогой, а сравнение дешёвое.
      • 0
        Похоже. Если в qsort основной цикл — «сравниваем и иногда меняем», то в msort — либо «сравниваем и меняем всегда», либо «меняем целые блоки, не смотря ни на что».
  • 0
    >Сортируем буфер обмена: в нем были и остались R младших элементов массива
    Почему это? Это же неправда, взять хотя бы тест 1 2 3 4 5 -5 -4 -3 -2 -1
    • 0
      Разумеется. В предыдущем пункте («Ищем на стыке предыдущего и следующего пунктов ошибку в алгоритме...») и в самом конце статьи как раз об этом и говорится :)
      • 0
        Вообще-то в тесте нет одинаковых элементов
        • 0
          «А что же за ошибка была в описании алгоритма? Дело в том, что если в буфер обмена или в остаток попал элемент, который после сортировки должен находиться в одной из первых R позиций, то в итоге он на место никак не попадет...»
          Или Ваш пример не попадает в этот случай?
          • 0
            Теперь всё ясно, я просто подумал, что конец статьи — это то, что после «UPD:». Большое спасибо.
  • 0
    Вам может быть интересно: github.com/BonzaiThePenguin/WikiSort (идея та же самая)

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