¿Cómo implementar algoritmos de clasificación clásicos en C++ moderno?

Bloques de construcción algorítmicos

Comenzamos ensamblando los componentes básicos algorítmicos de la Biblioteca estándar:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• Las herramientas de iteración como non-member std::begin()/ std::end()y with std::next()solo están disponibles a partir de C++ 11 y posteriores. Para C++98, es necesario escribirlos él mismo. Hay sustitutos de Boost.Range en boost::begin()/ boost::end()y de Boost.Utility en boost::next().
• el std::is_sortedalgoritmo solo está disponible para C++ 11 y versiones posteriores. Para C++98, esto se puede implementar en términos de std::adjacent_findun objeto de función escrito a mano. Boost.Algorithm también proporciona un boost::algorithm::is_sortedsustituto.
• el std::is_heapalgoritmo solo está disponible para C++ 11 y versiones posteriores.

Beneficios sintácticos

C++ 14 proporciona comparadores transparentes de la forma std::less<>que actúan polimórficamente sobre sus argumentos. Esto evita tener que proporcionar un tipo de iterador. Esto se puede usar en combinación con los argumentos de la plantilla de función predeterminada de C++ 11 para crear una sobrecarga única para ordenar algoritmos que toman <como comparación y aquellos que tienen un objeto de función de comparación definido por el usuario.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

En C++11, se puede definir un alias de plantilla reutilizable para extraer el tipo de valor de un iterador, lo que agrega un desorden menor a las firmas de los algoritmos de clasificación:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

En C++98, es necesario escribir dos sobrecargas y utilizar la typename xxx<yyy>::typesintaxis detallada.

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• Otra sutileza sintáctica es que C++ 14 facilita envolver comparadores definidos por el usuario a través de lambdas polimórficas (con autoparámetros que se deducen como argumentos de plantilla de función).
• C++ 11 solo tiene lambdas monomórficas, que requieren el uso del alias de plantilla anterior value_type_t.
• En C++98, es necesario escribir un objeto de función independiente o recurrir al tipo de sintaxis detallada std::bind1st// .std::bind2ndstd::not1
• Boost.Bind mejora esto con la sintaxis boost::bindy _1/ _2marcador de posición.
• C++ 11 y posteriores también tienen std::find_if_not, mientras que C++ 98 necesita std::find_ifun std::not1objeto de función alrededor.

Estilo C++

Todavía no existe un estilo C++ 14 generalmente aceptable. Para bien o para mal, sigo de cerca el borrador de Effective Modern C++ de Scott Meyers y el renovado GotW de Herb Sutter . Utilizo las siguientes recomendaciones de estilo:

• Las recomendaciones "Almost Always Auto" de Herb Sutter y "Preferir declaraciones automáticas a declaraciones de tipos específicos" de Scott Meyers , cuya brevedad es insuperable, aunque a veces se cuestiona su claridad .
• "Distinguir ()y {}al crear objetos" de Scott Meyers y elegir constantemente la inicialización entre llaves {}en lugar de la antigua inicialización entre paréntesis ()(para evitar todos los problemas de análisis más molestos en el código genérico).
• "Prefiera declaraciones de alias a typedefs" de Scott Meyers . Para las plantillas, esto es imprescindible de todos modos, y usarlo en todas partes ahorra typedeftiempo y agrega coherencia.
• Utilizo un for (auto it = first; it != last; ++it)patrón en algunos lugares para permitir la verificación invariante de bucle de subrangos ya ordenados. En el código de producción, el uso de while (first != last)y en ++firstalgún lugar dentro del bucle podría ser ligeramente mejor.

Orden de selección

La ordenación por selección no se adapta a los datos de ninguna manera, por lo que su tiempo de ejecución es siempreO(N²). Sin embargo, la clasificación por selección tiene la propiedad de minimizar el número de swaps . En aplicaciones donde el costo de intercambiar elementos es alto, la clasificación por selección puede ser el algoritmo elegido.

Para implementarlo usando la Biblioteca estándar, use repetidamente std::min_elementpara encontrar el elemento mínimo restante e iter_swapintercambiarlo en su lugar:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Tenga en cuenta que selection_sortel rango ya procesado está [first, it)ordenado como su invariante de bucle. Los requisitos mínimos son iteradores directos , en comparación con std::sortlos iteradores de acceso aleatorio.

Detalles omitidos :

• La clasificación de selección se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return;(o para iteradores directos/bidireccionales:) if (first == last || std::next(first) == last) return;.
• para iteradores bidireccionales , la prueba anterior se puede combinar con un bucle sobre el intervalo [first, std::prev(last)), porque se garantiza que el último elemento será el elemento mínimo restante y no requiere un intercambio.

Tipo de inserción

Aunque es uno de los algoritmos de clasificación elemental con O(N²)el peor de los casos, la clasificación por inserción es el algoritmo elegido cuando los datos están casi ordenados (porque es adaptativo ) o cuando el tamaño del problema es pequeño (porque tiene poca sobrecarga). Por estas razones, y porque también es estable , la ordenación por inserción se utiliza a menudo como caso base recursivo (cuando el tamaño del problema es pequeño) para algoritmos de ordenación de divide y vencerás con mayor sobrecarga, como la ordenación por fusión o la ordenación rápida.

Para implementar insertion_sortcon la Biblioteca estándar, use repetidamente std::upper_boundpara encontrar la ubicación donde debe ir el elemento actual y use std::rotatepara desplazar los elementos restantes hacia arriba en el rango de entrada:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Tenga en cuenta que insertion_sortel rango ya procesado está [first, it)ordenado como su invariante de bucle. La ordenación por inserción también funciona con iteradores directos.

Detalles omitidos :

• La clasificación por inserción se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return;(o para iteradores directos/bidireccionales:) if (first == last || std::next(first) == last) return;y un bucle sobre el intervalo [std::next(first), last), porque se garantiza que el primer elemento estará en su lugar y no requiere una rotación.
• para iteradores bidireccionales , la búsqueda binaria para encontrar el punto de inserción se puede reemplazar con una búsqueda lineal inversa utilizando el algoritmo de la biblioteca estándar std::find_if_not.

Cuatro ejemplos en vivo ( C++14 , C++11 , C++98 y Boost , C++98 ) para el siguiente fragmento:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• Para entradas aleatorias, esto proporciona O(N²)comparaciones, pero esto mejora a O(N)comparaciones para entradas casi ordenadas. La búsqueda binaria siempre utiliza O(N log N)comparaciones.
• Para rangos de entrada pequeños, la mejor localidad de memoria (caché, captación previa) de una búsqueda lineal también podría dominar una búsqueda binaria (se debe probar esto, por supuesto).

Ordenación rápida

Cuando se implementa cuidadosamente, la clasificación rápida es sólida y tiene O(N log N)la complejidad esperada, pero en O(N²)el peor de los casos la complejidad puede activarse con datos de entrada elegidos por el adversario. Cuando no se necesita una clasificación estable, la clasificación rápida es una excelente clasificación de uso general.

Incluso para las versiones más simples, la clasificación rápida es un poco más complicada de implementar utilizando la Biblioteca estándar que los otros algoritmos de clasificación clásicos. El siguiente enfoque utiliza algunas utilidades de iterador para ubicar el elemento medio del rango de entrada [first, last)como pivote, luego usa dos llamadas a std::partition(que son O(N)) para dividir en tres partes el rango de entrada en segmentos de elementos que son más pequeños que, iguales a, y mayor que el pivote seleccionado, respectivamente. Finalmente, los dos segmentos exteriores con elementos menores y mayores que el pivote se ordenan de forma recursiva:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

Sin embargo, es bastante complicado lograr que la clasificación rápida sea correcta y eficiente, ya que cada uno de los pasos anteriores debe verificarse y optimizarse cuidadosamente para el código de nivel de producción. En particular, por O(N log N)complejidad, el pivote tiene que dar como resultado una partición equilibrada de los datos de entrada, lo que no se puede garantizar en general para un O(1)pivote, pero sí se puede garantizar si se establece el pivote como la O(N)mediana del rango de entrada.

Detalles omitidos :

• la implementación anterior es particularmente vulnerable a entradas especiales, por ejemplo, tiene O(N^2)complejidad para la entrada " tubo de órgano1, 2, 3, ..., N/2, ... 3, 2, 1 " (porque el medio siempre es más grande que todos los demás elementos).
• La selección de pivote de mediana de 3 a partir de elementos elegidos aleatoriamente del rango de entrada protege contra entradas casi ordenadas cuya complejidad se deterioraría de otro modo hastaO(N^2).
• La partición de 3 vías (separar elementos más pequeños, iguales y más grandes que el pivote) como lo muestran las dos llamadas astd::partitionno es el algoritmo más eficienteO(N)para lograr este resultado.
• para iteradores de acceso aleatorio , O(N log N)se puede lograr una complejidad garantizada mediante la selección de pivote medio usando std::nth_element(first, middle, last), seguida de llamadas recursivas a quick_sort(first, middle, cmp)y quick_sort(middle, last, cmp).
• Sin embargo, esta garantía tiene un costo, porque el factor constante de la O(N)complejidad de std::nth_elementpuede ser más costoso que el de la O(1)complejidad de un pivote de mediana de 3 seguido de una O(N)llamada a std::partition(que es un paso hacia adelante único apto para caché). los datos).

Combinar ordenar

Si usar O(N)espacio adicional no es motivo de preocupación, entonces la ordenación por combinación es una excelente opción: es el único algoritmo de ordenación estable . O(N log N)

Es sencillo de implementar usando algoritmos estándar: use algunas utilidades de iterador para ubicar el medio del rango de entrada [first, last)y combine dos segmentos ordenados recursivamente con un std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

La ordenación por combinación requiere iteradores bidireccionales, siendo el cuello de botella el std::inplace_merge. Tenga en cuenta que al ordenar listas vinculadas, la ordenación por combinación solo requiere O(log N)espacio adicional (para recursividad). El último algoritmo se implementa std::list<T>::sorten la biblioteca estándar.

clasificación de montón

La clasificación en montón es sencilla de implementar, realiza unaO(N log N)clasificación in situ, pero no es estable.

El primer ciclo, O(N)fase "heapify", coloca la matriz en orden de montón. El segundo ciclo, la O(N log Nfase de "clasificación", extrae repetidamente el máximo y restaura el orden del montón. La biblioteca estándar hace que esto sea extremadamente sencillo:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

En caso de que consideres "hacer trampa" usar std::make_heapy std::sort_heap, puedes ir un nivel más profundo y escribir esas funciones tú mismo en términos de std::push_heapy std::pop_heap, respectivamente:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

La biblioteca estándar especifica tanto push_heapcomo pop_heapcomo complejidad O(log N). Sin embargo, tenga en cuenta que el bucle externo sobre el rango [first, last)genera O(N log N)complejidad para make_heap, mientras que std::make_heapsolo tiene O(N)complejidad. Por la O(N log N)complejidad general, heap_sortno importa.

Detalles omitidos : O(N)implementación demake_heap

Pruebas

Aquí hay cuatro ejemplos en vivo ( C++14 , C++11 , C++98 y Boost , C++98 ) que prueban los cinco algoritmos en una variedad de entradas (no pretenden ser exhaustivos ni rigurosos). Solo tenga en cuenta las enormes diferencias en el LOC: C++11/C++14 necesita alrededor de 130 LOC, C++98 y Boost 190 (+50%) y C++98 más de 270 (+100%).

Jul 09 '2014 09:07 TemplateRex