cpp sort
1.16.0 — Taxonomics
Es wäre schön, wenn nur eine oder zwei der Sortiermethoden alle anderen dominieren würden, unabhängig von der Anwendung oder dem verwendeten Computer. Aber tatsächlich hat jede Methode ihre eigenen besonderen Vorzüge. [...] Daher stellen wir fest, dass fast alle Algorithmen es verdienen, in Erinnerung zu bleiben, da es einige Anwendungen gibt, in denen sie sich als die besten erweisen. — Donald Knuth, Die Kunst der Computerprogrammierung, Band 3
cpp-sort ist eine generische C++14-Header-Sortierbibliothek. Es dreht sich um eine generische Hauptsortierschnittstelle und bietet mehrere kleine Tools zum Auswählen und/oder Entwerfen von Sortieralgorithmen. Die Verwendung seiner grundlegenden Sortierfunktionen sollte trivial genug sein:
# 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 bietet einen vollständigen Satz sortierungsbezogener Funktionen. Hier sind die Hauptbausteine der Bibliothek:
Hier ist ein umfassenderes Beispiel dafür, was mit der Bibliothek gemacht werden kann:
# 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 ; }
));
}Selbst wenn die Sortierfunktionen ohne die zusätzlichen Funktionen verwendet werden, bieten sie dennoch einige interessante Garantien (Ideen, die häufig dem Ranges TS entnommen wurden):
iter_swap und iter_moveoperator() in einen Funktionszeiger umgewandelt werdenIm Wiki können Sie mehr über alle verfügbaren Tools lesen und einige Tutorials zur Verwendung und Erweiterung von cpp-sort finden.
Das folgende Diagramm wurde mit einem Skript aus dem Verzeichnis „Benchmarks“ erstellt. Es zeigt die Zeit an, die heap_sort benötigt, um eine Million Elemente ohne Anpassung zu sortieren, wenn es entweder mit drop_merge_adapter oder split_adapter angepasst wird.
Wie oben zu sehen ist, sorgt das Umschließen heap_sort mit einem der Adapter dafür, dass es sich auf nicht-intrusive Weise an die Anzahl der Inversionen anpasst . Die zur Anpassung verwendeten Algorithmen haben unterschiedliche Vor- und Nachteile. Es liegt an Ihnen, einen der beiden zu verwenden.
Dieser Benchmark dient hauptsächlich dazu, die Möglichkeiten aufzuzeigen, die die Bibliothek bietet. Weitere solcher kommentierten Benchmarks finden Sie auf der entsprechenden Wiki-Seite.
cpp-sort erfordert C++14-Unterstützung und sollte mit den folgenden Compilern funktionieren:
/permissive- . Einige Funktionen sind nicht verfügbar.Die oben aufgeführten Compiler werden von der CI-Pipeline verwendet, und die Bibliothek wird auch regelmäßig mit den neuesten Versionen dieser Compiler getestet. Alle anderen Compiler-Versionen dazwischen sind ungetestet, sollten aber auch funktionieren. Wenn dies nicht der Fall ist, können Sie gerne ein Problem eröffnen.
Die Funktionen in der Bibliothek können je nach verwendeter C++-Version und aktivierten Compiler-Erweiterungen unterschiedlich sein. Diese Änderungen sind im Wiki dokumentiert.
Das Haupt-Repository enthält zusätzliche Unterstützung für Standardtools wie CMake oder Conan. Mehr darüber können Sie im Wiki lesen.
Ich habe ein neues Auto bekommen. Ich muss es nur zusammensetzen. Sie lassen sich Stück für Stück leichter stehlen. – Jarod Kintz, 3,33 $
Obwohl es sich bei einigen Teilen der Bibliothek um Originalrecherchen handelt und andere benutzerdefinierten und eher naiven Implementierungen von Standard-Sortieralgorithmen entsprechen, verwendet cpp-sort auch einen großen Teil des Codes und der Ideen aus Open-Source-Projekten wieder, der oft geändert wurde, um sich nahtlos in die zu integrieren Bibliothek. Hier ist eine Liste der externen Ressourcen, die zum Erstellen dieser Bibliothek verwendet wurden. Ich hoffe, dass die vielen verschiedenen Lizenzen kompatibel sind. Wenn dies nicht der Fall ist, kontaktieren Sie mich bitte (oder reichen Sie ein Problem ein) und wir werden sehen, was wir dagegen tun können:
Einige der von insertion_sorter und pdq_sorter verwendeten Algorithmen stammen aus Orson Peters‘ Muster-besiegendem Quicksort. Auch einige Teile der Benchmarks stammen von dort.
Der von tim_sorter verwendete Algorithmus stammt aus Goro Fujis (gfx) Implementierung eines Timsort.
Die drei von spread_sorter verwendeten Algorithmen stammen aus dem Steven Ross Boost.Sort-Modul.
Der von d_ary_spread_sorter verwendete Algorithmus stammt aus dem Boost.Heap-Modul von Tim Blechmann.
Der von spin_sorter verwendete Algorithmus stammt aus dem gleichnamigen Algorithmus, der in Boost.Sort implementiert ist. von Francisco Jose Tapia.
utility::as_function , utility::static_const und mehrere projektionserweiterte Hilfsalgorithmen stammen aus der Range v3-Bibliothek von Eric Niebler. Mehrere Ideen wie Proxy-Iteratoren, Anpassungspunkte und Projektionen sowie einige andere Hilfsfunktionen stammen ebenfalls aus dieser Bibliothek oder den zugehörigen Artikeln und Standard-C++-Vorschlägen.
Der von ska_sorter verwendete Algorithmus stammt aus Malte Skarupkes Implementierung seines eigenen ska_sort-Algorithmus.
Der von drop_merge_sorter verwendete Algorithmus stammt aus einer C++-Neuimplementierung von Emil Ernerfeldts Drop-Merge-Sortierung durch Adrian Wielgosik.
Viele erweiterte Standardalgorithmen sind direkt von ihren Gegenstücken in libc++ adaptiert und so erweitert, dass sie sowohl Projektionen als auch Proxy-Iteratoren verarbeiten können.
Die Bibliothek verwendet intern eine inplace_merge -Funktion, die mit Forward-Iteratoren arbeitet. Seine Implementierung verwendet einen von Dudziński und Dydek vorgeschlagenen und von Alexander Stepanov und Paul McJones in ihrem Buch Elements of Programming implementierten Zusammenführungsalgorithmus.
Die inplace_merge Überladung für Iteratoren mit wahlfreiem Zugriff verwendet den von Pok-Son Kim und Arne Kutzner in „Stable Minimum Storage Merging by Symmetric Compares“ vorgeschlagenen Symmerge -Algorithmus, wenn nicht genügend Speicher für die Durchführung einer Out-of-Place-Zusammenführung verfügbar ist.
Die von smooth_sorter verwendete Implementierung von Dijkstras Smoothsort wurde direkt von Keith Schwarzs Implementierung des Algorithmus übernommen.
Der von wiki_sorter verwendete Algorithmus wurde von BonzaiThePenguins WikiSort übernommen.
Der von grail_sorter verwendete Algorithmus wurde von Mrrls GrailSort übernommen.
Der von indirect_adapter mit Vorwärts- oder bidirektionalen Iteratoren verwendete Algorithmus ist eine leicht modifizierte Version von Matthew Bentleys Indiesort.
Die Implementierung der Random-Access-Überladung von nth_element die von einigen der Algorithmen verwendet wird, stammt aus der Miniselect-Bibliothek von Danila Kutenin und verwendet den AdaptiveQuickselect -Algorithmus von Andrei Alexandrescu.
Die von sorting_network_sorter verwendeten Sortiernetzwerke stammen alle aus dieser von Bert Dobbelaere verwalteten Liste. Die Seite enthält Verweise auf die Quellen aller aufgeführten Sortiernetzwerke.
Einige der von sorting_network_sorter verwendeten Optimierungen stammen aus dieser Diskussion auf StackOverflow und werden durch den Artikel Applying Sorting Networks to Synthesize Optimized Sorting Libraries unterstützt.
Die Testsuite implementiert Zufallszahlenalgorithmen neu, die ursprünglich an folgenden Stellen zu finden waren:
Die LaTeX-Skripte, die zum Zeichnen der Sortiernetzwerke verwendet werden, sind modifizierte Versionen von kaayys sortingnetwork.tex , leicht angepasst, um 0-basiert zu sein und das Netzwerk von oben nach unten zu zeichnen.
Zu den in den Projekten eingebetteten CMake-Tools gehören Skripte von RWTH-HPC/CMake-codecov und Crascit/DownloadProject.
Einige der Benchmarks verwenden eine farbenblinde Palette, die von Thøger Rivera-Thorsen entwickelt wurde.
