Как я написал алгоритм сортировки, который быстрее std::sort. Продолжение

Прим. Wunder Fund: не спешите минусовать эту публикацию — её перевода на Хабре ещё не было :)

Это — продолжение моей предыдущей публикации (вот — первая, вторая и третья части перевода), посвящённой тому, как я создал алгоритм сортировки, который быстрее std::sort. Эта статья — мой шанс углубиться в те детали, о которых меня спрашивали в комментариях. Я собираюсь разъяснить здесь некоторые вещи, которые оказались непонятными аудитории, и поговорить о будущем моего алгоритма, о доработках, в которых он нуждается.

Кто-то, за что я этому неизвестному благодарен, разместил ссылки на мою статью на Hacker News и на Reddit. И хотя эти ссылки там разместил не я, я, всё же, прочитал большую часть комментариев, сделанных пользователями этих сайтов. По какой-то причине те комментарии, что были сделаны в моём блоге, оказались гораздо позитивнее, чем комментарии на Hacker News и Reddit. Но у меня такое ощущение, что причина появления негативных комментариев заключается, в целом, в неправильном понимании того, о чём я пишу. Здесь я собираюсь расставить все точки над «i».

Прим. Wunder Fund 2: ну, вы наверное, и сами догадываетесь, как мы любим быстрые алгоритмы и оптимизации. Если вы тоже такое любите — вы знаете, что делать)

Обобщение поразрядной сортировки

Смысл самого популярного комментария на Hacker News заключается в следующем: «Ну не знаю… Этот алгоритм не может сортировать всё что угодно, да и всем известно, что поразрядная сортировка быстрее std::sort». Во-первых, мне не понятен источник этого негатива. Мой предыдущий материал, если выразить его в нескольких словах, выглядит так: «Всем привет! Мне не терпится поделиться рассказом о том, как я оптимизировал и обобщил поразрядную сортировку». А первая реакция читателей на это выглядит как «обобщил, да не совсем». В чём причина этого негатива? Я сделал шаг вперёд, а читатели сетуют на то, что я не сделал два шага. Почему бы просто не порадоваться тому факту, что я сделал область применения поразрядной сортировки шире, чем раньше?

Поэтому я хочу больше, чем прежде, рассказать об обобщении поразрядной сортировки. Примером того, что мой алгоритм сортировать не может, является вектор значений std::set. Предположим, речь идёт о векторе, в состав которого входят множества, состоящие из целых чисел. Причина, по которой я не могу его отсортировать, заключается в том, что в std::set нет чего-то вроде operator[]. У std::sort такой проблемы нет, так как std::set предоставляет операторы сравнения.

Имеется два возможных варианта решения этой проблемы:

1. Там, где я сейчас использую operator[], я мог бы применить, вместо этой конструкции, std::next. В результате, вместо того, чтобы писать container[index], я пользовался бы конструкцией вида *std::next(container.begin(), index).

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

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

Я, кроме того, не хотел выделять дополнительную память, которая понадобилась бы для реализации второго подхода. Дело в том, что мне не хотелось бы, чтобы ska_sort иногда требовалось бы выделение памяти в куче, а иногда — нет — в зависимости от типа сортируемых данных.

Смысл тут вот в чём: я легко могу обобщить поразрядную сортировку ещё сильнее, что позволит ей справляться и с описанным случаем, но интересным мне это не кажется. Оба подхода к такому обобщению имеют очевидные проблемы. Полагаю, для сортировки векторов std::set следует просто воспользоваться std::sort. Поэтому я и ограничил возможности ska_sort сортировкой тех структур данных, доступ к элементам которых можно получить за константное время.

Вот ещё один вопрос, который возникает у меня при чтении комментариев: «Почему вы хотите, чтобы мой алгоритм это поддерживал?». Я остановился на том уровне обобщения алгоритма, когда мне показалось, что он уже поддерживает все реальные варианты его возможного применения. Если нужно — алгоритм поразрядной сортировки можно обобщать и дальше, сделав так, чтобы он мог бы обрабатывать всё что угодно. Если кому-то и правда надо сортировать векторы std::set, или векторы std::list, тогда я, вероятно, специально для тех, кому это надо, реализовал бы второй из вышеописанных подходов к сортировке таких сущностей. Но главный вопрос заключается не в том, может ли ska_sort сортировать всё что угодно. Главный вопрос — это может ли некто сортировать с помощью ska_sort то, что ему нужно. И почти всегда на этот вопрос можно дать положительный ответ. Если у кого-то и правда есть задача сортировки, которую не способен решить ska_sort, тогда критика алгоритма мне понятна. Но о чём именно идёт речь? Что, к элементам чего нельзя обратиться за константное время, хотят с его помощью сортировать критики алгоритма?

Учитывая вышесказанное, отмечу, что есть одна реальная проблема, которую мне ещё предстоит решить. Это — возможность настройки поведения реализации алгоритма. Об этом я писал и в предыдущем материале. Особенно это важно при сортировке строк. Там, как раз, часто встречается необходимость в подстройке алгоритма под конкретную задачу. Например — при сортировке без учёта регистра символов. Или — при сортировке строк с учётом содержащихся в них числовых значений, когда, например, надо, чтобы строка foo100 шла бы после строки foo99. О том, как этого можно добиться, я расскажу ниже. Но решение этой задачи заключается не в дальнейшем обобщении ska_sort, благодаря чему с помощью моего алгоритма можно было бы сортировать большее количество типов данных. Её решение заключается в том, чтобы дать пользователю больше возможностей по настройке алгоритма при обработке данных, которые он уже способен сортировать.

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

>" title="Сортировка std::vector<std::set<int>>" height="394" data-src="https://habrastorage.org/getpro/habr/upload_files/326/e59/8f3/326e598f3548b515c54d150c690f406f.png" data-width="650"/>

По графику видно, что на довольно большом количестве тестовых наборов данных ska_sort лучше std::sort. А std::sort становится быстрее ska_sort лишь на довольно объёмных наборах данных. Если я конструирую наборы данных так, чтобы между ними были бы очень небольшие перекрытия, то ska_sort, на самом деле, всегда оказывается быстрее. Значит ли это, что мне надо выложить этот код в общий доступ? Я решил пока этого не делать, так как не считаю этот мой код, так сказать, «чистой победой». Я так думаю, если бы я решил включить этот функционал в общедоступный код моего алгоритма, то я реализовал бы в нём второй подход, где делается выделение памяти, так как я ожидаю того, что он покажет лучшие результаты.

Яблоки и апельсины. Сравнение поразрядной сортировки и std::sort

Один из критических выпадов в мою сторону, который поначалу был мне непонятен, заключается в том, что сравнивать ska_sort и std::sort — это как сравнивать яблоки и апельсины. Он озвучен всё в том же комментарии на Hacker News, ссылку на который я давал выше. С моей точки зрения и ska_sort, и std::sort — это алгоритмы сортировки. Какая разница — как именно устроены их внутренние механизмы? Если кому-то надо что-то сортировать, то единственное, что его заботит — это скорость сортировки, а не то, что происходит в недрах реализации алгоритма.

У моего друга по этому поводу появилась хорошая аналогия: «Сравнивать улучшенную поразрядную сортировку с std::sort — это всё равно, что написать реализацию хеш-таблицы, и рассказать о ней, указав на то, насколько она быстрее std::map».

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

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

Правда, вышеозвученные аргументы для меня значения не имеют, так как я сделал два заявления. Во-первых — то, что я обобщил поразрядную сортировку. Во-вторых — то, что я этот вариант сортировки оптимизировал. Второе заявление мне стоило бы подтвердить тестами производительности, в которых сравнивалась бы реализация моего алгоритма и другие реализации поразрядной сортировки. И, кроме того, несмотря на то, что нечто вроде boost::spreadsort не в состоянии выполнить все мои тесты, мне, всё же, стоило бы сравнить мой алгоритм с этими, воспользовавшись тестами, которые они способны выполнить. То есть — это сортировка целых чисел, чисел с плавающей точкой и строк. Признаю, что я не знаю, о чём тогда думал… Иногда мозг просто перескакивает к неверным выводам, а потом уже и не задумываешься о том, что привело к таким выводам…

Ну, как бы там ни было, вот — сравнение ska_sort c boost::spreadsort на сортировке равномерно распределённых целых чисел.

Тут видно, что, в целом, ska_sort быстрее boost::spreadsort. Исключение составляет лишь область между 2048 и 16384. Причиной этого, в основном, является тот факт, что алгоритмы делят сортируемые элементы на разное количество разделов. На каждом шаге рекурсии я разбиваю входные данные на 256 разделов, а boost::spreadsort — на большее количество разделов. Алгоритм boost::spreadsort не использует, в отличие от ska_sort, фиксированное количество разделов, в результате я, характеризуя boost::spreadsort, не могу назвать некое конкретное число. Я могу лишь говорить о том, что это число обычно больше чем 256.

Я поэкспериментировал с разными количествами разделов в моём первом материале о поразрядной сортировке, но тогда ничего особенного это не дало. Тогда я обнаружил, что если используется 2048 разделов, то сортировка проходит быстрее в том случае, когда коллекция содержит от 1024 до 2048 элементов. В других случаях быстрее оказалось использование 256 разделов. Возможно, мне, по образцу boost::spreadsort, стоит попробовать переменное количество разделов. Может, у меня получится выйти на алгоритм, который всегда будет быстрее boost::spreadsort. Вот так вот и получилось, что пользу принесло всего лишь обычное сравнение моей реализации поразрядной сортировки с другой её реализацией.

Теперь предлагаю взглянуть на исследование сортировки равномерно распределённых чисел с плавающей точкой.

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

Второе я объяснить не могу. Но это поведение поддаётся воспроизведению, в результате его можно подвергнуть дополнительным исследованиям. Лучшее, что я могу придумать, заключается в том, что такое поведение алгоритмов объясняется тем, что uniform_real_distribution просто не может выдать достаточно много уникальных значений. (Я запрашивал у генератора числа с плавающей точкой в диапазоне от 0 до 1). Поэтому тут появляется больше дублирующихся значений, чем тогда, когда количество сортируемых элементов невелико. Я попытался генерировать тестовые наборы с помощью exponential_distribution, но получил похожие графики.

Причина, по которой у графика boost::spreadsort наблюдаются волны меньшего размера, может заключаться в том, что этот алгоритм подстраивается под размер диапазона входных элементов. При сортировке целых чисел ему могут поступить числа во всём диапазоне, укладывающемся в 32 бита. А при сортировке чисел с плавающей точкой он получает лишь значения в диапазоне от 0 до 1. Мне нужно ещё поразбираться с тем, что boost::spreadsort на самом деле делает с этой информацией, но он её обрабатывает и использует её для определения того, сколько разделов ему использовать. У нас нет времени на углубление в этот вопрос. Вместо этого давайте посмотрим на сортировку строк.

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

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

   А boost::spreadsort делает это за один проход. Нет причины, по которой я не могу поступить так же. Единственное неудобство заключается в том, что это ещё сильнее усложнит мой алгоритм, так как мне придётся написать два немного разных варианта внутреннего цикла. Я, когда смогу, это попробую.

2. Алгоритм boost::spreadsort пользуется тем, что строки всегда хранятся в одном фрагменте памяти. Когда он пытается найти самый длинный общий префикс для этих строк, он использует команду memcmp, внутри которой применяется одновременное сравнение нескольких байтов. В моём алгоритме нет особых механизмов для обработки строк. Он одинаково работает со строками, с двусторонними очередями, с векторами, с массивами, или с чем угодно другим, поддерживающим конструкцию operator[]. Это значит, что я, за один раз, вынужден выполнять обработку лишь одного элемента, так как, если попытаться отсортировать std::deque, memcmp работать не будет. Решить эту проблему можно было бы, разработав специализированный механизм для обработки контейнеров, имеющих функцию .data(). Но это, правда, приведёт к ещё одной проблеме. Она может возникнуть при сортировке вектора пользовательских типов, а в этом случае memcmp, снова, окажется неправильным выбором. Эта проблема, кажется, решаема. Мне просто понадобится больше особых шаблонов для тех случаев, когда то, что сортируется, представляет собой указатель на символ, заключённый в контейнер, поддерживающий функцию .data(). Сделать это можно, но это ещё сильнее усложнит мой алгоритм.

В итоге могу сказать, что пока boost::spreadsort сортирует строки быстрее, чем ska_sort. Причина этого лишь в том, что мне сейчас не хочется тратить время на реализацию в ska_sort тех же оптимизаций, которые имеются в boost::spreadsort.

О временной сложности алгоритмов

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

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

2. Если я могу разделить все значения, ориентируясь на первый байт, то сразу после этого рекурсию можно остановить.

Комментарий указывает на то, что эти два заявления применяются к различным диапазонам входных значений. Да, так оно и есть. Комментатор смеётся надо мной из-за того, что я не говорю о том, что это применимо к разным диапазонам входных данных. Потом там обсуждаются разные мелочи, вроде имён внутренних переменных, там даётся некорректный совет об объединении циклов и о перебросе данных между буферами в ska_sort_copy. (При перебросе данных между буферами A и B нельзя запустить цикл, читающий данные из B, до тех пор, пока цикл, читающий данные из A, не завершит запись в B. В противном случае будут прочитаны неинициализированные данные). И я совершенно не понимаю — почему это — самый популярный комментарий…

Но то, что такой комментарий существует, послужит оправданием необходимости моего рассказа о работе с рекурсивными вызовами и о временной сложности моего алгоритма. Что-то об этом есть во многих комментариях (включая ответы на тот комментарий).

Принятие решений в тот момент, когда я должен приступить к рекурсивной обработке второго байта, в реальности, выглядит сложнее, чем может показаться. А именно, я перехожу к std::sort в том случае, если в разделе имеется менее 128 элементов. Это значит, что если входные данные, при анализе первого байта значений, характеризуются равномерным распределением, то окажется, что я могу обработать до 127*256 = 32512 элементов без каких-либо рекурсивных вызовов. Источником значения 256 является количество значений, которые может принимать первый байт. А смысл числа 127 в том, что если я создал 256 разделов по 127 элементов в каждом, то в каждом из этих разделов я перейду на std::sort вместо того, чтобы рекурсивно, второй раз, вызывать ska_sort.

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

«Волны» на графике ska_sort появляются каждый раз, когда мне приходится делать дополнительный рекурсивный вызов. Получается, что центральная волна, идущая от тестового набора размером 4096 элементов до набора в 16384 элементов, получается в ситуации, когда код, просматривающий первые байты, создаёт все больше и больше разделов, достаточно больших для того, чтобы их обработка потребовала бы рекурсивного вызова ska_sort. Например, предположим, что в последовательности из 2048 элементов я случайным образом получаю 80 элементов со значением 62 в первом байте. Затем, в последовательности из 4096 элементов, у меня уже 130 таких же значений. Обрабатывая последовательность с 2048 элементами, я непосредственно вызываю std::sort. А на 4096 элементах я выполняю дополнительный рекурсивный вызов, разделяя эти 130 элементов ещё на 256 разделов, после чего вызываю для каждого из них std::sort.

Затем, после пересечения отметки 16384, оказывается, что разделы достаточно велики для того, чтобы можно было бы обрабатывать их в замечательных длительных циклах. Алгоритм снова ускоряется. Это — до тех пор, пока мне не нужно второй раз выполнять рекурсию, что происходит на 512 тысячах элементов, после чего алгоритм снова замедляется.

При сортировке целых чисел существует естественный лимит таких волн. Их, самое большее, может быть четыре, так как значения целочисленного типа состоят всего из четырёх байтов.

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

Для начала, я заявляю, что в моём случае один проход по данным имеет временную сложность O(n). Это, при взгляде на исходный код, неочевидно, так как тут имеется пять циклов, три из которых являются вложенными. Но после более пристального изучения кода становится понятным, что эти циклы зависят от двух вещей. Во-первых — от количества разделов. Во-вторых — от количества элементов в коллекции. В результате первая догадка по поводу временной сложности алгоритма выглядит как O(n+p), где p — количество разделов. Это число в моём алгоритме не меняется и составляет 256, в результате мы выходим на значение O(n+256), которое сводится к O(n). Но это вот значение 256 является причиной замедления ska_sort в тех случаях, когда при обработке данных получается много маленьких разделов.

Теперь каждый раз, когда я не могу разделить элементы на разделы, размеры которых меньше чем 128 элементов, мне нужно выполнять рекурсивный вызов. Как это влияет на временную сложность алгоритма? Если взглянуть на это, ни о чём особо не задумываясь, то получится O(n*b), где b — это количество байтов, которые нужно просмотреть до тех пор, пока я не смогу различить все элементы. При сортировке целых чисел это будет, в худшем случае, 4. В результате мы получаем значение O(n*4), которое тоже сводится к O(n). При сортировке чего-либо с переменным количеством байтов, вроде строк, это b, правда, может оказаться сколько угодно большим. Один из приёмов, который я применяю для того, чтобы избежать по-настоящему плохого случая алгоритма, заключается в пропуске общих префиксов. Но при этом несложно создать набор входных данных, в котором b равняется n. В результате временной сложностью алгоритма при сортировке строк будет O(n^2). Но я выявляю подобные ситуации и перехожу на сортировку всех данных с помощью std::sort. В результате временной сложностью ska_sort при сортировке строк является O(n log n).

Мне, правда, больше нравится выражение O(n*b), так как график не выглядит как график O(n) (хотя график ska_sort_copy и выглядит как график O(n)). Выражение O(n*b) даёт лучшее представление о том, что происходит на самом деле. А взглянув на волны, присутствующие на графике, можно сказать о том, в какой именно точке значение b увеличилось на 1. Так же можно увидеть, что b не является значением, независимым от n. (Оно станет независимым от n при достаточно большом размере n. Предположим — когда сортируют триллион целых чисел. Но при небольших n значение b растёт вместе с n).

Эти рассуждения могут навести вас на мысль о том, что мой алгоритм работает медленнее всего тогда, когда все числа очень близки друг к другу. Предположим, все они близки к 0, а мне, чтобы их различить, придётся просмотреть по четыре байта каждого из них. Но, на самом деле, всё происходит с точностью до наоборот. А именно, в таких случаях мой алгоритм работает быстрее всего. Причина этого в том, что первые три прохода по данным в такой ситуации выполняются очень быстро, так как в первых трёх байтах всех элементов хранятся одни и те же значения. Лишь на последнем проходе выполняются какие-то действия. (Это — график сортировки геометрически распределённых целых чисел из моего предыдущего материала, где ska_sort, в итоге, на последовательностях больших размеров, оказывается более чем в пять раз быстрее std::sort).

И наконец, говоря о временной сложности моего алгоритма, мы должны учитывать то, что в некоторых ситуациях он предусматривает переход на std::sort. А обращение к std::sort происходит на разделах, содержащих менее 128 элементов. То есть временная сложность с учётом перехода на std::sort составляет не O(n log n), а O(n log 127), то есть — просто O(n). O(n log 127) тут получается по нескольким причинам:

1. Я вызываю std::sort для каждого элемента, то есть сложность должна быть как минимум O(n).

2. Каждому из этих вызовов std::sort видны лишь 127 элементов, в результате рекурсивные вызовы алгоритма быстрой сортировки ограничены, а при этом именно они ответственны за часть «log 127» в выражении O(n log 127).

Если вам кажется, что звучит это странно, учтите, что алгоритм интроспективной сортировки (introsort), который используется в std::sort, имеет временную сложность O(n log n), несмотря на то, что в ходе его работы для каждого элемента вызывается сортировка вставкой (временная сложность этого алгоритма — O(n^2)).

Другие обобщённые варианты алгоритма поразрядной сортировки

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

Один из примеров такого обобщения — алгоритм BinarSort, созданный Уильямом Гилритом, который оставил комментарий к моему посту в блоге. Суть этого алгоритма заключается в следующем: «Всё сделано из битов, поэтому, если мы можем сортировать биты — мы можем сортировать всё что угодно». Похожий образ мышления привёл меня к моему обобщению поразрядной сортировки. Большой минус рассмотрения всего в виде битов заключается в том, что это ведёт к созданию медленного алгоритма сортировки. В случае с 32-битными целыми числами нужно выполнить 31 рекурсивный вызов. Вот что получилось, когда я протестировал BinarSort на сортировке целых чисел.

Сразу бросается в глаза то, что BinarSort работает слишком медленно, как если бы его временная сложность была O(n log n). Причина этого в том же, в чём и причина того, что график ska_sort не выглядит как график алгоритма с настоящей временной сложностью O(n). Количество рекурсивных вызовов связано с количеством элементов. BinarSort приходится делать до 31 рекурсивного вызова. В тот момент, когда достигается такое количество вызовов, можно ожидать выравнивания графика, приближение его к горизонтальной линии. График алгоритма быстрой сортировки, используемого в std::sort, продолжил бы расти даже в таком случае. Но возникает такое ощущение, что для достижения такой области графика понадобятся огромные количества элементов. Вместо этого мы видим графическое представление работы алгоритма, который, чем больше рекурсивных вызовов делает, тем медленнее становится, никогда не добираясь до места, в котором его график превратился бы в подобие вертикальной линии.

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

Гораздо более многообещающий подход можно найти в этой публикации Фрица Хенглейна. Весь этот документ я не прочитал, но возникает такое впечатление, что автор сделал что-то очень похожее на то, что сделал я, за исключением того, что случилось это пять лет назад. В соответствии с его графиками оказывается, что его алгоритм тоже гораздо быстрее, чем более старые алгоритмы сортировки. Поэтому, полагаю, он проделал отличную работу, но по какой-то причине никто о ней не слышал. Урок, который из этого можно извлечь, заключается в том, что если занимаешься улучшением производительности алгоритмов — не надо делать этого на Haskell. Проблема, для начала, заключается в том, что сортировка в Haskell работает медленно. В результате автор сравнивает свой алгоритм с медленным алгоритмом сортировки. Такой алгоритм несложно обойти. Полагаю, его алгоритм был бы быстрее, чем std::sort, если бы он написал его на C++. Но точно этого сказать нельзя.

Vergesort

В комментариях мне встретилась одна приятная неожиданность. Дело в том, что пользователь Morwenn адаптировал свой алгоритм сортировки Vergesort таким образом, чтобы он работал бы поверх ska_sort. Получился алгоритм, который очень хорошо показывает себя на заранее отсортированных данных, но при этом быстро обрабатывает и последовательности, элементы которых перемешаны произвольным образом.

Выше показан опубликованный им график. Здесь ska_sort — это просто реализация моего алгоритма, а verge_sort — это комбинация исходного Vergesort и ska_sort. И что самое приятное — он опубликовал комментарий, где объяснил то, как он этого достиг.

В общем — фантастика. Я определённо попробую перенести его наработки в реализацию моего алгоритма. Возможно, даже есть способ объединить его цикл, проходящийся по данным, с моим первым циклом, в результате мне даже не понадобится делать дополнительный проход по данным.

Всё это приводит меня к планам на будущее.

Планы на будущее

Моя следующая задача — дать пользователям возможность подстраивать мою систему под свои нужды. Пока у меня нет полного решения этой задачи, но у меня есть кое-что, способное поддерживать сортировку ASCII-символов без учёта их регистра и умеющее правильно обрабатывать значения чисел, встречающихся в строках. Я надеюсь, что похожий подход можно использовать и при сортировке Unicode-символов. Идея заключается в том, что я даю пользователям механизм настройки моей системы, пользуясь которым, можно изменить то, как мой код использует итераторы в коллекциях. Можно изменить значение, возвращаемое из итератора, и то, как далеко продвигается итератор. Поэтому, для организации сортировки символов без учёта их регистра, можно просто вернуть из итератора символ a, в то время как реальным значением является A.

Сортировка строк с учётом имеющихся в них числовых значений — хитрая задача. Сейчас у меня есть идея, в соответствии с которой можно вернуть, вместо значения символьного типа, целочисленное значение, а затем продвинуть итератор на несколько позиций. Но с возвращаемым целым числом тоже нужно повозиться, так как надо вернуть либо символ, либо число. Я могу добавить в алгоритм поддержку std::variant (вероятно, мне это стоит сделать в любом случае), но можно просто решить, что при работе с символами мы просто приводим их к целочисленным значениям, а в случае с числами — возвращаем самое маленькое целочисленное значение плюс это число. То есть, например, для строки foo100 надо вернуть целочисленные значения, соответствующие символам f, o, o, а так же — INT_MIN+100. А для строки foo99 — целые числа для символов f, o, o, и INT_MIN+99. Затем, при обработке первых трёх значений, продвигаем итератор на один символ, при обработке числа 100 — на три символа, а при обработке числа 99 — на два. Тут есть один нетривиальный момент, который заключается в том, что итератор всегда надо продвигать на одно и то же число позиций в том случае, если элементы имеют одно и то же значение. То есть — если две разных строки содержат, по текущему индексу, значение INT_MIN+100, обе они должны продвинуть свои итераторы на три элемента. Нельзя, чтобы один из них прошёл бы четыре элемента. Я нуждаюсь в этом допущении, так как в рекурсивных вызовах мне понадобится увеличивать лишь один индекс. Поэтому я, на самом деле, не буду хранить итераторы, возвращаемые пользователем. Я буду хранить лишь единственный индекс, который могу использовать для всех значений, попавших в один и тот же раздел. Полагаю, это — многообещающая идея. Она может, кроме того, сработать на сортировке Unicode-символов, но это столь сложная тема, что я даже не знаю, сработает это вообще или нет. Полагаю, единственный способ это выяснить заключается в том, чтобы начать работу над этим и посмотреть, появятся ли при этом какие-то сложности.

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

Сейчас у меня есть одна большая проблема, которая заключается в том, что мне нужно от всего этого отдохнуть. Мне хочется на какое-то время оставить работу над этим алгоритмом сортировки. Я уже вроде как подустал от всего этого. Случилось это ещё до того, как я написал первый материал. К тому моменту я потратил на сортировку месяц свободного времени и, нажав на кнопку публикации материала, был несказанно счастлив от того, что всё это, наконец, закончилось. Поэтому, уж простите, но пока всё будет таким, как есть. Занимаюсь я этим в свободное время, и прямо сейчас есть другие дела, которым мне хотелось бы уделить внимание (Dark Souls III — это, скажу я вам, вещь).

Я планирую пользоваться моим алгоритмом на работе, и ожидаю, что это приведёт к внесению в него каких-то небольших улучшений. Когда начинаешь пользоваться чем-то для решения настоящих задач, это «что-то» всегда улучшается. Возможно, в этом году я ещё вернусь к теме сортировки.

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