cpp sort
1.16.0 — Taxonomics
Было бы хорошо, если бы только один или два метода сортировки доминировали над всеми остальными, независимо от используемого приложения или компьютера. Но на самом деле каждый метод имеет свои особенности. [...] Таким образом, мы обнаруживаем, что почти все алгоритмы заслуживают того, чтобы их запомнили, поскольку в некоторых приложениях они оказываются лучшими. - Дональд Кнут, Искусство компьютерного программирования, Том 3.
cpp-sort — это универсальная библиотека сортировки только заголовков C++14. Он основан на одном основном универсальном интерфейсе сортировки и предоставляет несколько небольших инструментов для выбора и/или разработки алгоритмов сортировки. Использование основных функций сортировки должно быть достаточно тривиальным:
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}cpp-sort предоставляет полный набор функций, связанных с сортировкой. Вот основные строительные блоки библиотеки:
Вот более полный пример того, что можно сделать с библиотекой:
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}Даже когда функции сортировки используются без дополнительных функций, они все равно предоставляют некоторые интересные гарантии (идеи, часто взятые из Ranges TS):
iter_swap и iter_moveoperator()Вы можете прочитать больше обо всех доступных инструментах и найти несколько руководств по использованию и расширению cpp-sort в вики.
Следующий график был создан с помощью сценария, найденного в каталоге тестов. Он показывает время, необходимое для heap_sort для сортировки одного миллиона элементов без адаптации, а затем, когда он адаптируется с помощью drop_merge_adapter или split_adapter .
Как видно выше, упаковка heap_sort с помощью любого из адаптеров делает ее адаптивной к количеству инверсий ненавязчивым образом. Алгоритмы, используемые для его адаптации, имеют разные плюсы и минусы, использовать любой из них зависит от вас.
Этот тест в основном предназначен для демонстрации возможностей, предлагаемых библиотекой. Дополнительные тесты с комментариями вы можете найти на специальной вики-странице.
cpp-sort требует поддержки C++14 и должен работать со следующими компиляторами:
/permissive- . Некоторые функции недоступны.Перечисленные выше компиляторы используются в конвейере CI, и библиотека также регулярно тестируется с использованием самых последних версий этих компиляторов. Все остальные промежуточные версии компилятора не проверены, но также должны работать. Не стесняйтесь открыть проблему, если это не так.
Функции библиотеки могут различаться в зависимости от используемой версии C++ и включенных расширений компилятора. Эти изменения задокументированы в вики.
Основной репозиторий содержит дополнительную поддержку стандартных инструментов, таких как CMake или Conan. Подробнее о них можно прочитать в вики.
У меня новая машина. Мне просто нужно собрать это воедино. Их легче воровать по частям. — Джарод Кинц, 3,33 доллара.
Несмотря на то, что некоторые части библиотеки являются оригинальными исследованиями, а некоторые соответствуют пользовательским и довольно наивным реализациям стандартных алгоритмов сортировки, cpp-sort также повторно использует большое количество кода и идей из проектов с открытым исходным кодом, часто изменяемых для плавной интеграции в библиотека. Вот список внешних ресурсов, использованных для создания этой библиотеки. Я надеюсь, что многие различные лицензии совместимы. Если это не так, свяжитесь со мной (или сообщите о проблеме), и мы посмотрим, что можно с этим сделать:
Некоторые из алгоритмов, используемых в insertion_sorter и pdq_sorter взяты из быстрой сортировки Орсона Питерса, устраняющей шаблоны. Некоторые части тестов также взяты оттуда.
Алгоритм, используемый tim_sorter взят из реализации Timsort Горо Фудзи (gfx).
Три алгоритма spread_sorter взяты из модуля Стивена Росса Boost.Sort.
Алгоритм, используемый d_ary_spread_sorter взят из модуля Boost.Heap Тима Блехмана.
Алгоритм, используемый spin_sorter взят из одноименного алгоритма, реализованного в Boost.Sort. Франсиско Хосе Тапиа.
utility::as_function , utility::static_const и несколько вспомогательных алгоритмов с улучшенными проекциями взяты из библиотеки Эрика Ниблера Range v3. Некоторые идеи, такие как прокси-итераторы, точки настройки и проекции, а также несколько других служебных функций, также взяты из этой библиотеки или из связанных статей и стандартных предложений C++.
Алгоритм, используемый ska_sorter основан на реализации Малте Скарупке его собственного алгоритма ska_sort.
Алгоритм, используемый drop_merge_sorter , основан на C++-реализации Адриана Вельгосика сортировки слиянием Эмиля Эрнерфельдта.
Многие расширенные стандартные алгоритмы напрямую адаптированы из своих аналогов в libc++ и улучшены для работы как с проекциями, так и с прокси-итераторами.
Внутри библиотеки используется функция inplace_merge , которая работает с итераторами вперед. В его реализации используется алгоритм слияния, предложенный Дудзиньским и Дыдеком и реализованный Александром Степановым и Полом МакДжонсом в их книге «Элементы программирования» .
Перегрузка inplace_merge для итераторов с произвольным доступом использует алгоритм Symmerge, предложенный Пок-Соном Кимом и Арне Катцнером в статье «Слияние с минимальным объемом памяти при помощи симметричных сравнений» , когда недостаточно доступной памяти для выполнения слияния вне места.
Реализация Smoothsort Дейкстры, используемая smooth_sorter была напрямую адаптирована из реализации алгоритма Кейта Шварца.
Алгоритм, используемый wiki_sorter был адаптирован из WikiSort от BonzaiThePenguin.
Алгоритм, используемый grail_sorter был адаптирован из GrailSort компании Mrrl.
Алгоритм, используемый indirect_adapter с прямыми или двунаправленными итераторами, представляет собой слегка модифицированную версию индисорта Мэтью Бентли.
Реализация перегрузки nth_element с произвольным доступом, используемая некоторыми алгоритмами, взята из библиотеки miniselect Данилы Кутенина и использует алгоритм AdaptiveQuickselect Андрея Александреску.
Все сортировочные сети, используемые sorting_network_sorter взяты из этого списка, поддерживаемого Бертом Доббелером. На странице есть ссылки на источники всех перечисленных сортировочных сетей.
Некоторые оптимизации, используемые sorting_network_sorter взяты из этого обсуждения на StackOverflow и подкреплены статьей «Применение сетей сортировки для синтеза оптимизированных библиотек сортировки» .
Набор тестов переопределяет алгоритмы случайных чисел, первоначально найденные в следующих местах:
Скрипты LaTeX, используемые для рисования сетей сортировки, представляют собой модифицированные версии sortingnetwork.tex от kaayy, слегка адаптированные для отсчета от 0 и рисования сети сверху вниз.
Инструменты CMake, встроенные в проекты, включают сценарии из RWTH-HPC/CMake-codecov и Crascit/DownloadProject.
В некоторых тестах используется палитра, удобная для дальтоников, разработанная Тёгером Ривера-Торсеном.
