cpp sort
1.16.0 — Taxonomics
Seria bom se apenas um ou dois métodos de classificação dominassem todos os outros, independentemente do aplicativo ou do computador usado. Mas, na verdade, cada método tem suas virtudes peculiares. [...] Assim descobrimos que quase todos os algoritmos merecem ser lembrados, pois há algumas aplicações em que eles se mostram melhores. - Donald Knuth, A Arte da Programação de Computadores, Volume 3
cpp-sort é uma biblioteca genérica de classificação somente de cabeçalho C++ 14. Ele gira em torno de uma interface de classificação genérica principal e fornece várias pequenas ferramentas para escolher e/ou projetar algoritmos de classificação. Usar seus recursos básicos de classificação deve ser bastante trivial:
# 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 fornece um conjunto completo de recursos relacionados à classificação. Aqui estão os principais blocos de construção da biblioteca:
Aqui está um exemplo mais completo do que pode ser feito com a biblioteca:
# 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 ; }
));
}Mesmo quando as funções de classificação são usadas sem os recursos extras, elas ainda fornecem algumas garantias interessantes (ideias frequentemente retiradas do Ranges TS):
iter_swap e iter_moveoperator()Você pode ler mais sobre todas as ferramentas disponíveis e encontrar alguns tutoriais sobre como usar e estender o cpp-sort no wiki.
O gráfico a seguir foi gerado com um script encontrado no diretório benchmarks. Ele mostra o tempo necessário para heap_sort classificar um milhão de elementos sem ser adaptado e, em seguida, quando é adaptado com drop_merge_adapter ou split_adapter .
Como pode ser visto acima, agrupar heap_sort com qualquer um dos adaptadores o torna adaptável ao número de inversões de maneira não intrusiva. Os algoritmos usados para adaptá-lo têm diferentes prós e contras, cabe a você usar qualquer um deles.
Este benchmark existe principalmente para mostrar as possibilidades oferecidas pela biblioteca. Você pode encontrar mais benchmarks comentados na página wiki dedicada.
cpp-sort requer suporte C++14 e deve funcionar com os seguintes compiladores:
/permissive- . Alguns recursos não estão disponíveis.Os compiladores listados acima são aqueles usados pelo pipeline de CI, e a biblioteca também é testada regularmente com as versões mais recentes desses compiladores. Todas as outras versões intermediárias do compilador não foram testadas, mas também devem funcionar. Sinta-se à vontade para abrir um problema se não for o caso.
Os recursos da biblioteca podem diferir dependendo da versão C++ usada e das extensões do compilador habilitadas. Essas mudanças estão documentadas no wiki.
O repositório principal contém suporte adicional para ferramentas padrão como CMake ou Conan. Você pode ler mais sobre eles no wiki.
Eu tenho um carro novo. Eu só preciso juntar tudo. Eles são mais fáceis de roubar pedaço por pedaço. - Jarod Kintz, $ 3,33
Embora algumas partes da biblioteca sejam pesquisas originais e outras correspondam a implementações personalizadas e bastante ingênuas de algoritmos de classificação padrão, o cpp-sort também reutiliza uma grande quantidade de código e ideias de projetos de código aberto, muitas vezes alterados para integrar-se perfeitamente ao biblioteca. Aqui está uma lista dos recursos externos usados para criar esta biblioteca. Espero que as muitas licenças diferentes sejam compatíveis. Se não for o caso, entre em contato comigo (ou envie um problema) e veremos o que pode ser feito a respeito:
Alguns dos algoritmos usados por insertion_sorter e pdq_sorter vêm do quicksort de Orson Peters, que derrota padrões. Algumas partes dos benchmarks também vêm daí.
O algoritmo usado por tim_sorter vem da implementação de um Timsort de Goro Fuji (gfx).
Os três algoritmos usados pelo spread_sorter vêm do módulo Steven Ross Boost.Sort.
O algoritmo usado por d_ary_spread_sorter vem do módulo Boost.Heap de Tim Blechmann.
O algoritmo usado por spin_sorter vem do algoritmo homônimo implementado em Boost.Sort. por Francisco José Tapia.
utility::as_function , utility::static_const e vários algoritmos auxiliares aprimorados por projeção vêm da biblioteca Range v3 de Eric Niebler. Várias ideias, como iteradores de proxy, pontos de customização e projeções, bem como algumas outras funções utilitárias também vêm dessa biblioteca ou dos artigos relacionados e propostas padrão do C++.
O algoritmo usado pelo ska_sorter vem da implementação de Malte Skarupke de seu próprio algoritmo ska_sort.
O algoritmo usado por drop_merge_sorter vem da reimplementação C++ de Adrian Wielgosik da classificação drop-merge de Emil Ernerfeldt.
Muitos algoritmos padrão aprimorados são adaptados diretamente de seus equivalentes em libc++, aprimorados para lidar com projeções e iteradores de proxy.
A biblioteca usa internamente uma função inplace_merge que funciona com iteradores de encaminhamento. Sua implementação utiliza um algoritmo de mesclagem proposto por Dudziński e Dydek, e implementado por Alexander Stepanov e Paul McJones em seu livro Elements of Programming .
A sobrecarga inplace_merge para iteradores de acesso aleatório usa o algoritmo Symmerge proposto por Pok-Son Kim e Arne Kutzner em Stable Mínimo Storage Merging by Symmetric Comparisons quando não há memória suficiente disponível para realizar uma mesclagem fora do local.
A implementação do smoothsort de Dijkstra usado por smooth_sorter foi adaptada diretamente da implementação do algoritmo de Keith Schwarz.
O algoritmo usado por wiki_sorter foi adaptado do WikiSort de BonzaiThePenguin.
O algoritmo usado por grail_sorter foi adaptado do GrailSort de Mrrl.
O algoritmo usado por indirect_adapter com iteradores diretos ou bidirecionais é uma versão ligeiramente modificada do indiesort de Matthew Bentley.
A implementação da sobrecarga de acesso aleatório de nth_element usada por alguns dos algoritmos vem da biblioteca miniselect de Danila Kutenin e usa o algoritmo AdaptiveQuickselect de Andrei Alexandrescu.
Todas as redes de classificação usadas por sorting_network_sorter vêm desta lista mantida por Bert Dobbelaere. A página contém referências às fontes de todas as redes de classificação listadas.
Algumas das otimizações usadas por sorting_network_sorter vêm desta discussão no StackOverflow e são apoiadas pelo artigo Aplicando redes de classificação para sintetizar bibliotecas de classificação otimizadas .
O conjunto de testes reimplementa algoritmos de números aleatórios originalmente encontrados nos seguintes locais:
Os scripts LaTeX usados para desenhar as redes de classificação são versões modificadas do sortingnetwork.tex de kaayy, ligeiramente adaptados para serem baseados em 0 e desenhar a rede de cima para baixo.
As ferramentas CMake incorporadas nos projetos incluem scripts de RWTH-HPC/CMake-codecov e Crascit/DownloadProject.
Alguns dos benchmarks usam uma paleta para daltônicos desenvolvida por Thøger Rivera-Thorsen.
