[Перевод] Я написал более быстрый алгоритм сортировки22.12.2021 06:16

От переводчика

Может показаться откровенной наглостью в наши дни утверждать, что Вы изобрели алгоритм сортировки, который на 30% быстрее, чем лучший существующий. Увы, я должен сделать гораздо более наглое заявление: я написал алгоритм сортировки, который в два раза быстрее, чем std: sort для многих входных данных. И за исключением случаев, когда я специально конструирую воспроизведение нахудших для него ситуаций, алгоритм никогда не бывает медленнее, чем std: sort (и даже когда попадаются эти худшие случаи, они обнаруживаются и происходит автоматический возврат к std: sort)

Почему это утверждение неудачное? Потому что мне, вероятно, будет сложно убедить вас в том, что я ускорил сортировку в два раза. Однако (чтобы всех убедить — перев.) всё это должно теперь оказаться (описанным — перев.) довольно длинным сообщением в блоге, а весь исходный код — открытым кодом, чтобы вы могли опробовать его на любых данных. Так что я либо могу убедить вас множеством аргументов и измерений, либо вы можете просто опробовать алгоритм сами.

Следуя (будучи продолжением — перев.) за моим предыдущим сообщением в блоге, (в статье автор неоднократно ссылается на своё предыдущее сообщение в блоге, описывающее его взгляд на классический Radix sort — прим. перев.) конечно же, это версия Radix sort. Что означает, что его сложность ниже, чем O (n log n). Я сделал два усовершенствования:

• оптимизировал внутренний цикл поразрядной сортировки на месте. Я начал с реализации сортировки по американскому флагу в Википедии, и сделал некоторые неочевидные улучшения. Это делает сортировку Radix намного быстрее, чем std: sort, даже для относительно небольших коллекций (от 128 элементов)

• обобщил поразрядную сортировку на месте для работы с целыми числами произвольного размера, числами с плавающей запятой, кортежами, структурами, векторами, массивами, строками и т. д. Я могу отсортировать все, что доступно с помощью операторов произвольного доступа, таких как operator [] или std: get. Если у вас есть настраиваемые структуры, вам просто нужно предоставить функцию, которая может извлекать ключ, который вы хотите отсортировать. Это тривиальная функция, которая менее сложна, чем оператор сравнения, который вам придется написать для std: sort.

Если вы просто хотите опробовать алгоритм, переходите к разделу «Исходный код и использование».

O (N) сортировка

Для начала я объясню, как вы можете построить алгоритм сортировки O (n). Если вы читали мой предыдущий пост в блоге, можете пропустить этот раздел. Если нет, читайте дальше:

Если вы типа меня месяц назад, вы точно знали, что доказано, что самый быстрый из возможных алгоритмов сортировки должен быть O (n log n). Есть математические доказательства того, что быстрее ничего не сделать. Я верил в это, пока не посмотрел вот эту лекцию из класса «Введение в алгоритмы» на MIT Open Course Ware. Там профессор объясняет, что сортировка должна быть O (n log n), когда все, что вы можете делать, это сравнивать элементы. Но если вам разрешено выполнять больше операций, чем просто сравнения, вы можете ускорить алгоритмы сортировки.

Я покажу пример с использованием алгоритма сортировки подсчетом:

template
void counting_sort(It begin, It end, OutIt out_begin, ExtractKey && extract_key)
{
    size_t counts[256] = {};
    for (It it = begin; it != end; ++it)
    {
        ++counts[extract_key(*it)];
    }
    size_t total = 0;
    for (size_t & count : counts)
    {
        size_t old_count = count;
        count = total;
        total += old_count;
    }
    for (; begin != end; ++begin)
    {
        std::uint8_t key = extract_key(*begin);
        out_begin[counts[key]++] = std::move(*begin);
    }
}

Эта версия алгоритма может сортировать только символы без знака. Или, скорее, он может сортировать только типы, которые могут предоставить ключ сортировки, который является беззнаковым символом. В противном случае мы бы индексировали вне допустимого диапазона в первом цикле. Позвольте мне объяснить, как работает алгоритм:

У нас есть три массива и три цикла. У нас есть входной массив, выходной массив и счетный массив. В первом цикле мы заполняем счетный массив, перебирая входной массив, считая, как часто появляется каждый элемент.

Второй цикл превращает счетный массив в префиксную сумму счетчиков. Допустим, в массиве не 256 записей, а всего 8 записей. Допустим, числа выпадают так часто:

Итак, в этом случае всего было девять элементов. Номер 1 появился дважды, номер 2 появился один раз, номер 4 появился пять раз, а номер 5 появился один раз. Так что, возможно, входная последовательность была {4, 4, 2, 4, 1, 1, 4, 5, 4}.

Последний цикл снова перебирает исходный массив и использует ключ для поиска в массиве суммы префиксов. И, о чудо, этот массив сообщает нам конечную позицию, в которой нам нужно сохранить целое число. Итак, когда мы перебираем эту последовательность, 4 переходит в позицию 3, потому что это значение, которое сообщает нам массив суммы префиксов. Затем мы увеличиваем значение в массиве так, чтобы следующие 4 переместились в позицию 4. Число 2 переместится в позицию 2, следующие 4 переместятся в позицию 5 (потому что мы уже увеличили значение в массиве суммы префиксов дважды) и т. Д. Я рекомендую вам пройти через это один раз вручную, чтобы прочувствовать это. Конечным результатом этого должно быть {1, 1, 2, 4, 4, 4, 4, 4, 5}.

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

Также обратите внимание, как это работает с любым типом, а не только с целыми числами. Все, что вам нужно сделать, это предоставить функцию extract_key () для вашего типа. В последнем цикле мы перемещаем указанный вами тип, а не ключ, возвращенный этой функцией. Так что это может быть любая настраиваемая структура. Например, вы можете отсортировать строки по длине. Просто используйте функцию size () в extract_key и ограничьте длину до 255. Вы можете написать модифицированную версию counting_sort, которая сообщает вам, где находится позиция последнего раздела, чтобы вы могли затем отсортировать все длинные строки с помощью std: sort (это должно быть небольшое подмножество всех ваших строк, чтобы второй проход по этим строкам был быстрым)

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

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

Самая очевидная проблема, с которой мы сталкиваемся, заключается в том, что когда мы меняем первый элемент с первой позиции, новый элемент, вероятно, не захочет быть на первой позиции. Вместо этого он может захотеть быть на позиции 10. Решение простое: продолжайте менять местами первый элемент, пока не найдем элемент, который действительно хочет (должен быть — прим.перев.) на первом месте. И только когда это произойдет, мы перейдем ко второму элементу массива.

Вторая проблема, с которой мы сталкиваемся, заключается в том, что мы обнаруживаем множество уже отсортированных разделов (частей массива — прим.перев.). Однако мы можем не знать, что они уже отсортированы. Представьте, что у нас есть число 3 два раза, и оно хочет быть на шестой и седьмой позициях. Допустим, при замене первого элемента на место мы меняем первые 3 на слот шесть, а вторые 3 на слот седьмой. Теперь они отсортированы, и нам больше не нужно с ними ничего делать. Но когда мы продвинемся от первого элемента, в какой-то момент мы встретим 3 в слоте шесть. И мы поменяем его местами на восьмерку, потому что это следующая точка, на которую попадет тройка. Затем мы находим следующие 3 и меняем их местами на девять. Затем мы снова находим первые 3 и меняем их местами на десять и т.д. Это продолжается до тех пор, пока мы не выйдем за границы массива и не сломаемся.

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

С этими двумя изменениями у нас получается алгоритм сортировки на месте, который сортирует символы без знака. Это сортировка типа американский флаг, описанная в Википедии.

RADIX сортировка на месте

Radix sort использует вышеуказанный алгоритм и обобщает его на целые числа, которые не помещаются в один символ без знака. Версия на месте фактически использует довольно простой трюк: сортируйте по одному байту за раз. Первая сортировка по старшему байту. Это разделит ввод на 256 разделов. Теперь рекурсивно отсортируйте в каждом из этих разделов, используя следующий байт. Продолжайте делать это, пока у вас не закончатся байты.

Если вы сделаете простые подсчёты, вы обнаружите, что для четырехбайтового целого числа вы получаете 256 ^ 3 рекурсивных вызовов: мы подразделяем на 256 разделов, затем рекурсивно, подразделяем каждый из них на 256 разделов и снова рекурсируем, а затем разделяем каждый из меньших разделов снова на 256 разделов и в последний раз выполняем рекурсию. Если бы мы действительно выполнили все эти рекурсии, это был бы очень медленный алгоритм. Способ обойти эту проблему — прекратить рекурсию, когда количество элементов в разделе меньше некоторого магического числа, и вместо этого использовать std: sort внутри этого подраздела. В моем случае я прекращаю рекурсию, когда размер раздела меньше 128 элементов. Когда я разбиваю массив на разделы с меньшим количеством элементов, я вызываю std: sort внутри этих разделов.

Если вам интересно: причина, по которой порог равен 128, заключается в том, что я делю вход на 256 разделов. Если количество разделов равно k, то сложность сортировки по одному байту составляет O (n + k). Точка, в которой сортировка radix выполняется быстрее, чем std: sort, — это когда цикл, зависящий от n, начинает преобладать над циклом, который зависит от k. В моей реализации это где-то около 0,5 тыс. Нелегко переместить его намного ниже (есть идеи, но пока ничего не работает).

Обобщение RADIX сортировки

Должно быть ясно, что алгоритм, описанный в последнем разделе, работает для беззнаковых целых чисел любого размера. Но он также работает и для коллекций целых чисел без знака (включая пары и кортежи) и строк. Просто отсортируйте по первому элементу, затем по следующему, затем по следующему и т.д., Пока размеры разделов не станут достаточно маленькими (на самом деле публикация которую Википедия называет источником своей статьи «Сортировка американский флаг», предназначалась для этого алгоритма как алгоритм сортировки строк).

Но это просто обобщить для работы со знаковыми целыми числами: просто переместите все значения вверх в диапазон беззнакового целого того же размера. Значение для int16_t просто приведите к uint16_t и добавьте 32768.

Майкл Херф также обнаружил хороший способ обобщить это для чисел с плавающей запятой: переинтерпретировать преобразование числа с плавающей запятой в uint32, затем перевернуть каждый бит, если число с плавающей запятой было отрицательным, но перевернуть только знаковый бит, если число с плавающей запятой было положительным. Тот же трюк работает с double и uint64s. Майкл Херф объясняет, почему это работает в публикации по ссылке, вкратце это выглядит так: положительные числа с плавающей запятой уже сортируются правильно, если мы просто переинтерпретируем их приведение к uint32. Показатель степени стоит перед мантиссой, поэтому мы будем сначала отсортировывать по экспоненте, а затем по мантиссе. Все получается. Однако отрицательные числа с плавающей запятой будут сортироваться неправильно. Переворачивание всех битов на них исправляет это. Последняя оставшаяся проблема заключается в том, что положительные числа с плавающей запятой необходимо сортировать как бОльшие, чем отрицательные, и самый простой способ сделать это — перевернуть знаковый бит, поскольку это самый старший бит.

Из основных типов остаются только логические значения и различные типы символов. Символы можно просто повторно интерпретировать в беззнаковые типы того же размера. Логические значения также можно преобразовать в беззнаковые символы, но мы также можем использовать специальный, более эффективный алгоритм для логических значений: просто используйте std: partition вместо обычного алгоритма сортировки. И если нам нужно выполнить рекурсию, потому что мы сортируем более чем по одному ключу, мы можем выполнить рекурсию в каждую из секций.

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

Оптимизация внутреннего цикла

Краткое описание алгоритма сортировки для сортировки одного байта:

• Подсчитайте элементы и создайте префиксную сумму, которая сообщает нам, где разместить элементы.

• Поменяйте местами первый элемент на место, пока мы не найдем элемент, который хочет быть на первой позиции (в соответствии с суммой префикса)

• Повторите шаг 2 для всех позиций.

Я реализовал этот алгоритм сортировки, используя сортировки со звуком Тимо Бингманна. Вот как это выглядит (и звучит):

Как видно из видео, большую часть времени алгоритм тратит на первую пару элементов. Иногда массив в основном сортируется по времени, когда алгоритм продвигается вперед от первого элемента. То, что вы не видите на видео, — это массив суммы префиксов, построенный сбоку. Визуализация сделала бы алгоритм более понятным (это прояснило бы, как алгоритм может знать конечное положение элементов, чтобы поменять их прямо там), но я не сделал эту визуализацию.

Если мы хотим отсортировать несколько байтов, мы рекурсивно переходим к каждому из 256 разделов и выполняем сортировку в тех, которые используют следующий байт. Но это не самая медленная часть. Медленная часть — это шаг 2 и шаг 3.

Если вы отпрофилируете этот код, вы обнаружите, что он тратит все свое время на подкачку. Сначала я подумал, что это из-за промахов кеша. Обычно, когда строка сборки, занимающая много времени, разыменовывает указатель, это промах в кэше. Я объясню, в чем была настоящая проблема, ниже, но даже при том, что моя интуиция ошиблась, это подтолкнуло меня к хорошему ускорению: если у нас есть промах в кэше для первого элемента, почему бы не попробовать заменить второй элемент на место во время ожидания для кеша промахнулись по первому?

Мне уже нужно хранить информацию о том, какие элементы поменялись местами, поэтому я могу их пропустить. Итак, что я делаю, так это перебираю все элементы, которые еще не были переставлены на свои места, и меняю их местами. За один проход по массиву это заменит как минимум половину всех элементов на свои места. Чтобы понять почему, давайте подумаем, как это работает в этом списке: {4, 3, 1, 2}: мы смотрим на первый элемент, 4, и меняем его местами на 2 в конце, давая нам следующий список: {2, 3, 1, 4}, затем мы смотрим на второй элемент, 3, и меняем его местами на 1, давая нам следующий список: {2, 1, 3, 4}, затем мы прошли итерацию на полпути по списку и обнаруживаем, что все оставшиеся элементы отсортированы (мы делаем это, проверяя, что смещение, сохраненное в массиве суммы префиксов, такое же, как начальное смещение следующего раздела), поэтому мы закончили, но наш список не отсортирован. Чтобы решить эту проблему, можно например, когда мы дойдем до конца списка, просто начать с самого начала, заменив все несортированные элементы на свои места. В этом случае нам нужно только переставить 2 на место, чтобы получить {1, 2, 3, 4}, после чего мы знаем, что все разделы отсортированы, и можно остановиться.

В Sound of Sorting это выглядит так:

Детали реализации

Вот как выглядит приведенный выше алгоритм в коде:

struct PartitionInfo
{
    PartitionInfo()
        : count(0)
    {
    }
 
    union
    {
        size_t count;
        size_t offset;
    };
    size_t next_offset;
};
 
template
void ska_byte_sort(It begin, It end, ExtractKey & extract_key)
{
    PartitionInfo partitions[256];
    for (It it = begin; it != end; ++it)
    {
        ++partitions[extract_key(*it)].count;
    }
    uint8_t remaining_partitions[256];
    size_t total = 0;
    int num_partitions = 0;
    for (int i = 0; i < 256; ++i)
    {
        size_t count = partitions[i].count;
        if (count)
        {
            partitions[i].offset = total;
            total += count;
            remaining_partitions[num_partitions] = i;
            ++num_partitions;
        }
        partitions[i].next_offset = total;
    }
    for (uint8_t * last_remaining = remaining_partitions + num_partitions, * end_partition = remaining_partitions + 1; last_remaining > end_partition;)
    {
        last_remaining = custom_std_partition(remaining_partitions, last_remaining, [&](uint8_t partition)
        {
            size_t & begin_offset = partitions[partition].offset;
            size_t & end_offset = partitions[partition].next_offset;
            if (begin_offset == end_offset)
                return false;
 
            unroll_loop_four_times(begin + begin_offset, end_offset - begin_offset, [partitions = partitions, begin, &extract_key, sort_data](It it)
            {
                uint8_t this_partition = extract_key(*it);
                size_t offset = partitions[this_partition].offset++;
                std::iter_swap(it, begin + offset);
            });
            return begin_offset != end_offset;
        });
    }
}

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

Третий цикл намного сложнее сортировки со счетом. Это три вложенных цикла, и только самый внешний является нормальным для цикла for:

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

Средний цикл использует std: partition для удаления завершенных разделов из списка оставшихся разделов. Я использую специальную версию std: partition, потому что std: partition развернет свой внутренний цикл, а я этого не хочу. Вместо этого мне нужно развернуть самый внутренний цикл. Но поведение custom_std_partition идентично поведению std: partition. Этот цикл означает, что если элементы попадают в разделы разного размера, например, для входной последовательности {3, 3, 3, 3, 2, 5, 1, 4, 5, 5, 3, 3, 5, 3, 3}, где разделы для 3 и 5 больше, чем для других разделов, это очень быстро завершит разделы для 1, 2 и 4, а затем после этого внешний цикл и внутренний цикл должны пройти только по разделам для 3 и 5. Вы могли подумать, что я мог бы использовать здесь std: remove_if вместо std: partition, но мне нужно, чтобы действие было неразрушающим, потому что мне понадобится тот же список разделов при выполнении рекурсивных вызовов. (не показано в этом листинге кода)

Самый внутренний цикл, наконец, меняет местами элементы. Он просто перебирает все оставшиеся несортированные элементы в разделе и меняет их местами в их окончательную позицию. Это был бы обычный цикл for, за исключением того, что нужно развернуть этот цикл, чтобы получить высокую скорость. Поэтому я написал функцию под названием «unroll_loop_four_times», которая принимает итератор и счетчик цикла, а затем разворачивает цикл.

Почему это быстрее

Этот новый алгоритм сразу оказался намного быстрее, чем сортировка по американскому флагу. Что имело смысл, потому что я думал, что обманул промахи кеша. Но как только я отпрофилировал код, я заметил, что этот новый алгоритм сортировки на самом деле имел немного больше промахов в кэше. Также было больше ошибочных предсказаний ветвей. Он также выполнил больше инструкций. Но как-то на это ушло меньше времени. Это было довольно загадочно, поэтому я описал это как только мог. Например, я запустил его в Valgrind, чтобы увидеть, что, по мнению Valgrind, должно происходить. В Valgrind этот новый алгоритм был на самом деле медленнее, чем сортировка по американскому флагу. В этом есть смысл: Valgrind — это просто симулятор, поэтому что-то, что выполняет больше инструкций, имеет немного больше промахов в кеше и немного больше неверных предсказаний ветвлений, будет медленнее. Но почему бы ему быстрее работать на реальном оборудовании?

Мне потребовалось больше дня, на разглядывание чисев в профилировке, прежде чем я понял, почему это было быстрее: лучше параллелизм на уровне инструкций. Вы не могли бы изобрести этот алгоритм на старых компьютерах, потому что на старых компьютерах он был бы медленнее. Большая проблема с сортировкой по американскому флагу заключается в том, что ей нужно дождаться завершения текущего свопа, прежде чем он сможет начаться при следующем обмене. Не имеет значения, что нет промаха в кэше: современные процессоры могут выполнять несколько свопов одновременно, если только им не нужно ждать завершения предыдущего. Развертывание внутреннего цикла также помогает в этом. Современные процессоры великолепны, поэтому они могут запускать несколько циклов параллельно даже без развертывания цикла, но развертывание цикла помогает.

Команда perf в Linux имеет метрику, называемую «инструкций на цикл», которая измеряет параллелизм на уровне инструкций. В сортировке по американскому флагу мой процессор выполняет 1,61 инструкции за цикл. В этом новом алгоритме сортировки он достигает 2,24 инструкций за цикл. Неважно, нужно ли вам выполнять еще несколько инструкций, если вы можете делать на 40% больше за раз.

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

При этом для небольших коллекций сортировка по американскому флагу выполняется быстрее. Кажется, что параллелизм на уровне инструкций действительно применяется в коллекциях из более чем тысячи элементов. Итак, мой окончательный алгоритм сортировки на самом деле смотрит на количество элементов в коллекции, и если оно меньше 128, я вызываю std: sort, если меньше 1024, я вызываю сортировку по американскому флагу, а если больше этого, я запускаю свой новый алгоритм сортировки.

std: sort на самом деле представляет собой аналогичную комбинацию, сочетающую быструю сортировку, сортировку вставкой и сортировку кучей, поэтому в некотором смысле они также являются частью моего алгоритма. Если бы я достаточно постарался, я мог бы построить входную последовательность, которая фактически использует все эти алгоритмы сортировки. Эта входная последовательность была бы моим наихудшим случаем: мне пришлось бы вызвать наихудшее поведение сортировки по основанию, чтобы мой алгоритм вернулся к std: sort, а затем мне также пришлось бы запустить наихудшее поведение быстрой сортировки, поэтому этот std: sort возвращается к сортировке кучей. Итак, давайте поговорим о худших и лучших случаях.

Лучший и худший случай

Наилучший случай для моей реализации сортировки по основанию — это если входные данные помещаются в несколько разделов. Например, если у меня есть тысяча элементов, и все они попадают только в три раздела (скажем, у меня просто число 1 сто раз, число 2 — четыреста раз и число 3 — пятьсот раз), тогда мои внешние циклы почти ничего не делают, и мой внутренний цикл может переставить все на свои места в красивых длинных непрерывных прогонах.

Мой другой лучший случай — это уже отсортированные последовательности: в этом случае я перебираю данные ровно дважды: один раз для просмотра каждого элемента и один раз для замены каждого элемента самим собой.

Наихудший случай для моей реализации может быть достигнут только при сортировке данных переменного размера, таких как строки. Для ключей фиксированного размера, таких как целые числа или числа с плавающей запятой, я не думаю, что это действительно плохой случай для моего алгоритма. Один из способов построить наихудший случай — отсортировать строки «a», «ab», «abc», «abcd», «abcde», «abcdef» и т.д. Так как radix sort просматривает один байт за раз, и это byte позволяет выделить из себя только один элемент, это займет время O (n ^ 2). Моя реализация определяет это, записывая, сколько было рекурсивных вызовов. Если их слишком много, я возвращаюсь к std: sort. В зависимости от вашей реализации быстрой сортировки это также может быть худшим случаем для быстрой сортировки, и в этом случае std: sort возвращается к сортировке кучей. Я кратко отладил это, и мне показалось, что std: sort не вернулся к сортировке кучей для моего тестового примера. Причина этого в том, что в моем тестовом примере были отсортированные данные, а std: sort, похоже, использует правило медианы трех для выбора точки поворота, которое выбирает хорошую точку поворота для уже отсортированных последовательностей. Зная это, вероятно, можно создать последовательности, которые попадут в наихудший случай как для моего алгоритма, так и для быстрой сортировки, используемой в std: sort, и в этом случае алгоритм вернется к сортировке кучей. Но я не пытался построить такую ​​последовательность.

Я не знаю, насколько распространен этот случай в реальном мире, но одна уловка, которую я взял из реализации ускоренной реализации поразрядной сортировки, заключается в том, что я пропускаю общие префиксы. Итак, если вы сортируете сообщения журнала и у вас много сообщений, начинающихся с «warning:» или «error:», то моя реализация Radix-сортировки сначала отсортирует их по отдельным разделам, а затем внутри каждого из этих разделов будет пропускать общий префикс и продолжать сортировку с первого отличающегося символа. Такое поведение должно помочь снизить частоту возникновения наихудшего случая.

В настоящее время я возвращаюсь к std: sort, если мой код повторяется более шестнадцати раз. Я выбрал это число, потому что это была первая степень двойки, для которой определение наихудшего случая не срабатывало при сортировке некоторых файлов журнала на моем компьютере.

Резюме алгоритма и его наименование

Алгоритм сортировки, который я предоставляю в виде библиотеки, называется «Ska Sort». Потому что я не собираюсь придумывать новые алгоритмы очень часто в своей жизни, так что с таким же успехом могу поставить свое имя на одном из них, когда это сделаю. Улучшенный алгоритм сортировки байтов, который я описал выше в разделах «Оптимизация внутреннего цикла» и «Детали реализации», является лишь небольшой частью этого. Этот алгоритм называется «Ska Byte Sort».

Таким образом, Ska Sort:

• Алгоритм сортировки по основанию на месте

• Сортирует по одному байту (на 256 разделов)

• Возвращается к std: sort, если коллекция содержит меньше некоторого порога элементов (в настоящее время 128)

• Использует внутренний цикл сортировки по американскому флагу, если коллекция содержит меньше большего порога элементов (в настоящее время 1024)

• Использует Ska Byte Sort, если коллекция больше этого (порога — перев.)

• Вызывает себя рекурсивно для каждого из 256 разделов, используя следующий байт в качестве ключа сортировки

• Возвращается к std: sort, если он повторяется слишком много раз (в настоящее время 16 раз)

• Использует std: partition для сортировки логических значений

• Автоматически преобразует целые числа со знаком, числа с плавающей запятой и типы символов в правильный целочисленный тип без знака

• Автоматически обрабатывает пары, кортежи, строки, векторы и массивы, сортируя по одному элементу за раз

• Пропускает общие префиксы коллекций (например, при сортировке строк)

• Предоставляет две точки настройки для извлечения ключа сортировки из объекта: объект функции, который может быть передан в алгоритм, или функция с именем to_radix_sort_key (), которую можно поместить в пространство имен вашего типа.

Итак, Ska Sort — сложный алгоритм. Конечно, сложнее простой быстрой сортировки. Одна из причин этого заключается в том, что в Ska Sort у меня гораздо больше информации о типах, которые я сортирую. В алгоритмах сортировки на основе сравнения все, что у меня есть, — это функция сравнения, которая возвращает логическое значение. В Ska Sort я могу знать, что «для этой коллекции мне сначала нужно выполнить сортировку по логическому значению, а затем по плавающему значению», и я могу написать собственный код для обоих этих случаев. На самом деле мне часто нужен собственный код: код, сортирующий кортежи, должен отличаться от кода, сортирующего строки. Конечно, у них один и тот же внутренний цикл, но им обоим нужно выполнять разную работу, чтобы добраться до этого внутреннего цикла. При сортировке на основе сравнения вы получаете одинаковый код для всех типов.

Оптимизации, которых я не делал

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

Во-первых, часть, в которой говорится о сортировке чисел с плавающей запятой, сортирует 11 бит за раз, а не по одному байту за раз. Это означает, что он делит диапазон на 2048 разделов вместо 256 разделов. Преимущество здесь заключается в том, что вы можете отсортировать четырехбайтовое целое число (или четырехбайтовое число с плавающей запятой) за три прохода вместо четырех. Я опробовал это в своем (упоминавшемся ранее — перев.) предыдущем сообщении в блоге и обнаружил, что это работает быстрее только в некоторых случаях. В большинстве случаев это было медленнее, чем сортировка по одному байту за раз. Возможно, стоит попробовать еще раз этот трюк для сортировки по основанию счисления на месте, но я этого не делал.

Во-вторых, в статье American Flag Sort говорится об управлении рекурсиями вручную. Вместо того, чтобы делать рекурсивные вызовы, они хранят стек всех разделов, которые еще нужно отсортировать. Затем они зацикливаются, пока этот стек не станет пустым. Я не пробовал эту оптимизацию, потому что мой код и так слишком сложен. Эту оптимизацию проще выполнить, если вам нужно только отсортировать строки, потому что вы всегда используете одну и ту же функцию для извлечения текущего байта. Но если вы можете сортировать целые числа, числа с плавающей запятой, кортежи, векторы, строки и многое другое, это сложно.

Демонстрация производительности

Наконец, мы подошли к тому, насколько быстрым на самом деле является этот алгоритм. Со времени моего предыдущего сообщения в блоге я изменил способ вычисления этих чисел. В своем предыдущем сообщении в блоге я совершил большую ошибку: я измерил, сколько времени уходит на настройку моих тестовых данных и их сортировку. Проблема в том, что настройка может занимать значительную часть времени. Так что на этот раз я также измеряю настройку отдельно и вычитаю это время из измерений, так что у меня остается только время, необходимое для фактической сортировки данных. Итак, приступим к нашему первому измерению: Сортировка целых чисел: (сгенерировано с использованием std: uniform_int_distribution)

Этот график показывает, сколько времени занимает сортировка различного количества элементов. Раньше я не упоминал ska_sort_copy, но, по сути, это алгоритм из моего предыдущего сообщения в блоге, за исключением того, что я изменил его так, чтобы он возвращался к ska_sort вме

© Habrahabr.ru