cpp sort
1.16.0 — Taxonomics
Ce serait bien si seulement une ou deux des méthodes de tri dominent toutes les autres, quelle que soit l'application ou l'ordinateur utilisé. Mais en fait, chaque méthode a ses propres vertus. [...] On constate ainsi que presque tous les algorithmes méritent d'être rappelés, puisqu'il existe certaines applications dans lesquelles ils s'avèrent les meilleurs. — Donald Knuth, L'art de la programmation informatique, volume 3
cpp-sort est une bibliothèque générique de tri d'en-têtes C++14 uniquement. Il s'articule autour d'une interface de tri générique principale et fournit plusieurs petits outils pour sélectionner et/ou concevoir des algorithmes de tri. Utiliser ses fonctionnalités de tri de base devrait être assez simple :
# 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 fournit un ensemble complet de fonctionnalités liées au tri. Voici les principaux éléments constitutifs de la bibliothèque :
Voici un exemple plus complet de ce qui peut être fait avec la bibliothèque :
# 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 ; }
));
}Même lorsque les fonctions de tri sont utilisées sans les fonctionnalités supplémentaires, elles offrent quand même des garanties intéressantes (idées souvent tirées des Gammes TS) :
iter_swap et iter_moveoperator()Vous pouvez en savoir plus sur tous les outils disponibles et trouver des tutoriels sur l'utilisation et l'extension de cpp-sort dans le wiki.
Le graphique suivant a été généré avec un script trouvé dans le répertoire benchmarks. Il montre le temps nécessaire à heap_sort pour trier un million d'éléments sans être adapté, puis lorsqu'il est adapté avec drop_merge_adapter ou split_adapter .
Comme on peut le voir ci-dessus, envelopper heap_sort avec l'un ou l'autre des adaptateurs le rend adaptatif au nombre d'inversions de manière non intrusive. Les algorithmes utilisés pour l’adapter ont des avantages et des inconvénients différents, c’est à vous d’utiliser l’un ou l’autre.
Ce benchmark est surtout là pour montrer les possibilités offertes par la bibliothèque. Vous pouvez trouver d’autres benchmarks commentés de ce type dans la page wiki dédiée.
cpp-sort nécessite la prise en charge de C++14 et devrait fonctionner avec les compilateurs suivants :
/permissive- . Certaines fonctionnalités ne sont pas disponibles.Les compilateurs répertoriés ci-dessus sont ceux utilisés par le pipeline CI, et la bibliothèque est également testée régulièrement avec les versions les plus récentes de ces compilateurs. Toutes les autres versions intermédiaires du compilateur n’ont pas été testées, mais devraient également fonctionner. N'hésitez pas à ouvrir un ticket si ce n'est pas le cas.
Les fonctionnalités de la bibliothèque peuvent différer selon la version C++ utilisée et les extensions du compilateur activées. Ces changements sont documentés dans le wiki.
Le référentiel principal contient une prise en charge supplémentaire pour les outils standard tels que CMake ou Conan. Vous pouvez en savoir plus à leur sujet sur le wiki.
J'ai une nouvelle voiture. J'ai juste besoin de le mettre en place. Ils sont plus faciles à voler pièce par pièce. — Jarod Kintz, 3,33 $
Même si certaines parties de la bibliothèque sont des recherches originales et d'autres correspondent à des implémentations personnalisées et plutôt naïves d'algorithmes de tri standard, cpp-sort réutilise également une grande partie du code et des idées de projets open source, souvent modifiés pour s'intégrer de manière transparente dans le bibliothèque. Voici une liste des ressources externes utilisées pour créer cette bibliothèque. J'espère que les nombreuses licences différentes sont compatibles. Si ce n'est pas le cas, contactez-moi (ou soumettez un problème) et nous verrons ce qui peut être fait :
Certains des algorithmes utilisés par insertion_sorter et pdq_sorter proviennent du tri rapide anti-modèle d'Orson Peters. Certaines parties des critères proviennent également de là.
L'algorithme utilisé par tim_sorter provient de l'implémentation par Goro Fuji (gfx) d'un Timsort.
Les trois algorithmes utilisés par spread_sorter proviennent du module Boost.Sort de Steven Ross.
L'algorithme utilisé par d_ary_spread_sorter provient du module Boost.Heap de Tim Blechmann.
L'algorithme utilisé par spin_sorter est issu de l'algorithme éponyme implémenté dans Boost.Sort. par Francisco José Tapia.
utility::as_function , utility::static_const et plusieurs algorithmes d'assistance améliorés par projection proviennent de la bibliothèque Range v3 d'Eric Niebler. Plusieurs idées telles que les itérateurs proxy, les points de personnalisation et les projections, ainsi que quelques autres fonctions utilitaires proviennent également de cette bibliothèque ou des articles associés et des propositions standard C++.
L'algorithme utilisé par ska_sorter provient de l'implémentation par Malte Skarupke de son propre algorithme ska_sort.
L'algorithme utilisé par drop_merge_sorter provient de la réimplémentation C++ d'Adrian Wielgosik du tri par fusion par dépôt d'Emil Ernerfeldt.
De nombreux algorithmes standards améliorés sont directement adaptés de leurs homologues de la libc++, améliorés pour gérer à la fois les projections et les itérateurs proxy.
La bibliothèque utilise en interne une fonction inplace_merge qui fonctionne avec les itérateurs forward. Son implémentation utilise un algorithme de fusion proposé par Dudziński et Dydek, et implémenté par Alexander Stepanov et Paul McJones dans leur livre Elements of Programming .
La surcharge inplace_merge pour les itérateurs à accès aléatoire utilise l'algorithme Symmerge proposé par Pok-Son Kim et Arne Kutzner dans Stable Minimum Storage Merging by Symmetric Comparisons lorsqu'il n'y a pas assez de mémoire disponible pour effectuer une fusion déplacée.
L'implémentation du smoothsort de Dijkstra utilisée par smooth_sorter a été directement adaptée de l'implémentation de l'algorithme par Keith Schwarz.
L'algorithme utilisé par wiki_sorter a été adapté du WikiSort de BonzaiThePenguin.
L'algorithme utilisé par grail_sorter a été adapté du GrailSort de Mrrl.
L'algorithme utilisé par indirect_adapter avec des itérateurs directs ou bidirectionnels est une version légèrement modifiée de l'indiesort de Matthew Bentley.
L'implémentation de la surcharge d'accès aléatoire de nth_element utilisée par certains algorithmes provient de la bibliothèque miniselect de Danila Kutenin et utilise l'algorithme AdaptiveQuickselect d'Andrei Alexandrescu.
Les réseaux de tri utilisés par sorting_network_sorter proviennent tous de cette liste entretenue par Bert Dobbelaere. La page contient des références aux sources de tous les réseaux de tri qu'elle répertorie.
Certaines des optimisations utilisées par sorting_network_sorter proviennent de cette discussion sur StackOverflow et sont étayées par l'article Applying Sorting Networks to Synthesize Optimized Sorting Libraries .
La suite de tests réimplémente les algorithmes de nombres aléatoires trouvés à l'origine aux endroits suivants :
Les scripts LaTeX utilisés pour dessiner les réseaux de tri sont des versions modifiées du sortingnetwork.tex de Kaayy, légèrement adaptés pour être basés sur 0 et dessiner le réseau de haut en bas.
Les outils CMake intégrés aux projets incluent des scripts de RWTH-HPC/CMake-codecov et Crascit/DownloadProject.
Certains tests utilisent une palette compatible avec les daltoniens développée par Thøger Rivera-Thorsen.
