cpp sort
1.16.0 — Taxonomics
Sería bueno si sólo uno o dos de los métodos de clasificación dominaran a todos los demás, independientemente de la aplicación o la computadora que se utilice. Pero, en realidad, cada método tiene sus propias virtudes peculiares. [...] Así encontramos que casi todos los algoritmos merecen ser recordados, ya que hay algunas aplicaciones en las que resultan mejores. — Donald Knuth, El arte de la programación informática, Volumen 3
cpp-sort es una biblioteca de clasificación genérica de solo encabezados de C++14. Gira en torno a una interfaz de clasificación genérica principal y proporciona varias herramientas pequeñas para seleccionar y/o diseñar algoritmos de clasificación. Usar sus funciones básicas de clasificación debería 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 proporciona un conjunto completo de funciones relacionadas con la clasificación. Estos son los principales componentes básicos de la biblioteca:
Aquí tienes un ejemplo más completo de lo que se puede hacer con la 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 ; }
));
}Incluso cuando las funciones de clasificación se utilizan sin funciones adicionales, siguen ofreciendo algunas garantías interesantes (ideas a menudo tomadas de Ranges TS):
iter_swap e iter_moveoperator()Puede leer más sobre todas las herramientas disponibles y encontrar algunos tutoriales sobre el uso y la extensión de cpp-sort en la wiki.
El siguiente gráfico se generó con un script que se encuentra en el directorio de pruebas comparativas. Muestra el tiempo necesario para que heap_sort ordene un millón de elementos sin adaptarse y luego, cuando se adapta con drop_merge_adapter o split_adapter .
Como se puede ver arriba, envolver heap_sort con cualquiera de los adaptadores lo hace adaptable a la cantidad de inversiones de una manera no intrusiva. Los algoritmos utilizados para adaptarlo tienen diferentes pros y contras, depende de ti utilizar cualquiera de ellos.
Este punto de referencia sirve principalmente para mostrar las posibilidades que ofrece la biblioteca. Puede encontrar más puntos de referencia comentados en la página wiki dedicada.
cpp-sort requiere compatibilidad con C++ 14 y debería funcionar con los siguientes compiladores:
/permissive- . Algunas funciones no están disponibles.Los compiladores enumerados anteriormente son los que utiliza la canalización de CI y la biblioteca también se prueba con las versiones más recientes de esos compiladores de forma regular. Todas las demás versiones intermedias del compilador no están probadas, pero también deberían funcionar. No dude en abrir un problema si no es el caso.
Las características de la biblioteca pueden diferir según la versión de C++ utilizada y las extensiones del compilador habilitadas. Esos cambios están documentados en la wiki.
El repositorio principal contiene soporte adicional para herramientas estándar como CMake o Conan. Puedes leer más sobre ellos en la wiki.
Tengo un auto nuevo. Sólo necesito armarlo. Son más fáciles de robar pieza por pieza. — Jarod Kintz, 3,33 dólares
Aunque algunas partes de la biblioteca son investigaciones originales y otras corresponden a implementaciones personalizadas y bastante ingenuas de algoritmos de clasificación estándar, cpp-sort también reutiliza una gran cantidad de código e ideas de proyectos de código abierto, a menudo modificados para integrarse perfectamente en el biblioteca. Aquí hay una lista de los recursos externos utilizados para crear esta biblioteca. Espero que las diferentes licencias sean compatibles. Si no es el caso, comuníquese conmigo (o envíe un problema) y veremos qué se puede hacer al respecto:
Algunos de los algoritmos utilizados por insertion_sorter y pdq_sorter provienen de la ordenación rápida que anula patrones de Orson Peters. Algunas partes de los puntos de referencia también provienen de ahí.
El algoritmo utilizado por tim_sorter proviene de la implementación de Timsort de Goro Fuji (gfx).
Los tres algoritmos utilizados por spread_sorter provienen del módulo Boost.Sort de Steven Ross.
El algoritmo utilizado por d_ary_spread_sorter proviene del módulo Boost.Heap de Tim Blechmann.
El algoritmo utilizado por spin_sorter proviene del algoritmo del mismo nombre implementado en Boost.Sort. Por Francisco José Tapia.
utility::as_function , utility::static_const y varios algoritmos auxiliares de proyección mejorada provienen de la biblioteca Range v3 de Eric Niebler. Varias ideas, como iteradores de proxy, puntos de personalización y proyecciones, así como algunas otras funciones de utilidad, también provienen de esa biblioteca o de artículos relacionados y propuestas estándar de C++.
El algoritmo utilizado por ska_sorter proviene de la implementación de Malte Skarupke de su propio algoritmo ska_sort.
El algoritmo utilizado por drop_merge_sorter proviene de la reimplementación en C++ de Adrian Wielgosik de la clasificación drop-merge de Emil Ernerfeldt.
Muchos algoritmos estándar mejorados se adaptan directamente de sus contrapartes en libc++, mejorados para manejar tanto proyecciones como iteradores proxy.
La biblioteca utiliza internamente una función inplace_merge que funciona con iteradores directos. Su implementación utiliza un algoritmo de fusión propuesto por Dudziński y Dydek, e implementado por Alexander Stepanov y Paul McJones en su libro Elements of Programming .
La sobrecarga inplace_merge para iteradores de acceso aleatorio utiliza el algoritmo Symmerge propuesto por Pok-Son Kim y Arne Kutzner en Fusión de almacenamiento mínimo estable mediante comparaciones simétricas cuando no hay suficiente memoria disponible para realizar una fusión fuera de lugar.
La implementación del smoothsort de Dijkstra utilizado por smooth_sorter ha sido adaptada directamente de la implementación del algoritmo de Keith Schwarz.
El algoritmo utilizado por wiki_sorter ha sido adaptado de WikiSort de BonzaiThePenguin.
El algoritmo utilizado por grail_sorter ha sido adaptado de GrailSort de Mrrl.
El algoritmo utilizado por indirect_adapter con iteradores directos o bidireccionales es una versión ligeramente modificada del indiesort de Matthew Bentley.
La implementación de la sobrecarga de acceso aleatorio de nth_element utilizada por algunos de los algoritmos proviene de la biblioteca miniselect de Danila Kutenin y utiliza el algoritmo AdaptiveQuickselect de Andrei Alexandrescu.
Todas las redes de clasificación utilizadas por sorting_network_sorter provienen de esta lista mantenida por Bert Dobbelaere. La página tiene referencias a las fuentes de todas las redes de clasificación que enumera.
Algunas de las optimizaciones utilizadas por sorting_network_sorter provienen de esta discusión en StackOverflow y están respaldadas por el artículo Aplicación de redes de clasificación para sintetizar bibliotecas de clasificación optimizadas .
El conjunto de pruebas vuelve a implementar algoritmos de números aleatorios que se encontraban originalmente en los siguientes lugares:
Los scripts LaTeX utilizados para dibujar las redes de clasificación son versiones modificadas de sortingnetwork.tex de kaayy, ligeramente adaptadas para estar basadas en 0 y dibujar la red de arriba a abajo.
Las herramientas CMake integradas en los proyectos incluyen scripts de RWTH-HPC/CMake-codecov y Crascit/DownloadProject.
Algunos de los puntos de referencia utilizan una paleta adaptada a los daltónicos desarrollada por Thøger Rivera-Thorsen.
