Camaradas, buenas noches! Nos quitó la primera edición del libro "
C ++ 17 STL. Biblioteca de plantillas estándar " y continúa analizando la segunda, que finalmente decidimos presentar aquí un punto de vista alternativo. El autor del artículo de hoy es Ivan Čukić, quien también posee el libro
Functional Programming en C ++ , que se está preparando para su publicación en Manning Publishing House. Ofrecemos evaluar sus pensamientos, códigos y cálculos escépticos.
PreámbuloQuería nombrar esta publicación "Sobre la crueldad de los algoritmos STL" para probar mis propias habilidades para provocar clics. Pero luego decidió que era mejor escribir un artículo para el público objetivo, y no escribir una publicación en la que se reunieran aquellos que quisieran discutir sobre mis tesis atroces.
Por lo tanto, puedo suponer que está interesado en los algoritmos, su complejidad y desea escribir el código más perfecto.
AlgoritmosEn la comunidad profesional de C ++ moderna, a menudo se aconseja a las personas: hacer que su programa sea más seguro, más rápido, más expresivo, etc. - Utilice los algoritmos de la biblioteca estándar. También trato de popularizar este consejo en mis libros, discursos, seminarios ... siempre que haya una audiencia adecuada.
Por supuesto, es absolutamente cierto que si nos atrae escribir un bucle
for para resolver el problema que tenemos ante nosotros, primero debemos pensar si los algoritmos existentes de la biblioteca estándar (o boost) son adecuados para esto, y no actuar a ciegas.
Todavía necesitamos saber cómo se implementan estos algoritmos, qué requisitos y garantías están asociados con ellos, cuál es su complejidad espacial y temporal.
Por lo general, si nos enfrentamos a una tarea que cumple exactamente con los requisitos del algoritmo STL y se puede aplicar directamente, este algoritmo será la solución más efectiva.
Puede surgir un problema si necesitamos preparar los datos de alguna manera antes de aplicar el algoritmo.
Intersección de conjuntosSupongamos que estamos escribiendo una herramienta para desarrolladores de C ++ que daría consejos para reemplazar las opciones de captura predeterminadas (hablando de
[=] y
[&] ) en expresiones lambda, y mostraría explícitamente una lista de variables capturadas.
std::partition(begin(elements), end(elements), [=] (auto element) { ^~~ - - , [threshold] return element > threshold; });
Al analizar un archivo, necesitamos una colección que almacene variables de los ámbitos actuales y vecinos. Tan pronto como encontremos una expresión lambda con una captura predeterminada, necesitaremos ver qué variables se usan allí.
Como resultado, tenemos dos conjuntos: en uno habrá variables de las áreas de visibilidad circundantes, y en el otro habrá variables utilizadas en el cuerpo de la expresión lambda.
La lista de opciones de captura que vamos a ofrecer para el reemplazo debe ser la intersección de estos dos conjuntos (las expresiones lambda pueden usar variables globales que no necesitan ser capturadas, y no todas las variables del alcance circundante se usarán en la expresión lambda).
Y, si necesitamos intersección, entonces podemos usar el
std::set_intersection .
Este algoritmo es bastante hermoso en su simplicidad. Acepta dos colecciones ordenadas y las ejecuta simultáneamente de principio a fin:
- Si el elemento actual en la primera colección es igual al elemento actual en la segunda colección, se agrega al resultado, que el algoritmo simplemente mueve al siguiente elemento en ambas colecciones;
- Si el elemento real en la primera colección es menor que el elemento real en la segunda colección, entonces el algoritmo simplemente omite el elemento actual en la primera colección;
- Si el elemento real en la primera colección es más grande que el elemento real en la segunda colección, entonces el algoritmo simplemente omite el elemento actual en la segunda colección;
Se omite al menos un elemento (de la primera o segunda colección de entrada) en cada iteración; por lo tanto, la complejidad del algoritmo será lineal:
O(m + n) , donde
m es el número de elementos en la primera colección
n es el número de elementos en la segunda colección .
Simple y efectivo. Siempre que las colecciones de entrada estén ordenadas.
ClasificaciónAquí está el problema: ¿qué pasa si las colecciones no están ordenadas previamente?
En el ejemplo anterior, sería aconsejable almacenar variables del alcance circundante en una estructura tipo pila, donde el analizador podría simplemente agregar nuevos elementos que ingresen en un nuevo alcance y eliminar las variables del alcance actual tan pronto como se vaya.
Por lo tanto, las variables no se ordenarán por nombre, y no podremos usar directamente
std::set_intersection para operaciones en ellas. Del mismo modo, si realiza un seguimiento de las variables en el cuerpo de una expresión lambda, lo más probable es que no podamos guardarlas en forma ordenada.
Dado que
std::set_intersection solo funciona con colecciones ordenadas, en muchos proyectos se produce este principio: primero clasificamos las colecciones y luego llamamos al
std::set_intersection .
Si olvidamos que la clasificación de una pila de variables en nuestro ejemplo devalúa completamente el uso completo de la pila que definimos, el algoritmo de intersección para colecciones sin clasificar se verá así:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_1(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { std::sort(first1, last1); std::sort(first2, last2); return std::set_intersection(first1, last1, first2, last2, dest); }
¿Cuál es la complejidad de todo este algoritmo? La clasificación lleva un tiempo cuasilineal, por lo que la complejidad general de este enfoque es
O(n log n + m log m + n + m) .
Ordenar más pequeño¿Es posible hacerlo sin ordenar?
Si ambas colecciones no están ordenadas, entonces tendremos que dar la vuelta a la segunda colección para cada elemento del primero, para decidir si incluirla en el conjunto de resultados. Aunque este enfoque es bastante común en proyectos reales, es aún peor que el anterior: su complejidad es
O(n * m) .
En lugar de ordenar todo en una fila, o no ordenar nada, recuerde Zen y elija el Tercer Camino: clasificamos solo una colección.
Si solo se ordena una colección, entonces podemos iterar sobre todos los valores de los no clasificados uno por uno y para cada valor verificar si está en la colección ordenada. Para hacer esto, aplique una búsqueda binaria.
En este caso, la complejidad del tiempo será
O(n log n) para ordenar la primera colección y
O (m log n) para ordenar y verificar. La complejidad total será
O((n + m) log n) .
Si decidimos ordenar la segunda colección, y no la primera, entonces la complejidad sería
O((n + m) log m) .
Para lograr la máxima eficiencia, siempre clasificamos la colección en la que hay menos elementos, de modo que la complejidad final de nuestro algoritmo sea
((m + n) log (min(m, n)) .
La implementación se verá así:
template <typename InputIt1, typename InputIt2, typename OutputIt> auto unordered_intersection_2(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_2(first2, last2, first1, last1, dest); return; } std::sort(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return std::binary_search(first1, last1, FWD(value)); }); }
En nuestro ejemplo con listas de captura en expresiones lambda, la colección de variables presentes en la expresión lambda generalmente se ordena, ya que es probable que sea más pequeña que la colección de todas las variables de todos los ámbitos circundantes.
HashingLa última opción - para construir
std::unordered_set (puesta en práctica de un conjunto desordenado sobre la base de un hash) de una colección más pequeña, y clasificarlos. En este caso, la complejidad de las operaciones de búsqueda promediará
O(1) , pero llevará tiempo construir
std::unordered_set . La complejidad del edificio puede variar de
O(n) a
O(n*n) , y este es un problema potencial.
template <typename InputIt1, typename InputIt2, typename OutputIt> void unordered_intersection_3(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt dest) { const auto size1 = std::distance(first1, last1); const auto size2 = std::distance(first2, last2); if (size1 > size2) { unordered_intersection_3(first2, last2, first1, last1, dest); return; } std::unordered_set<int> test_set(first1, last1); return std::copy_if(first2, last2, dest, [&] (auto&& value) { return test_set.count(FWD(value)); }); }
El enfoque de hash gana por completo cuando necesita calcular las intersecciones de varios conjuntos con un único conjunto pequeño predefinido. Es decir, tenemos el conjunto
A , los conjuntos
B₁ ,
B₂… y queremos calcular
A ∩ B₁, A ∩ B₂…En este caso, puede ignorar la complejidad de la construcción
std::unordered_set , y la complejidad de calcular cada intersección será lineal -
O(m) , donde
m es el número de elementos en la segunda colección.
ControlPor supuesto, siempre es útil verificar la complejidad del algoritmo, pero en tales casos también es aconsejable verificar varios enfoques utilizando puntos de control. Especialmente al elegir entre las dos últimas opciones, donde comparamos búsquedas binarias y conjuntos basados en hash.
Mi prueba más simple mostró que la primera opción, donde tienes que ordenar ambas colecciones, es siempre la más lenta.
Ordenar una colección más pequeña supera
std::unordered_set poco a
std::unordered_set , pero no particularmente.
Tanto el segundo como el tercer enfoque son ligeramente más rápidos que el primero en el caso cuando ambas colecciones tienen el mismo número de elementos, y mucho más rápido (hasta seis veces) cuando el número de elementos en una colección es aproximadamente 1000 veces más que en el segundo.