И ещё о сортировках

    И ещё о сортировках


    Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.

    Существуют десятки различных способов расположить элементы данных по порядку. Среди них выделяют те, что работают быстро, такие, что, например, могут в максимум за минуты отсортировать любой массив данных, размещенный в оперативной памяти компьютера. Более конкретно можно сказать, что сортировка, работающая быстро, упорядочивает на хорошем современном персональном компьютере миллиард целых чисел за менее, чем сто секунд. Если использовать для сортировки большего числа элементов примитивные, небыстрые методы, например, пузырьковую сортировку или сортировку выбором, то время, затраченное на такую обработку данных может превзойти любые ожидания – такой «процессинг» реально может занять несколько дней, недель и даже лет. Эта большая разница вызвана тем, что время сортировки быстрыми методами занимает величину примерно пропорциональную Nlog N, а примитивными – N2. С ростом N разница между двумя величинами становится очень заметной. Поэтому примитивные методы разумно использовать только для работ с данными небольшого объёма, например, на современных компьютерах до нескольких тысяч элементов. Их также естественно использовать для обучения азам программирования и логического мышления, так как они существенно проще, чем быстрые методы.

    Хотелось бы разобраться в существующих в нынешних стандартных библиотеках методах сортировки. Выяснить как велика разница между ними по основной характеристике, скорости работы, а также их характерные особенности. Кроме того, рассмотрим попутно для сравнения и упражнения для ума некоторые несложные в реализации методы. Стоит ещё, отметить, что оптимизатор компилятора GCC и возможно других хороших компиляторов работает с сортировками очень хорошо, ускоряя код в несколько раз (иногда даже более 5 раз).

    Начнём с метода пузырька (bubble sort) как самого простого и медленного. По этому методу нужно раз за разом проходить по массиву данных, сравнивая соседние элементы и меняя их местами, если порядок между ними нарушен. После каждого прохода, как минимум, один элемент (наибольший или наименьший – зависит от выбранного порядка) оказывается на своём месте. Помимо простоты у этого метода есть ещё одно достоинство, он не требует дополнительной памяти. Можно отметить ещё одну особенность метода пузырька – он очень быстро обрабатывает уже упорядоченные данные и это в отдельных случаях делает его одним из самых быстрых методов. Если данные только частично упорядочены, то этот метод работает с ними быстрее, но в большинстве случаев лишь совсем незначительно. Для тестов я использовал следующую реализацию.

    Ещё один медленный метод – сортировка выбором (selection sort). Здесь на каждом проходе сначала находятся наибольший и наименьший элементы в данных и затем эти элементы ставятся в соответствующие выбранному порядку крайние позиции. На следующем проходе сортируем уже данные без этих крайних элементов. Этот метод так же прост, как и пузырьковая сортировка, и так же не требует дополнительной памяти, но он заметно быстрее. Более того, сортировка по этому методу выполняет рекордно минимальное количество перестановок элементов данных. Поэтому в случае, когда перестановки значительно медленнее сравнений, упорядочение методом выбора может оказаться приемлемой, если число элементов данных невелико. Вот моя реализация. Чаще такую сортировку реализуют, ставя на место только один элемент за проход. Сортировка кучей (или пирамидальная), о которой речь пойдет далее, – это максимально продвинутый вариант рассматриваемой сортировки.

    Код для последнего рассматриваемого медленного метода, сортировки вставками (insertion sort), наверное самый короткий среди всех кодов, реализующих сортировки, поэтому этот метод иногда используют сложные быстрые сортировки для случаев, когда число сортируемых элементов мало (несколько десятков). Он чем-то похож на сортировку пузырьком, так как и тут и там последовательно сравниваются соседние элементы. Но сортировка вставками ищет для очередного элемента правильную позицию в уже отсортированной части данных, а не просто выталкивает экстремальный элемент в крайнюю позицию. При таком подходе также не нужна дополнительная память. Как и пузырьковая сортировка, сортировка вставками очень быстра на упорядоченных данных и быстрее на частично упорядоченных. В последним случае заметно быстрее пузырьковой. Обычно сортировка вставками несколько быстрее сортировки выбором. И в отличие от последней, она, как и сортировка пузырьком, – устойчива. Хуже всего сортировка вставками работает с данными с обратным порядком, с которыми она иногда становится самой медленной из медленных. Для тестов была использована следующая реализация. Её можно немного ускорить, если использовать не линейный, а бинарный поиск, например, функцией std::bsearch. Значительного ускорения можно будет добиться, если использовать структуру типа списка, вставка элемента в которую проходит очень быстро. Можно ещё заметить, что это наиболее естественная сортировка – её, например, обычно интуитивно используют, играя в карты.

    Сортировка Шелла (shell sort) является самой простой среди быстрых методов и вполне пригодной для реализации только начинающими изучать программирование учащимися. Она является лишь некоторым видоизменением пузырьковой сортировки. Разница между ними только в том, что в сортировке Шелла расстояние между сравниваемыми элементами берётся меняющимся от прохода к проходу, от большего на первом проходе, до 1 на последних, таким образом, на этих последних проходах метод Шелла вырождается в примитивную сортировку пузырьком. Дональд Шелл опубликован базовый алгоритм сортировки, получившей его имя, в 1959 году. Таким образом, это одна из первых универсальных сортировок, которые работают быстро. Для сравнения, алгоритм быстрой сортировки был опубликован спустя два года, а популярные ныне сортировка Тима или интроспективная сортировка стали известны только в 90-е. C cортировкой Шелла связаны несколько интересных нерешённых математических проблем, главная из которых – это как оптимально выбирать смещения между сравниваемыми элементами. Удалось найти некоторые рекордные последовательности, например, A102549. Такие последовательности находят путем колоссальных вычислений, поэтому они имеют очень небольшую длину, A102549 – это всего 8 элементов, что хватает только для данных до примерно из 3000 элементов. Для больших данных продолжения нужно искать почти наугад. Использовал значения, близкие степеням числа 2, e, 2.25 и 3. Простые числа, близкие степеням 2 показали наихудшие результаты, заметно уступая лучшим. А вот остальные три варианта оказались примерно одинаковыми с точки зрения влияния на быстродействие и наверное весьма близкими к оптимальным. Причем в этих трёх случаях использование простых чисел не давало осязаемых преимуществ. Любопытно, что смещения предлагаемые в Википедии (с основанием 2.25) на основании ссылок на соответствующие труды, не показали на тестах лучших результатов, хотя и их отличия от лучших были весьма незначительны (не более 5-10%). Использование A102549 в качестве начальной также не дало никаких заметных результатов. Михаил Опанасенко также пытался разгадать сортировку Шелла и получил интересный результат о том, что смещения, выбираемые по формуле sn+1=10sn/3, дают очень хороший эффект и возможно даже, что близкий к идеальному. Мои результаты это подтверждают. В многих случаях именно такие смещения дали наилучший результат, хотя это было и не всегда и отрыв от ближайшего результата был совсем невелик (примерно 5%). Мой код для реализации сортировок Шелла использует маленькие таблицы со смещениями, хотя если не использовать простые числа, то эти смещения для таблиц можно почти мгновенно вычислить, как это и сделано в реализации одного из приведенных вариантов этой сортировки.

    Интересно, что если брать смещения близкие степеням тройки несколько иначе и использовать несколько другой алгоритм (см. реализацию), то на 32-битных числах будем получать скорости, близкие к лучшим, но на более длинных числах и на строках будем получать существенное замедление, иногда более, чем на 100%. Результаты по лучшему алгоритму, использованному oms7, также есть в следующей далее таблице, но он, хотя и показывает хорошие по порядку результаты, по абсолютным значениям заметно отстаёт от лидеров.

    Будет ли когда-нибудь найден способ находить оптимальные смещения? Возможно, но осмелюсь предположить, что ещё не скоро. Сортировка Шелла используется в ядре Linux, а в, как минимум, в одной библиотеке С её код используется для стандартной функции qsort(). Теоретически доказано, что скорость работы оптимальной сортировки Шелла по порядку лишь незначительно медленнее «настоящих» быстрых логарифмических методов. Действительно, зависимость среднего времени обработки данных от их размера для оптимальной сортировки Шелла описывается формулой ∽N(log N/log log N)2, которая даже для весьма больших N весьма близка к типичной для других быстрых методов формуле ∽Nlog N. Обычно сортировка Шелла часто даже быстрее теоретически более быстрых по порядку методов и начинает чуть уступать им лишь, при обработке довольно больших массивов (порядка 10-в миллионов элементов). Этой сортировке совершенно не нужна дополнительная память и она стабильно ведёт себя для самых разных вариантов заполнения данных, выгодно отличаясь этим от быстрых сортировок. Свойством устойчивости метод Шелла не обладает.

    Быстрая сортировка (quick sort) лишь незначительно сложнее алгоритма Шелла и до сих пор является одним из самым быстрым способом упорядочить случайно разбросанные данные. Однако у этой сортировки есть несколько недостатков. Ей требуется дополнительная память и для очень редких случаев она работает крайне медленно, по квадратичной зависимости. Главная идея этого метода в разделении данных на две части: данные в одной части должны быть больше или меньше (зависит от выбранного порядка), чем в другой. Существует несколько способов такого разделения. В идеале при каждом делении обе части должны получаться примерно одинаковыми по размеру, а хуже всего получается тогда, когда при делении одна из частей получается состоящей только из одного элемента. Рассмотрим несколько реализаций алгоритмов быстрой сортировки, в частности, метод Хоара, в котором опорный, делящий данные на две части элемент выбирается из середины сортируемых данных.

    Рассмотрим также чрезвычайно компактный алгоритм Ломуто, который иногда чуть (примерно на 1%) быстрее рассмотренного метода Хоара. Однако, на типовых частных случаях, например, на упорядоченных, обратных или маловариантных данных метод Ломуто показывает чрезвычайную медленность. Кроме того, среди рассмотренных вариантов быстрой сортировка эта оказалась при практических прогонах самой жадной к размеру стека: при сортировке относительно небольших массивов только этой сортировке не хватило 8 мегабайт для стека, пришлось ставить через ulimit этот размер побольше. Такая жадность к стеку приводит при обработке больших данных (десятки миллионов строк) и к существенному замедлению работы, природу которого назвать затруднюсь. Могу лишь констатировать, что с такими данными эту и сортировку из следующего абзаца лучше не использовать.

    Метод Ломуто в качестве опорного выбирает последний элемент, но возможно реализовать быструю сортировку вообще без опорного элемента, точнее выбор такого элемента здесь происходит как результат уже произведенной бисекции данных. Такая сортировка по скоростным характеристикам оказалась близкой к методу Ломуто, хотя обычно чуть быстрее, а в экстремальных случаях – заметно быстрее Ломуто, но медленнее Хоара.

    В 2009 был опубликован алгоритм быстрой сортировки с двумя опорными точками, который стал стандартным для языка Java. Этот алгоритм на 20% уменьшает число перестановок по сравнению с лучшими типовыми, но число сравнений не меняется. Его автор – Владимир Ярославский. Действительно работает, как правило, быстрее других быстрых сортировок. Я немного его оптимизировал, использовав давно известный факт, что на архитектуре x86, swap работает обычно быстрее, чем присваивание, а для строк С++ – намного-намного быстрее. Все рассмотренные до сих пор быстрые сортировки не обладают свойством устойчивости.

    Дополнительная память для быстрых сортировок нужна для организации рекурсивных вызовов. Однако, второй такой вызов можно заменить на цикл, проведя оптимизацию хвостовой рекурсии, которая по скорости может не дать никаких выигрышей, но существенно снижает размер используемых дополнительных данных. Я реализовал вариант сортировки Хоара с такой оптимизацией. Кроме того, в системных программах можно проверять указатель стека и если он приблизился к критическому значению, то можно просто сбросить все рекурсивные вызовы и начать сортировку заново – для этого случая очевидно, что нужно использовать вариант быстрой сортировки, не замедляющейся на почти упорядоченных данных, например, предложенный выше вариант Хоара. Борьба с использованием дополнительной памяти может считаться главной идеей быстрой сортировки из стандартной библиотеки языка С в GCC. В ней вообще отказались от рекурсии. Вместо неё используют её симуляцию, что позволяет на треть сократить нагрузку на стек. Код получился немаленький, около 150 строк. Об этой сортировке ещё будет небольшой материал ниже.

    Сортировка хешем (hash sort) может быть очень быстрой, близкой к ∽N. Однако, иногда она может работать и по квадратичной зависимости. Скорость работы этого метода сортировки очень зависит от входных данных. Если данные равномерно распределяются хеш-функцией по вспомогательному массиву, то получаем максимально быструю линейную зависимость. А если все данные сгруппированы возле нескольких далеко отстоящих друг «центров масс» или когда много одинаковых элементов данных, т. е. когда случается много хеш-коллизий, то получаем худшую зависимость типа ∽N2. Как и для сортировки деревом, для сортировки хешем нужно довольно много дополнительных данных, в приводимом листинге кода нужно, например, 12 дополнительных байт на каждое сортируемое целое число (int32, x86-64). Интересным свойством сортировки хешем является отсутствие операций сравнения между элементами данных, что отличает эту сортировку от всех рассмотренных выше. Точнее эти операции нужны только для случая коллизий. При сортировке данных, где ключ совпадает со всем элементом данных, можно использовать дополнительный счетчик числа одинаковых элементов, но это скорее сомнительная оптимизация. Можно ещё использовать бинарное дерево вместо списка для хранения данных хеш-коллизий, это значительно ускоряет работу для отдельных частных случаев, когда много коллизий, но в целом работа при использовании бинарного дерева во многих случаях замедляется и это при том, что в таком случае на элемент данных приходится хранить почти 100 байт дополнительной информации. Я реализовал три варианта хеш-сортировки с использованием бинарного дерева: один использует неупорядоченное дерево, а два других – стандартные деревья из библиотек std и boost. Хеш-сортировка практически непригодна для сортировки текстовых строк, за исключением совсем коротких, так как для таких данных невозможно сделать хорошую хеш-функцию. Стандартный хеш С++ (unordered_multiset) для сортировки у меня приспособить не получилось: пробовал использовать монотонные хеш-функции и упорядочивающие отношения вместо равенства – это не сработало.

    Сортировка массивом (array sort) очень похожа на предыдущую. Также используется вспомогательный массив, куда хеш-функцией заносятся значения. При коллизии нужно сдвинуть непрерывный фрагмент занятых элементов на позицию влево или вправо, освобождая указываемую хеш-функцией позицию для нового элемента. Для получения хорошей скорости нужно, чтобы вспомогательный массив был в несколько раз (от 2-3) больше исходного. С ростом размера вспомогательного массива скорость работы увеличивается только до некоторого предела, зависящего от сортируемых данных и связанной с ними хеш-функции, а затем (типично с 4-5) падает. Скорость работы – примерно такая же как и у хеша, но на хороших данных чуть быстрее, а на плохих – заметно медленнее. Этой сортировке также надо довольно много дополнительной памяти. Если ограничить количество элементов в сортируемом массиве числом, чуть большим четырех миллиардов, то утроенный вспомогательный массив потребует столько же дополнительных данных, что и сортировка хешем, а усемеренный – 28 байт, что заметно меньше, чем для сортировки деревом, или намного меньше, чем хешем с деревьями. Эта сортировка также почти непригодна для работы со строками. В Википедии статьи про такой алгоритм нет, а вот моя реализация.

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

    Одна из самых быстрых сортировок, которая вообще никогда не используют сравнений, – это известная ещё с XIX века поразрядная сортировка (radix sort). Её идея очень проста – нужно работать с группами разрядов представления данных (для тестов брал группы из 8, 11 и 16 разрядов). По каждой группе строятся таблицы, а результаты потом сравнительно простым способом объединяют. Существует два основных способа использовать поразрядную сортировку. Для сортировки чисел разряды удобнее брать справа налево (это вариант LSD – Least Significant Digit), а для сортировки строк слева направо (это вариант MSD – Most Significant Digit). Поразрядная сортировка часто бывает значительно быстрее любых других методов упорядочения данных. Удивительно, что поддержка поразрядной сортировки до сих пор не слишком значительна: её нет ни в boost, ни в стандартной библиотеке С++, мне неизвестен даже её вариант для какой-нибудь известной библиотеки для работы с числами или строками С++. У этой сортировки есть, конечно, и недостатки. Она очень чувствительна к типу данных для сортировки, например, нужно иметь свой вариант такой сортировки для данных каждого размера, нужно делать специальный варианты для беззнаковых и знаковых целых чисел, а поддержка работы с вещественными числами может потребовать совсем немаленьких усилий. Её вариант при использовании порядка от младшего байта к старшему обычно требует дополнительной памяти, чуть большей, чем для исходных данных (это существенно меньше, чем для сортировки хешем или массивом и тем более деревом). Кроме того, этот вариант малопригоден для сортировки длинных строк. Мой код для этой сортировки здесь, он основан на коде из упоминавшейся статьи oms7. Вариант с обратным порядком обработки байт более универсален и очень хорошо подходит для сортировки строк. Этот вариант можно реализовать без использования дополнительной памяти (цена этому – потеря свойства устойчивости), как это сделано в функции radixsort() библиотеки bsd. Мой код для этого варианта также основан на коде oms7, он ценой использования дополнительной памяти, несколько большей размера исходных данных, имеет свойство устойчивости, но неоптимизирован для строк и поэтому показывает значительно худшие характеристики производительности, чем аналогичная по назначению функция sradixsort() из уже упомянутой библиотеки bsd. Эта сортировка может показать удивительно плохие результаты при работе с маленькими числовыми массивами, работая на несколько порядков медленнее, чем даже пузырьковая, хотя речь идет об очень маленьких величинах не более нескольких миллисекунд и эту разницу непросто заметить. Так получается из-за того, что она использует вспомогательные массивы небольшого размера, но при сортировке данных маленького размера эти небольшие размеры могут оказаться больше самих сортируемых данных. Для избежания замедления вариант «слева направо» использует сортировку вставками вместо основной в таких случаях. В заключении, стоит отметить, что это единственная известная мне относительно популярная сортировка, всегда достоверно работающая со скоростью ∽N, но коэффициент пропорциональности здесь зависит от размеров элементов данных и для строк или длинных чисел он может быть весьма ощутим.

    Вариантом поразрядной сортировки MSD является сортировка лучом, структурой данных, которая позволяет эффективно размещать ключи ассоциативного массива. Моя реализация, несмотря на оптимизацию использования памяти, всё равно оказалась к ней весьма жадной. По скорости лучшие результаты получились при сортировке длинных строк.

    Далее рассмотрим некоторые сортировки, которые можно встретить в стандартных библиотеках.

    Начнём с быстрой из стандартной библиотеки C (qsort, вариант GCC), о ней уже писал. Могу здесь только добавить, что это сортировка как и другие С-сортировки (например, следующие далее из библиотеки BSD) непригодны для работы с объектными данными, в частности, строками С++, что вызвано тем, что такие данные не являются POD. Имея исходники, проблему легко решить, заменяя операции типа memcpy на обычные присваивания. Можно ещё заметить, что в некоторых стандартных библиотеках С, эта сортировка может быть не обязательно именно быстрой, её могут заменять на другие. В текущей версии для GCC эта сортировка даже обладает свойством устойчивости. С упомянутыми си-сортировками при сборе данных иногда возникали сюрпризы, они могли, например, работая с типом std::vector через функциональный объект, создавать сложности – могу порекомендовать использовать её с объектными данными с осторожностью. По данным прогонов эта сортировка иногда относительно медленная: она заметно уступает по скорости другим реализациям быстрой сортировки при работе с числами, но при работе с си-строками она лучшая, лишь сортировке с двумя опорными точками иногда получается её обогнать, но на длинных строках стандартая qsort обгоняет её почти всегда. Самое интересное открылось при попытке отсортировать с её помощью миллиард целых чисел – оказалось, что заполнение типа 7 приводит к временной зависимости, близкой к квадратичному закону, т. е. к возможному «процессингу» длительностью до нескольких лет (не стал ждать окончания и остановил это на 21 часу прогона). На меньших данных эта сортировка умеет обычно подбирать опорные точки, с которыми работает быстро.

    Интроспективная сортировка используется в стандартной библиотеке C++, хотя какой в точности метод, используется в std::sort зависит от реализации, привёл сведения только по GCC. По данным прогонов, это вторая по скорости после spread-сортировки при работе с числами, причем преимущество spread-сортировки небольшое (от почти 0 до 30%), а вот с сортировкой строк всё значительно хуже – она может уступать лидерам в 3-4 раза. Это фактически быстрая сортировка, в которой учитываются два частных случая: 1) если число рекурсий стало слишком большим, то происходит переключение на сортировку кучей; 2) если число элементов для сортировки мало, то происходит переключение на сортировку вставками.

    Устойчивая сортировка из стандартной библиотеки С++ (std::stable_sort), как следует из названия, имеет свойство устойчивости – она сохраняет относительный порядок между элементами с одинаковым ключом. Это свойство сравнительно редко является необходимым, хотя пишу об этом скорее голословно, только на основании собственного опыта. Может использовать дополнительную память, что делает её быстрее. Удивительно, но эта сортировка нередко оказывается быстрее std::sort.

    В сверхпопулярном языке питон в качестве стандартной используется сортировка Тима. Для тестов использовал её вариант из github-репозитория. Она показывает рекордно хорошие результаты на частично-упорядоченных данных, но в среднем всё же заметно медленнее лидеров. Обычно её скорость – это среднее между быстрыми сортировками и сортировками Шелла, хотя на строках она иногда бывает близка к лидерам. Обладает свойством устойчивости. Она реализует относительно непростой алгоритм, в стандартной реализации которого в 2015 была обнаружена ошибка, которая, впрочем, требует скорее нереальной ситуации для своего проявления.

    В С-библиотеке BSD есть поразрядная сортировка (radixsort) и её устойчивый вариант (sradixsort). К сожалению, обе эти сортировки можно использовать только для С-строк. Как будет видно из данных по тестам – это сегодня наибыстрейший способ отсортировать строки и поэтому удивительно, что нет её стандартного варианта для строк С++.

    В С-библиотеке BSD есть ещё сортировка слиянием (mergesort). Эта сортировка известна как одна из самых быстрых для данных с последовательным доступом (файлы, списки) и возможно используется в стандартной библиотеке С++ для сортировки списков (std::list и std::forward_list). Кстати, она известна ещё с 1948 и одним из её разработчиков был весьма небезызвестный математик и специалист по первым компьютерным системам фон Нейман. Из быстрых методов эта сортировка не выделяется лучшими характеристиками, хотя, как правило, она несколько быстрее методов Шелла. Она требует дополнительной памяти и обычно реализуется устойчивой.

    Кроме того там ещё есть сортировка кучей (heapsort). Куча обычно используется для оптимальной организации очереди с приоритетами, но может использоваться и для сортировки. Сортировки кучей не требуют дополнительной памяти, но свойством устойчивости не обладают. По скорости для чисел она значительно (до 3-6 раз) медленнее, чем методы Шелла, но для не очень коротких строк строк она показывает совсем неплохие результаты, обгоняя (с ростом длины строки преимущество растет) методы Шелла.

    Сортировка кучей есть и в стандартной библиотеке C++. Такая сортировка делается за две операции: построение кучи (std::make_heap) и затем собственно сортировка (std::sort_heap). Здесь в отличие от библиотеки bsd сортировка – это именно одна из операций для кучи. Обычно этот вариант сортировки несколько быстрее предыдущего (вариант bsd показывает лучшие результаты только на коротких числах и длинных си-строках).

    Используя стандартную библиотеку С++, можно сортировать и бинарным сбалансированным деревом (std::multiset) – просто заполняем дерево, а затем обходим. Можно считать этот метод нерекурсивной быстрой сортировкой. Некоторая проблема возникает в том, что стандартый распределитель памяти отличается заметной неспешностью, поэтому для лучших результатов надо использовать свой распределитель, что ускоряет примерно на 10-30%. Можно ещё отметить, что такой метод требует очень много дополнительной памяти, с g++ на каждый элемент данных, помимо него самого нужно ещё хранить 32 байтa (на архитектуре x86-64) – интересно было бы попробовать хранить такое дерево как кучу, т.  без дополнительных байт. Если использовать boost::container::multiset, памяти нужно поменьше: только дополнительных 24 байта на элемент данных. Однако как boost, так и стандартная библиотека продемонстрировали один неприятный сюрприз – в процессе работы они иногда требовали больше памяти, чем было необходимо. Возможно это из-за балансировки бинарных деревьев. Коды – здесь.

    В библиотеке boost есть spreadsort, алгоритм которой был изобретён уже в 21 веке. Это наиболее быстрый в целом на сегодня метод из присутствующих в известных библиотеках. Эта сортировка использует некоторые идеи поразрядной и подобно ей может быть довольно капризной к типу аргументов. Обычно это сортировка показывает рекордные результаты, иногда существенно лучшие тех, что у ближайших конкурентов. Единственное исключение – это сортировка С-строк, где она существенно уступает поразрядным методам из библиотеки bsd. При сортировке длинных С-строк она может уступать и другим методам, например, spin-сортировке или быстрой сортировке с двумя опорными точками. У spread-сортировки (boost v1.62) обнаружилась очень неприятная проблема — при сортировке небольших (до 1000 элементов) массивов С-строк она работает с ошибками.

    Там есть ещё новый алгоритм pdqsort, улучшающий, как заявлено автором, интроспективную сортировку. Этот новый алгоритм, который пока ещё не описан в Википедии. Его результаты – хотя и неплохие, но не особо впечатляющие. Он медленнее std::sort на коротких целых, но быстрее на строках и длинных целых. В обоих случаях разница скорее незначительная. Лучшие результаты у этой сортировки получились для длинных С++-строк – здесь она уступает, хотя и заметно, только лидеру, spread-сортировке.

    В boost можно ещё найти spinsort. Это также новый алгоритм, обладающий в отличие от предыдущего свойством устойчивости и который также ещё не описан в Википедии. Обычно он близок к лидеру, но с заметным отставанием от него. Требует, хотя и не слишком много, дополнительной памяти.

    Закончим на flat_stable_sort из всё той же библиотеки boost. Это ещё один новый устойчивый алгоритм, который пока не описан в Википедии. Это безусловно быстрый метод, но несколько уступающий большинству других быстрых библиотечных методов. Он использует очень мало дополнительной памяти (ему, однако, всегда нужна таблица фиксированного размера 8 КБ) и часто заметно быстрее метода Шелла.

    Рассмотрим таблицу времени (в мс) работы этих алгоритмов на компьютере с 8 ГБ оперативной памяти с процессором AMD Phenom™ II X4 955 @3.214 МГц. Компьютер работал в общей сложности несколько месяцев, а суммарный размер собранных данных в двух json-файлах, которые загружаются с таблицами, составляет почти 400 КБ. Тайминги приводятся по среднему от числа прогонов, для меньшего размера данных прогонов было больше. Работа с кэшем довольно сложным образом меняет скорость вычислений, поэтому полученные результаты в лучшем случае только приблизительны (могу предполагать, что неточности таймингов могут доходить до 20%). Полагаю, что на лучших современных процессорах для ПК результат может быть получен в 2-3 раза быстрее, но при этом нужно иметь в виду, что многие более современные процессоры работают, переключаясь между разными частотами и результат, полученный с ними, будет ещё более приблизительным.

    Эта и следующая таблица – интерактивны. Помимо абсолютных значений таймингов можно посмотреть также их значения относительно среднего, медианы, минимума и максимума. Можно менять точность в знаках. Можно также получить отношения таймингов по разным видам заполнений и типам данных. Последнее, например, может показать, что сортировка С-строк заметно быстрее строк С++. Из методов сортировки также можно выбирать и собирать разнообразные подмножества. Можно, конечно, и устанавливать сортировку по любому столбцу. К сожалению, я не знаю как в статье на хабре использовать Javascript, поэтому таблицы доступны только по ссылкам. Для случая, если github.io окажется перегруженным, даю ещё резервные ссылки на первую и вторую таблицы.

    Время измеряется в миллисекундах, но в законе временной зависимости, чтобы избежать слишком маленьких коэффициентов приводятся формулы для микросекунд. Таким образом, если подставляем в формулу значение для N, то результат надо ещё разделить на 1000, чтобы получить число, близкое к соответствующему из таблицы. Закон временной зависимости выводится на основании полученных таймингов, из сопоставления двух результатов (обычно берутся крайние). Проверить качество выведенного закона можно, используя опцию относительного отклонения (deviation) фактической величины от выводимой.

    Некоторые общие выводы по результатам этой таблицы:

    • лучшие shell-сортировки на данных размером до 10 миллионов элементов могут обгонять timsort и даже некоторые быстрые сортировки;
    • timsort очень близка по скорости qsort (clib), иногда несколько обгоняя, а иногда наоборот отставая;
    • heapsort и особенно treesort часто заметно тормозят, но на фоне пузырька или даже выбора видно, что это всё-таки быстрые методы. Интересно, что оба этих метода нередко имеют весьма близкие характеристики – они оба строят деревья. Легко заметить, что у heapsort и treesort зависимости хотя и явно не квадратичные, но очевидно и не Nlog N, а существенно хуже – сравните с сортировкой Шелла, которая с ростом объёма данных ведёт себя гораздо лучше, чем heapsort или treesort, при том, что она сама медленнее, чем Nlog N. Таким образом, практические реализации сортировок кучей и деревом не соответствуют их теоретическим спецификациям;
    • данные по сортировкам строк показывают, что законы временных зависимостей здесь не такие как для чисел – на эти законы здесь как-то накладываются длины строк, которые сортируются. Мне, к моему сожалению, неизвестны формулы для известных сортировок, которые бы давали точные законы временных зависимостей при работе со строками;
    • интересно, что скорость работы с вещественными числами примерно такая же как и целыми – это следствие того, что в современной архитектуре x86 сделаны очень эффективные оптимизации для работы со стеком;
    • hash_sort показала совершено посредственные результаты, это возможно из-за того, что из-за использования дополнительной памяти резко падает эффективность работы кэшей процессора. На небольших случайных данных (менее ста тысяч элементов) сортировка хешем обгоняет лучшие быстрые (quick) сортировки. Можно ещё заметить, что возможно опять из-за кешей, некоторые результаты у этой сортировки очень странные, например, 105, 106 и 107 32-разрядных целых при использовании частично упорядоченного (partially ordered) заполнения сортируются за примерно одно и то же время! Какие-то почти квантовые эффекты. :) Уверен, что если поискать, то можно найти и другие труднообъяснимые результаты.

    Добавлю ещё некоторые выводы по некоторым частным случаям:

    • некоторые типы заполнения данных обнаруживают слабые места быстрых сортировок. Однако выбор опорного элемента сложным образом делает вероятность попадания на плохую для сортировки последовательность практически нулевой. Можно также выбирать опорный элемент на каждом проходе по разному или случайно. Возможно так и делают в qsort (clib). Рассматриваемый метод Хоара работает очень медленно только на специально сконструированных последовательностях, встретить которые случайно при практической работе – это случай с вероятностью 2N-3/NN, то есть почти абсолютно невозможное событие. Хотя если рассматривать последовательности, на которых метод Хоара работает не максимально медленно, а только с существенным замедлением, то таких случаев гораздо больше, что, однако, оставляет вероятность случая недопустимо медленной обработки данных по-прежнему практически ничтожной, хотя и весьма раздражающей своим отличием от нуля. Также почти невозможно случайно получить данные, на которых быстрая сортировка с двумя опорными точками, будет работать медленно, по квадратичному закону. Варианты быстрых сортировок Ломуто и без опорного элемента показывают очень плохие результаты почти на всех частных случаях заполнений;
    • на некоторых частных случаях, самая медленная «пузырьковая» сортировка даёт отличные результаты, а одни из самых быстрых, quick-сортировки, наоборот очень плохие;
    • сортировка хешем показала очень плохой результат на заполнениях типа 8 и 9, это объясняется тем, что монотонная последовательность берётся из последовательных величин, начиная с меньшего, а 1% случайных чисел берётся из диапазона от меньшего до максимального значения, что скучивает все последовательные 99% данных в один элемент хеша. Этот случай очень хорошо демонстрирует проблемы, которые могут возникнуть при использовании этой сортировки или сортировки массивом с неизвестными данными;
    • сортировка выбором ведёт себя очень стабильно на всех типах заполнения, heap- и tree-сортировки также довольно стабильны, без явных пиков и провалов. Это верно, конечно, и для сортировок Шелла, а также большинства других быстрых методов из стандартных библиотек.

    Теперь пора рассказать об типах данных, использованных с сортировочными алгоритмами:

    1. целые числа, 32-битные знаковые (int32_t), но использовались только неотрицательные. Другие числовые данные также брались только неотрицательные – это не снижает общности полученных результатов, но делает их получение для некоторых алгоритмов существенно проще;
    2. целые числа, 64-битные знаковые (int64_t);
    3. целые числа, 128-битные знаковые (__int128 – поддерживаются, как минимум, GCC);
    4. структуры из пяти целых чисел (int32_t), одно из которых используется как ключ (INT1P4). При сортировке таких данных более существенно на время вычислений начинает влиять количество перестановок, поэтому методы с меньшим числом перестановок получают некоторое преимущество;
    5. вещественные числа типа двойной точности, double (float numbers);
    6. короткие строки C++ и С. Брались строки длиной от 1 до 16 (strings short и c-strings short);
    7. строки С и С++ средней длины, длина которых от 1 до 256 (strings и c-strings);
    8. длинные строки С и С++, длина которых от 1 до 220 (это чуть больше миллиона), причем строки подбираются так, что их средняя длина не превосходит 512, – так подбирались строки только для случайного заполнения, для остальных случаев просто брались строки длиной от 1 до 512 (strings long и c-strings long).

    А также о способах заполнения исходного массива для сортировки:

    1. случайно;
    2. строго по возрастанию (упорядоченные, ordered);
    3. строго по убыванию (обратного порядка, reversed);
    4. случайные величины из диапазона от 0 до 99 (малого разброса, low variation 100);
    5. случайная последовательность из 0 и 1 (малого разброса, low variation 2);
    6. константой 0 (малого разброса, low variation 1);
    7. последовательность, приводящая приведённый вариант qsort (Hoare) к самому медленному исполнению. Любопытно, что таких последовательностей ровно 2N-3 среди всех последовательностей длины N;
    8. строго по возрастанию, с вставкой 1% случайных чисел (partially ordered);
    9. строго по убыванию, с вставкой 1% случайных величин (partially reversed).

    Следует подчеркнуть, что случайные данные (random) – это самый типичный случай заполнения массива, все остальные способы – это крайне редкие и даже почти невозможные при нормальной работе частности.

    Рассмотрим ещё результаты тестов, где сортировки работают со всеми возможными последовательностями данных. Число таких последовательностей равно факториалу от их длины, таким образом, для последовательностей длины 12 существует 479'001'600 вариантов – такое их количество хороший современный ПК обсчитает за менее, чем минуту. Если мы возьмём последовательности длины 14, то получим уже 87'178'291'200 вариантов на несколько часов работы компьютера. Поэтому в следующей таблице – среднее время (в тактах процессора, получаемых через инструкцию RDTSC) одной сортировки при сортировке всех перестановок длиной только до 12. В качестве данных берутся прежние числовые типы и короткие строки. Конечно, можно было заметить, что последовательности с повторяющимися элементами не рассматриваются. Однако, осмелюсь предположить, что их наличие качественно не изменило бы результатов, но могло существенно замедлить их получение.

    Результаты по таким маленьким данным не слишком репрезентативны и особенно по сложным методам сортировки, но представление о поведении сортировок они всё-таки дополняют. Некоторые сортировки, насколько мне известно, заменяют свой основной алгоритм на другой при работе с маленькими массивами – это сортировки spread, быстрая с двумя опорными точками и radix_msd (две последних используют вставки). А некоторые сортировки (flat_stable и radix) используют маленькие таблицы, но при крошечных размерах данных эти таблицы оказываются гораздо большими самих данных, что сильно тормозит эти методы на фоне других и производит странные результаты. Странные результаты также получаются и у других поразрядных сортировок и у сортировок хешем и массивом. Такие необычные результаты легко объясняются тем, что время подготовки данных перед сортировкой у этих методов для маленьких данных больше времени самой сортировки. Конечно, при измерении таких маленьких временных интервалов (наносекунды) влияние разнообразных погрешностей на выводимый закон гораздо выше, чем в предыдущей таблице. Поэтому законы получились очень приблизительные, часто «с заносом» к преувеличенным значениям. Последнее частично объясняется тем, что при работе с маленькими данными время собственно сортировки становится сравнимым с временем вызова функции сортировки и нескольких необходимых вспомогательных операций по замеру времени. Программа старается вычесть названные накладные расходы из выводимого результата, но это получается делать скорее очень приблизительно. При всём этом осмелюсь ещё предположить, что, сравнивая результаты для разных типов данных и принимая в расчет сделанные замечания, можно делать иногда предположения, не очень далёкие от точных.

    В заключении ещё одна таблица, которая показывает насколько много требуется разным тестируемым методам сортировки дополнительной памяти. Очевидно, эта величина зависит от системы. В моих тестах, как уже писал, это x86-64, GCC. Буква Т в ней означает размер типа в байтах (в этот размер длина строки не входит: для си-строк – это размер указателя, для строк си++ – это размер дескриптора, 32 байта для x86-64 GCC), буква L – средняя длина типа в байтах (для чисел это равно Т, а для строк это средняя длина строки), буква А может иметь значение 1 или 0 – это выравнивание до 64-битной границы, а буква M – это выравнивание от стандартного распределителя памяти (оно предположительно выравнивает на 32-байтную границу). Значок * означает, что данные по этому типу сортировки были получены только на основании анализа чтения поля VmRSS из /proc/PID/status (упомянутое поле – это размер программы-процесса).

    Таблица дополнительной памяти
    Метод Зависимость
    array*1 (T + 1/8)N
    array*k, k>1 (T + 4k)N
    bubble 0
    clib_qsort от ≈TN/2 до ≈TN*
    flat_stable ≈TN/256
    hash (T + 8 + 4A)N
    hashbt (T + 12)N
    hashbt_boost (56 + T + 4A + M)N
    hashbt_std (80 + T + 4A + M)N
    heapsort 0
    insertion 0
    mergesort_bsd от ≈Tlog2N до TN*
    pdq TlogN
    quicksort от ≈16log2N до 16N
    quicksort_tco от 0 до N
    radix ≈TN
    radix8_trie от ≈TN + 24L до ≈(T + 24L + 12)N
    radix_bsd 0
    radix_msd ≈TN
    selection 0
    shell 0
    spin TN/2
    spread ≈0
    sradix_bsd ≈TN*
    stlsort от 0 до до ≈Tlog2N*
    stlstable от 0 до ≈TN/2*
    timsort от 0 до ≈TN*
    tree_boost (T + 24)N
    tree_stl (T + 32)N


    Существуют, конечно, и другие методы сортировки как примитивные, так и быстрые. В библиотеке boost есть параллельные алгоритмы, позволяющие получать преимущества от наличия дополнительных процессорных ядер в системе. Можно ещё вместо std::multiset использовать самоупорядочивающийся контейнер boost::container::flat_multiset, но это работает очень медленно.

    Пользуюсь случаем, чтобы сказать несколько замечаний о библиотеке boost вообще. Рекомендую не проходить мимо. Даже те возможности, которые есть в стандартной библиотеке, в boost, как правило, реализованы лучше, а иногда (как, например, регулярные выражения) значительно лучше. Если говорить о контейнерах, то в boost их заметно больше, а те, что совпадают со стандартными, иногда несколько быстрее и имеют часто небольшие, но приятные улучшения. Boost более тщательно проверяет соответствие типов, что иногда может помочь с обнаружением почти неуловимых ошибок, которые обычно себя не проявляют, но в некоторых обстоятельствах способны неожиданно активироваться. К недостаткам boost относиться безусловно совершенно нечитаемые и огромные по объёму сообщения об ошибках компиляции на многих конструкциях из этой библиотеки – это, хотя и в меньшей степени, относится и к стандартной библиотеке. Разработчикам С++ пора с этим уже что-то делать.

    Все файлы с тестами и некоторые другие смежные материалы можно взять из моего репозитория. Если кому-то интересны сырые исходные данные, то их можно взять тут (1.4 МБ). Буду рад любым комментариям, критике и добавлениям.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 53

      +2
      Спасибо, сам коллекционирую сортировки и не перестаю удивляться, что всё время узнаю о существовании новых алгоритмов. К тем примерно ста более-менее разным сортировкам, о которых мне известно после прочтения статьи добавились spinsort, pdqsort, flat stable sort… Иногда очень удивляюсь насколько изобретательны программисты, которые придумывают всё новые и новые способы упорядочивания. Какая-то удивительно неисчерпаемая тема.

      На досуге внимательно ознакомлюсь с материалом и утащу в свою сокровищницу несколько новых драгоценных камней.
        +1
        Благодарю вас, но неужели знали про новейшую быструю сортировку с двумя опорными точками?
          0
          Это я просто внаскидку перечислил с экстравагантными названиями, там многоточие стоит, означающее, что ряд не завершён. Кроме того, времени на обстоятельное ознакомление со статьёй сейчас нет, пока что прошёлся по тексту по диагонали.
          +3
          К тем примерно ста более-менее разным сортировкам, о которых мне известно
          Внушительная цифра. Не хотите опубликовать в виде статьи список своей коллекции? Хотя бы всего несколько строк на каждую сортировку:
          — Номер (от 1 до 100)
          — Название
          — Краткая характеристика (простая, быстрая, похожа на предыдущую и т.д.)
          — Ссылка на источник.
          Думаю, что такой справочный список будет очень полезен. (Посмотрел, что у Вас много публикаций по сортировкам, но меньше 100 :), но и такому количеству Ваших публикаций индекс для поиска по ним будет полезен).

          И спасибо автору!
            +2
            Я потихоньку составляю своеобразный справочник всех сортировок в виде excel-приложения с макросами. Там и краткая справка по каждой сортировке и примерно для половины алгоритмов реализована пошаговая визуализация на vba. Приложение доступно, если интересно, то в моих статьях без особого труда найдёте ссылку на него.

            Текущий список выглядит так (картинка кликабельна):
        0
        -
          0
          del
            +1
            А где сортировка воронкой от разработчика rybvv? Жаль ту тему удалили, такие жаркие комменты были.
              +4
              В одном своём проекте на Pascal под Win64, нужен был максимально быстрый способ сортировать массив из миллионов INT рандомизированных значений.
              Попробовав разные алгоритмы, написал разновидность комбинированного Q-sort и Insert-sort на Assembler. Эмпирическим путём выяснил, на малых размерах массива 16-24 элементов, Сортировка вставками показывает феноменальное быстродействие и не требует дополнительной памяти, достаточно регистров.
              Для уменьшения выделения памяти на быструю сортировку правая часть разделения по опорному элементу рассчитывалась итеративно, тем самым меньше нагружая стек, что критично на огромных массивах.
              Работало много быстрее библиотечных функций.
              Провожу код:
              procedure qSort_insSort(var m : Array of LongWord; l,r : LongWord);
              procedure ASM_QSort assembler;
              ASM
              @@START_SORT:
              MOV R10,RDX
              SUB R10,20 // Если отрезок меньше 20 элементов сортируем вставками (так быстрее)
              CMP R10,RCX
              JA @@ASM_QSort // Иначе сортируем быстрой сортировкой со срединным опорным элементом
              // Сортировка вставками --------------------------------------------------------
              MOV R8,RCX // i:=0;
              @@I_BEGIN:
              ADD R8,4 // i:=i+1;
              CMP R8,RDX // while (i<=r) do
              JA @@END // i>r
              MOV R9,R8 // j:=i;
              @@J_BEGIN:
              CMP R9,0 // j<=0
              JNA @@I_BEGIN // Оканчиваем итерацию j
              MOV R10,R9 // (j)
              SUB R9,4 // (j-1)
              MOV EAX,DWord[R9] // m[j-1]
              MOV EBX,DWord[R10] // m[j]
              CMP EAX,EBX // m[j-1]<=m[j]
              JNA @@I_BEGIN // Оканчиваем итерацию j
              MOV DWord[R9],EBX
              MOV DWord[R10],EAX
              JMP @@J_BEGIN
              // Qsort с рекурсией -----------------------------------------------------------
              @@ASM_QSort:
              MOV R8,RCX
              ADD R8,RDX
              SHR R8,3
              SHL R8,2
              MOV R10D,DWord[R8] // находим срединный элемент

              MOV R8,RCX // i:= P1; j:= P2;
              MOV R9,RDX

              @@i_START: // while (o < m[j]) do dec(j);
              MOV EAX,DWord[R8]
              CMP EAX,R10D
              JNL @@j_START // если больше или равно
              ADD R8,4
              JMP @@i_START

              @@j_START: // while (PLongWord(j)^ > o) do dec(j,4);
              MOV EBX,DWord[R9]
              CMP EBX,R10D
              JNG @@j_STOP // если меньше или равно
              SUB R9,4
              JMP @@j_START
              @@j_STOP:

              CMP R8,R9 // if (i <= j) then
              JG @@NO_XCHG // если меньше или равно
              MOV EAX,DWord[R8] // temp:=m[i]; m[i]:=m[j]; m[j]:=temp;
              MOV EBX,DWord[R9]
              MOV DWord[R8],EBX
              MOV DWord[R9],EAX
              ADD R8,4 // inc(i); dec(j);
              SUB R9,4
              @@NO_XCHG:

              CMP R8,R9 // until (i > j);
              JNG @@i_START // если меньше или равно

              CMP RCX,R9 // if (P1 < j) then
              JNB @@SORT1 // Jump, если больше или равно
              PUSH R8 // i
              PUSH RDX // p2
              // Первый аргумент (p1) уже в регистре RCX
              MOV RDX,R9 // Устанавливаем второй аргумент (j)
              CALL ASM_QSort // вызываем Сортировку первого отрезка (рекурсивно)

              POP RDX // p2
              POP R8 // i
              @@SORT1:

              CMP R8,RDX // if (i < P2) then
              JNB @@END // Jump, если больше или равно
              MOV RCX,R8 // Устанавливаем первый аргумент (i)
              // Второй аргумент (p2) уже в регистре RDX
              JMP @@START_SORT // вызываем Сортировку второго отрезка (Без рекурсии)
              @@END:
              END;

              // Вызов процедуры сортировки
              begin
              ASM
              CMP R8,R9 // Если L>=R
              JNB @@NO_RUN
              CMP RDX,R9 // Если LENGTH(M)>=R
              JA @@NO_RUN
              CMP R8,0 // Если L<0
              JB @@NO_RUN
              CMP RDX,0 // Если LENGTH(M)=0
              JE @@NO_RUN
              LEA RDX,[RCX+R9*4]
              LEA RCX,[RCX+R8*4]
              CALL ASM_QSort
              XOR RAX,RAX
              JMP @@END
              @@NO_RUN:
              MOV RAX,1
              @@END:
              END;
              end;

                +7

                Какой у вас интересный и выразительный Паскаль получился...

                  +1
                  Сам проект на паскале, но одна высоконагруженная функция на ассемблере это же мелочь, правда?
                  Паскаль как и С очень близки к железу по организации доступа памяти. В данном случае в целях оптимизации была использована передачи аргументов в функцию через регистры, не используя стек. Для обычных задач это не требуется, но тут выжимал все соки.
                  +2
                  Добавил несколько строк кода
                  const SS = 100;
                  var a: array[1 .. SS]of longword;
                  var i: longint;
                  begin
                      for i := 1 to SS do a[i] := random(SS);
                      qSort_insSort(a, 0, SS - 1);
                      for i := 1 to SS - 1 do
                          if a[i - 1] > a[i] then begin
                              writeln('error i = ', i, ' a[i-1] = ', a[i - 1], ' a[i] = ', a[i]);
                              halt(2)
                      end;
                  end.
                  

                  и получил, что отсортировало с ошибкой. Может пришлёте версию, которая работает? Возможно, что что-то сделал не так сам — в этом случае надеюсь на корректирующую информацию.
                    +1
                    Благодарю за интерес к вопросу.
                    Собственно, у Вас должно всё нормально выводиться, но учтите, собирать проект нужно только под 64-битной версией компилятора. У Win32 и Win64 разные соглашения о вызовах. Если не разберётесь пишите в личку.
                    Заголовок спойлера
                    Procedure test();
                    const n=16;
                    var m:Array of LongWord;
                    i:LongWord;
                    begin
                    SetLength(m,n);
                    Randomize;

                    for i:=0 to Length(m)-1 do m[i]:=Random(9000)+1000;
                    for i:=0 to n-1 do WRITE(inttostr(m[i])+' ');
                    WRITELN('');

                    qSort_insSort(@m[0],0,n-1);

                    for i:=0 to n-1 do WRITE(inttostr(m[i])+' ');
                    WRITELN('');
                    end;

                      +1
                      Благодарю вас. Но почему в личку? У вас очень интересный код и если кто захочет его запустить, то наверняка эта дискуссия ему поможет. Там более паскаль сегодня многие не знают. 3наком с ABI x86, но тут что-то другое. Всё-таки непонятно почему мой код не работает правильно, передаю массив по ссылке, но он при выходе из пп не меняется, a если использую @a[0], то получаю ошибку Error: Call by var for arg no. 1 has to match exactly: Got «Pointer» expected "{Open} Array Of LongWord". :( Если запускаю код из вашего последнего примера, то картинка та же. Извините, сейчас нет времени самому разобраться в коде, жду Ваших подсказок. Повторю, мой код успешно собирается и запускается, только работает некорректно.
                        +1
                        Я очень извиняюсь, конечно же:
                        qSort_insSort(m,0,n-1);
                        По поводу Вашего кода, проверил загвоздка в том, что вы выделяете память на стеке, а нужно только в куче, так как стек и так интенсивно используется в работе процедуры. Так мы используем свободные регистры на адресацию к массиву.
                        Собрал проект на Lazarus64.
                          +2
                          У меня память выделяется не на стеке, а статично — это не проблема, если не хотим более 4 ГБ в массиве. Проблема была в том, что ABI для Microsoft Windows другой, а я с этой системой работаю мало и этого не знал. Пришлось чуть править код и использовать такой
                          код для Linux
                          ASM
                          CMP RDX,RCX // Если L>=R
                          JNB @@NO_RUN
                          CMP RSI,RCX // Если LENGTH(M)>=R
                          JA @@NO_RUN
                          CMP RDX,0 // Если L<0
                          JB @@NO_RUN
                          CMP RSI,0 // Если LENGTH(M)=0
                          JE @@NO_RUN
                          LEA RAX,[RDI+RCX*4]
                          LEA RCX,[RDI+RDX*4]
                          MOV RDX,RAX
                          CALL ASM_QSort
                          XOR RAX,RAX
                          JMP @@END
                          @@NO_RUN:
                          MOV RAX,1
                          @@END:
                          END;
                          

                          Получил ожидаемые результаты. На том же компьютере для 108 случайных чисел — 9.5 сек., а 109 случайных чисел — 107.8 сек. Это 15-е место среди приведенных сортировок, между qsort_dualpivot и spin. Отставание от qsort_dualpivot примерно 7%. Все прочие быстрые сортировки биты, а qsort_dualpivot также использует вставки. Но отставание от лидера — почти в 3 раза. Ещё почти уверен, что если перенести паскаль-код на С или С++ и скомпилировать с оптимизацией, то скорость будет примерно такая же или даже чуть быстрее из-за странных оптимизационных трюков. Обогнать оптимизирующий компилятор ручной работой с ассемблером сегодня очень сложно.
                            +1
                            Вы провели отличную работу. Пришёл к такому же выводу: микроассемблерные вставки не стоят тех усилий что на них затрачиваются, особенно при смене компилятора или платформы. Это был отличный опыт, отрицательный результат не менее ценен. Уверен из алгоритма можно ещё немного выжать, но зачем? Для большинства повседневных задач хватает библиотечных функций.
                              +2
                              Благодарю вас. Сделал
                              код на С
                              void MQSort(vector<int> &m, int l, int r) {
                              LOOP:
                                  if (r - l <= 20) {
                                      int i = l + 1, j;
                                      while (i <= r) {
                                          j = i++;
                                          while (j > 0 && m[j - 1] > m[j]) {
                                              swap(m[j - 1], m[j]);
                                              --j;
                                          }
                                      };
                                      return;
                                  }
                                  int o = m[(l + r)/2], i = l, j = r;
                                  do {
                                      while (m[i] < o) ++i;
                                      while (o < m[j]) --j;
                                      if (i <= j)
                                          swap(m[i++], m[j--]);
                                  } while (i <= j);
                                  if (l < j) MQSort(m, l, j);
                                  if (i < r) {
                                      l = i;
                                      goto LOOP;
                                  }
                              }
                              


                              И оказалось, что в данном случае ассемблерные вставки дали преимущество над g++ -O3 примерно в 12%. Код сортировки вставками можно чуть улучшить, взять, например, из quick_double_pivot. Само использование вставок даёт при сортировке случайных чисел примерно 10% ускорения. Спасибо за интересный код.
                                +1
                                Как вариант оптимизации, предлагаю Вам поиграться с коэффициентом выбора разбиения "<20" возможно на некоторых диапазонах его стоит делать меньше или больше, я выбрал среднее, возможно есть более оптимальные значения.
                                  +1
                                  del
                                    +1
                                    Исправил грубую ошибку в ассемблерном коде и немного изменил алгоритм, получил небольшой прирост в скорости (3-9%). Всё сильно зависит от исходных данных. Чем больше повторов в значениях тем быстрее работает относительно прежнего.
                                    Код
                                    // Комбинированная сортировка --------------------------------------------------
                                    procedure qSort_insSort2(var m : Array of LongWord; l,r : LongWord);
                                    procedure ASM_QSort assembler;
                                    ASM
                                    @@START_SORT:
                                    MOV R8,RCX // i:=0; Используется в обоих алгоритмах экономим 3 байта

                                    MOV RAX,RDX
                                    SUB RAX,RCX
                                    CMP RAX,R11

                                    JGE @@Q_Sort // Иначе сортируем быстрой сортировкой со срединным опорным элементом
                                    // Сортировка вставками --------------------------------------------------------
                                    //MOV R8,RCX // i:=0;
                                    @@I_BEGIN:
                                    ADD R8,R12 // i:=i+1;
                                    CMP R8,RDX // while (i<=r) do
                                    JA @@END // i>r
                                    MOV R9,R8 // j:=i;
                                    @@J_BEGIN:
                                    CMP R9,RCX // j<=0
                                    JNA @@I_BEGIN // Оканчиваем итерацию j

                                    MOV R10,R9 // (j)
                                    SUB R9,R12 // (j-1)
                                    MOV EAX,DWord[R9] // m[j-1]
                                    MOV EBX,DWord[R10] // m[j]
                                    CMP EAX,EBX // m[j-1]<=m[j]
                                    JNA @@I_BEGIN // Оканчиваем итерацию j

                                    MOV DWord[R9],EBX // Меняем местами
                                    MOV DWord[R10],EAX
                                    JMP @@J_BEGIN
                                    // Qsort с рекурсией -----------------------------------------------------------
                                    @@Q_Sort:
                                    //MOV R8,RCX

                                    ADD R8,RDX
                                    SHR R8,3
                                    SHL R8,2
                                    MOV R10D,DWord[R8] // находим срединный элемент

                                    MOV R8,RCX // i:= P1;
                                    MOV R9,RDX // j:= P2;

                                    @@i_START: // while (o < m[j]) do dec(j);
                                    MOV EAX,DWord[R8]
                                    CMP EAX,R10D
                                    JNL @@j_START // если больше или равно
                                    ADD R8,R12
                                    JMP @@i_START

                                    @@j_START: // while (PLongWord(j)^ > o) do dec(j,4);
                                    MOV EBX,DWord[R9]
                                    CMP EBX,R10D
                                    JNG @@j_STOP // если меньше или равно
                                    SUB R9,R12
                                    JMP @@j_START
                                    @@j_STOP:

                                    CMP R8,R9 // if (i <= j) then
                                    JG @@NO_XCHG // если меньше или равно
                                    MOV EAX,DWord[R8] // temp:=m[i]; m[i]:=m[j]; m[j]:=temp;
                                    MOV EBX,DWord[R9]
                                    MOV DWord[R8],EBX
                                    MOV DWord[R9],EAX
                                    ADD R8,R12 // inc(i); dec(j);
                                    SUB R9,R12
                                    @@NO_XCHG:

                                    CMP R8,R9 // until (i > j);
                                    JNG @@i_START // если меньше или равно

                                    CMP RCX,R9 // if (P1 < j) then
                                    JNB @@SORT1 // Jump, если больше или равно
                                    PUSH R8 // i
                                    PUSH RDX // p2
                                    // Первый аргумент (p1) уже в регистре RCX
                                    MOV RDX,R9 // Устанавливаем второй аргумент (j)
                                    CALL ASM_QSort // вызываем Сортировку первого отрезка (рекурсивно)

                                    POP RDX // p2
                                    POP R8 // i

                                    @@SORT1:
                                    CMP R8,RDX // if (i < P2) then
                                    JNB @@END // Jump, если больше или равно
                                    MOV RCX,R8 // Устанавливаем первый аргумент (i)
                                    // Второй аргумент (p2) уже в регистре RDX
                                    JMP @@START_SORT // вызываем Сортировку второго отрезка (Без рекурсии)
                                    @@END:
                                    END;
                                    begin
                                    ASM
                                    CMP R8,R9 // Если L>=R
                                    JNB @@NO_RUN
                                    CMP R9,RDX // Если R>LENGTH(M)
                                    JA @@NO_RUN
                                    CMP R8,0 // Если L<0
                                    JB @@NO_RUN
                                    CMP RDX,0 // Если LENGTH(M)=0
                                    JE @@NO_RUN
                                    LEA RDX,[RCX+R9*4]
                                    LEA RCX,[RCX+R8*4]

                                    MOV R11,100 // Будем хранить константу сравнения в регистре R11 так экономим 1 байт инструкций на каждом цикле
                                    MOV R12,4

                                    CALL ASM_QSort
                                    XOR RAX,RAX
                                    JMP @@END
                                    @@NO_RUN:
                                    MOV RAX,1
                                    @@END:
                                    END;
                                    end;

                                      +1
                                      Результат получился почти никакой. Ускорение только менее 1%. Оптимизировать современные ассемблеры штука непростая, тут две команды могут быть намного быстрее эквивалентной одной, неопределенности из-за поведения предикторов переходов и много других тонкостей. Приведу ещё некоторые данные по результатам работы с вашим кодом с миллиардом чисел: на нулевых данных — 33 cек. (20.5 место — между разными Шеллами), на случайных 0 и 1 — 36 сек. (9.5 место — между Шеллом и flat_stable), на диапазоне из 100 случайных чисел — 50.5 сек. (12.5 место — между std::sort и qsort_hoare2), на упорядоченных числах — 36.7 сек. (18.5 место — между Шеллом и утроенным массивом), на числах c инвертированным порядком — 37 сек. (11.5 место — между хешем и утроенным массивом), на частично упорядоченных числах — 48.3 сек. (7.5 место — между spread и flat_stable), на числах c частично инвертированным порядком — 48.2 сек. (9.5 место — между spread и spin), по заполнения типа 7 данных привести не могу — их пришлось бы ждать возможно больше года. :) Может как-нибудь перепишу ваш код в С++ и добавлю данные в таблицы…
                      +1
                      30 лет (в 1989 году) назад написал на турбопаскале свой первый профессиональный код — библиотеку сортировок. Алгоритмы черпал из третьего тома Кнута — быстрая, двойными включениями, прямым выбором, пузырьковая, шейкер, пирамидальная.

                      В 1991 году в рамках диплома пытался создать адаптивную (с точки зрения выбора алгоритма сортировки) систему для прикладных задач. Но все это так и осталось дипломом — в продакте используется исключительно быстрая сортировка. Кстати и по сей день — что является предметом моей гордости :)
                        +1
                        В каком продакшен? Быстрая сортировка сегодня — это не лучший выбор. Другие и быстрее, и стабильнее. А мой пример с qsort показывает, что хитрые способы выбора опорной точки не гарантируют от зависания.
                          +2
                          Продакшен — учетные ментовские задачи уровня райотдела и города (люди, оружие, прописка, загранпаспорта и т.д.). Написано, как Вы понимаете, очень давно по современным меркам. Реализация алгоритма изначально — классическая рекурсивная, по Кнуту. Потом добавили вариацию нерекурсивную. В таком виде эта штука 30 лет и работает :) Естественно, без зависаний :)
                            +1
                            А какой алгоритм вы бы посоветовали как дефолтную замену qsort? Без оптимизации под конкретную задачу с конкретными требованиями, а просто «вот это нужно сейчас отсортировать».
                              +1
                              Промахнулся с ответом. :) он рядом в общем потоке комментариев.
                          +1
                          Как показывают тесты, до десятков миллионов чисел даже сортировки Шелла чуть быстрее и последние стабильны, т.е. гарантируют, что зависания не случится. Для меня самого был сюрприз, что qsort сломалась на миллиарде чисел — случай скорее редкостный, но и не невозможный. Рекомедую «просто для сортировки» использовать средства из коробки — std::sort, std::stable_sort — работают существенно быстрее qsort, имеют гарантию от сюрпризов и работают с любыми данными. Если нужно сортировать большие массивы си-строк, то использование (s)radixsort даст ускорение в несколько раз, а spread-сортировка будет наибыстрейшей во многих других случаях. Если совсем мало памяти, то метод Шелла не подведет, отработает достаточно быстро. Опций много и лучше всего подбирать алгоритм по задаче.
                            +1
                            Спасибо за ответ!
                            Так std::sort — это ж и есть плюсовая шаблонная реализация quicksort, разве нет?
                              +1
                              нет, писал же — это интроспективная сортировка, которая иногда использует коды быстрой, но не всегда. И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN. Хотя мой материал показывает, что heapsort, которую иногда используют вместо быстрой, несколько медленнее, но гораздо быстрее N2.
                                +1
                                И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN.

                                Гм. Тут, как мне кажется, Вы неверно выразились. Позвольте сделать утверждение: «Не существует алгоритма сортировки, который имеет худшую сложность NlogN». Наверное, в стандартах C++ прописано что-то иное.

                                Что касается сортировки Шелла, то там лучшее время N log2 N (где двоечка — это квадрат логарифма), в то время как у быстрой среднее время N log N. Худшее время у них одинаковое N2 (квадрат). Источники — раз и два.

                                Поэтому можно сколько угодно написать «как показывают тесты ...», но математику никто не отменял и сути проистекающих процессов это не изменит.

                                Теперь что касается сортировки миллионов и миллиардов чисел. Можно ли привести пример прикладной области, в которой регулярно приходится сортировать такие большие наборы чисел и причем каждые раз разные? Конечно, мы можем пробовать конкретные реализации алгоритмов на прочность, как японскую бензопилу, из спортивного интереса. Но в реальной жизни это скорее всего означает большую ошибку проектирования.

                                  +1
                                  Насчет Шелла вы, возможно, не поняли о чем речь. N2 — это для случая плохих смещений — кто же с такими работает? А для хороших смещений в тексте статьи и в википедии предел худшести другой — N(log N/log log N)2 — это, повторю, очень мало отличается от Nlog N и мои результаты это очень хорошо подтверждают. Что касается, что миллиард — это много, то это почти смешно. Читал, что какие-то авторитеты в не так уж далёкое время утверждали, что 64 КБ — это много, а всем известный Билл говорил чуть позже примерно то же про 640 КБ… Данных много и гораздо больше миллиардов единиц. Как и писал, есть стабильные методы побыстрее Шелла, например, flat_stable… По std::sort смотрите стандарт — en.cppreference.com/w/cpp/algorithm/sort — поэтому правильное утверждение «существует много алгоритмов с худшим случаем NlogN» и более того поразрядные сортировки работают стабильно на любых данных с O(N).
                                    +2
                                    Насчет Шелла вы, возможно, не поняли о чем речь.

                                    Давайте я еще раз повторю свою мысль — лучшее время сортировки Шелла по вычислительной сложности уступает среднему времени быстрой сортировки. Это математически достоверный результат, а не «как показывают мои тесты». Вот Вам пруф о том, что средний результат сортировки Шела хуже N log N.
                                      +1
                                      Вы совершенно правы, никто с этим не спорит и не спорил. Но разница столь мала, что это преимущество быстрой сортировки с std::qsort (gcc) проявляется только на десятках и более миллионов единиц сортировки (извините, что приходится повторятся).
                                        +1
                                        Извиняюсь, не заменил в начале ложного утверждения, так как концовка была правильной. Лучшее время сортировки Шелла никак не уступает среднему времени быстрой сортировки. Тут всё очень просто, так лучшее время для Шелла — это на упорядоченной последовательности, отрабатывает гораздо быстрее лучшего времени быстрой. И причем тут тесты?
                                          +1
                                          Я говорил не про время, а про алгоритмическую сложность. Лучшее, среднее и худшее время есть доказанные математические формулы. Ссылки на них приводил — сравнение формул (N log2 N) vs (N log N) весьма наглядно. [Двойка в логарифме означает квадрат логарифма].

                                          А тесты здесь притом — Вы в своих доводах упоминаете «как показывают мои тесты» и дальше декларация чего-то. Это, хм-м, не аргумент. Вы можете сколько угодно на примерах демонстрировать скорость сортировки Шелла, но против формул не попрешь. Или Вы с ними не согласны?
                                            +1
                                            Мои тесты именно и подтверждают все формулы, кроме сортировок деревом и кучей. Последние случаи, как раз, хороший повод проверить эти методы кому-нибудь ещё. Могу предположить, что мне нужно кое-что объяснить. Что в формулах о скорости обычно присутствует символ О, который означает соответствие с точностью до множителя. Так вот эти множители они для практики весьма важны. У Шелла этот множитель меньше, чем у быстрой сортировки и это объясняет почему Шелл до довольно больших массивов обгоняет быструю.
                                        +1
                                        Что касается, что миллиард — это много, то это почти смешно.

                                        То есть реальных примеров привести не можете? Обсуждаем сферического коня в вакууме?
                                          +1
                                          поэтому правильное утверждение «существует много алгоритмов с худшим случаем NlogN» и более того поразрядные сортировки работают стабильно на любых данных с O(N).


                                          Я был неправ, а Вы правы в отношении худшей сложности. Например, вот — сортировка интросорт, имеет среднюю и наихудшую производительность N log N.

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

                                            +1
                                            Сортировка Шелла по сути является улучшенной версией сортировки вставками, поэтому, не исключено, что является одним из наилучших вариантов для крупных почти упорядоченных массивов.

                                            Сортировка простыми вставками на почти упорядоченных массивах достигает сложности O(n), мне пока неясно, почему в аналогичных условиях «шелл» должен показывать худшие результаты.
                                              +1
                                              Э-э-э, изначально вопрос звучал как «А какой алгоритм вы бы посоветовали как дефолтную замену qsort? Без оптимизации под конкретную задачу с конкретными требованиями, а просто «вот это нужно сейчас отсортировать».» и никто не говорил про «крупные почти упорядоченные массивы».

                                              То есть фрагмент ответа «Рекомедую «просто для сортировки» использовать средства из коробки» мне абсолютно понятен, а вот зачем всплыла сортировка Шелла — нет. Ну да ладно — возможно, ответ кроется в личных симпатиях автора :) Я же питаю симпатию к qsort :)
                                              +1
                                              Извините, но вы то, что выше, читали? там про эту интроспективную сортировку упоминалось не раз. Алгоритм Шелла не самый быстрый, но по совокупности свойств (скорости, требованию к дополнительной памяти, стабильности и простоте) вполне достойный. Поэтому его наверное и используют в таких критических местах как ядра ОС.
                                                +1
                                                Могу предположить, что если бы в интросорт использовали сортировку Шелла, а не кучей, то это было бы быстрее для случаев, когда быстрая сортировка не идёт.
                                                  +1
                                                  Мне кажется, что Ваше первое образование было гуманитарным, а потом Вы увлеклись сортировками.

                                                  Нигде в Ваших упоминаниях сортировки интро выше не звучало про её худшую вычислительную сложность N log N. Я же упомянул этот алгоритм исключительно в этом контексте — это была иллюстрация признания моей ошибки.

                                                  А что касается достойности алгоритма — не могу спорить, это такое понятие, которое формулой не измеришь. Нахождение его в ядре ОС означает, что алгоритм очень прозрачный и простой и разработчики совершенно к месту применяют Принцип Оккама.
                                                    +1
                                                    Звучало — дал Вам ссылку на стандарт С++. Кстати, может и другие мои хабр-статейки посмотрите? Критический настрой — ценная вещь.
                                                      +2
                                                      Проглядел список Ваших статей — увы, за пределами моих компетенций.

                                                      Но за эту статью и особенно за полемику к ней хочу Вас поблагодарить особо — получил и новые знания, и удовольствие.

                                                      Спасибо! :)
                                                    +1
                                                    del
                                                    +1
                                                    del
                                          +1
                                          del
                                            +1
                                            Весьма заинтересовало, как всё-таки хипсорт на очень больших массивах стал тормозить. Не может тут дело быть в том, что он не влезает в кэш и делает по сути рандомные обращения в сортируемые массив? То есть он продолжает оставаться O(N*log N), но уже в случае с неэффективным кэшем.
                                              +1
                                              Почему только на больших? Куча на числовых данных любого размера отстаёт по порядку даже от Шелла, но обычно чуть обгоняет дерево. А вот на строках куча обгоняет Шелла, что означает, что дорогих операций сравнения там всё же поменьше. Предполагая, что алгоритмы кучи и дерева заслуживают более тщательного изучения, официальные текущие данные по ним явно немного лучше реальных. Кэш, конечно, влияет, но он влияет и на другие алгоритмы. Осмелюсь утверждать, что у кучи и дерева (точнее их стандартных реализаций) имеем скорее O(Nlog2N) или даже чуть хуже. Провести соответствующие тесты совсем несложно…

                                            Only users with full accounts can post comments. Log in, please.