Andrei Alexandrescu es una verdadera leyenda viviente. Esta es una persona que ha hecho una contribución significativa a la historia de los lenguajes de programación modernos y las técnicas generalizadas y de metaprogramación. Cuántas copias se rompieron en las discusiones
sobre el Diseño moderno C ++ y los
Estándares de codificación 101 (escritos con el Excepcional Escudo de armas C ++ de Sutter) y otros
libros y artículos . Como coautor
del lenguaje D , tuvo la oportunidad no solo de teorizar, sino también de hacer realidad su sueño y, lo que es típico, lo
encarnó .
Ahora tiene en sus manos un
informe de la conferencia DotNext 2018 Piter, que habla sobre las tecnologías modernas de optimización. ¿Qué tiene que ver .NET con él? Este es un informe fundamental de una persona que ha estado optimizando toda su vida. Si el rendimiento es importante para usted, debe verlo (o leer este artículo). ¡Bienvenido a cat!
El arte de la evaluación comparativa
Me gustaría discutir con usted varios temas relacionados con la evaluación comparativa. Para comenzar, repitamos algunas cosas básicas.
La ley de Amdahl es parte de los clásicos de la informática, se usa principalmente en la computación paralela, pero funciona en cualquier sistema complejo. Si queremos mejorar el trabajo de cierto sistema, entonces debemos comenzar donde se concentran los principales problemas de este sistema. La ley en sí es obvia: si un componente es el 20% del sistema, entonces la mejora máxima en el rendimiento del sistema que se puede lograr mediante la optimización de la operación de solo este componente es del 20%. Demasiado a menudo tengo que conocer personas (por supuesto, nuestros lectores no les pertenecen) que hacen cosas como optimizar el análisis de la línea de comandos. Estas operaciones toman los primeros 10 microsegundos de su programa, y las personas analizan su complejidad algorítmica y se horrorizan si el tiempo es cuadrático.
Como probablemente sepa, antes de comenzar la optimización, es necesario perfilar la aplicación y seleccionar puntos calientes en ella. Aquí debería decirse sobre la
ley de Ladma (este no es un apellido real, y Amdal, leído al revés). Debe concentrar sus esfuerzos en el componente que conduce a la mayor inversión de tiempo. Es necesario moverlo fuera de la aplicación, realizar el trabajo necesario, regresar y probar nuevamente. La razón por la que necesita hacer esto es porque muy a menudo una mejora del rendimiento del 20% es el resultado de diez mejoras del 2%. Y en el marco de un sistema grande, es imposible medir una mejora tan pequeña. Para esto, el componente debe probarse en un conjunto de pruebas. Una mejora del 20% en el rendimiento de uno de los componentes principales del sistema puede significar una mejora del 5% para el sistema en su conjunto, y para algunas áreas este es un excelente resultado. No olvide que las optimizaciones pueden tener una serie de efectos globales, por lo que, según los resultados de la evaluación comparativa selectiva, debe tener mucho cuidado al sacar conclusiones sobre el funcionamiento del sistema en su conjunto.
Un error que estoy seguro de que nuestros lectores no cometen, pero que generalmente es bastante común: las personas miden la velocidad de depuración del ensamblaje. Esto nunca debe hacerse. Esto es similar a estar molesto debido a la baja velocidad del caracol en las carreras: no está destinado a tal competencia, tiene otros objetivos en la vida. Otro error, algo menos obvio: las personas primero miden el rendimiento básico del sistema e inmediatamente después realizan una evaluación comparativa. Pero después de recopilar la línea de base, muchos recursos se calientan. Por ejemplo, los archivos abiertos se almacenan en el búfer y permanecen en la memoria (al menos en Linux). Por lo tanto, la segunda prueba será más rápida solo porque se inicia después de la primera. Esto sucede incluso con llamadas malloc. Después de estas llamadas, el sistema no vuelve a su estado original, incluso si se realizan llamadas de liberación de memoria. La configuración interna, el almacenamiento en caché y las características utilizadas por el asignador de memoria permiten que las siguientes llamadas malloc se ejecuten mucho más rápido. Incluso sin tener en cuenta el efecto de la memoria caché, Malloc recuerda que, por ejemplo, algunas funciones asignaron memoria para objetos de 4 kilobytes muchas veces, lo que significa que debe tener una lista libre con un tamaño de elemento de 4 kilobytes. O otro ejemplo: las búsquedas de DNS se almacenan en caché para su reutilización después de la primera consulta. Si es posible, durante la evaluación comparativa, debe reiniciar todo el proceso cada vez, de principio a fin.
Por ejemplo, para devolver completamente el sistema a su estado original, en el caso de los archivos, deben abrirse en un disco separado, que, después del final de la prueba, debe eliminarse (según tengo entendido, esto se puede hacer en Windows). La operación no es fácil, pero en la mayoría de los casos es necesaria.
Continuando con la conversación sobre los errores durante la optimización, tuve que lidiar con esos casos cuando los costos de printf se incluyen en los resultados de la prueba. Hay errores de procedimiento cuando se cambia más de una cosa antes de cada medición, lo que viola los principios más básicos de un experimento científico, ya que no está claro qué efecto está midiendo. Otro error grave es cuando se optimizan algunos casos raros, lo que conduce a la pesimismo en otras situaciones.
Aquí hay un ejemplo con Stack Overflow. El autor a menudo clasifica los datos ya ordenados y se sorprende, porque la función `is_sorted 'es obviamente mucho más rápida que` sort. ¿Por qué entonces en `sort the first line not is` if is_sorted return? Está optimizando un caso extremadamente raro, datos completamente ordenados, y todos los demás que tengan al menos un elemento no ordenado deberán asumir los costos de esta optimización. Esto no vale la pena hacerlo.
Creo que no tengo que demostrar durante mucho tiempo que las arquitecturas de la competencia actual son extremadamente complejas: cambio dinámico de frecuencia, interrupción por otros procesos, virtualización, etc. Por lo tanto, es casi imposible obtener el mismo tiempo al medir, sus indicadores siempre temblarán. Por lo tanto, uno no debe confiar en cosas que parecen obvias. Digamos que puede parecer obvio que menos instrucciones significan un código más rápido, y esto no siempre es cierto. También puede parecer que el uso de datos almacenados siempre será más rápido que volver a realizar los cálculos, por lo que si almacena los resultados en caché, estará bien. Como en el caso anterior, no se puede afirmar de manera inequívoca, al igual que lo contrario no se puede declarar incondicionalmente; todo depende del contexto. Obviamente, solo debe tener una cosa: todo debe medirse. Si mide todo, obtendrá mejores resultados que los expertos con conocimiento que no toman medidas.
Hay una serie de prácticas bastante confiables, cuya discusión puede llevarlo a pensamientos interesantes. Debemos comenzar con el hecho de que las matemáticas no te decepcionarán. Permite mostrar que los sistemas con diferentes velocidades pueden ser equivalentes. La matemática da reglas para mostrar la equivalencia de ciertas cosas e identificar algunas propiedades, y aunque no está sesgada, no importa qué cosas son interesantes y cuáles no. Muchas personas piensan que la optimización se basa en el conocimiento del código de máquina y el trabajo con bits, pero de hecho tiene muchas matemáticas, porque demuestra que un sistema más rápido es equivalente a uno más lento.
Otra regla general es que a las computadoras les encanta que las cosas sean aburridas. ¿Necesitas multiplicarnos por dos vectores, mil millones de elementos en cada uno? Esta es una tarea ideal para una computadora, todo el equipo que contiene está especialmente afilado para este tipo de tareas. Para analizar estos datos, basándome en ellos para construir una expresión regular, no quiero hacer esto. A las computadoras no les gustan cosas como ramas, dependencias, llamadas indirectas, en resumen: no les gusta el código inteligente, les gusta el código aburrido. A las computadoras no les gusta la grabación indirecta, un problema complejo que las personas involucradas en el hierro han estado luchando durante mucho tiempo y no pueden resolver.
Otra regla es que debe dar preferencia a las operaciones menos potentes, en otras palabras, prefiera la suma a la multiplicación y la multiplicación a la exponenciación. Nuevamente, las matemáticas son útiles aquí.
Finalmente, la última regla: cuanto más pequeña, más bella. El tamaño pequeño permite que las computadoras se den cuenta de sus ventajas, ya que prefieren que los datos, y especialmente las instrucciones, estén cerca unos de otros. Los resultados de varias mediciones de la velocidad de la aplicación siempre diferirán, tendrá una distribución de los resultados. Por lo general, solo tomamos el promedio de estos pocos resultados. Pero el problema es que, debido a las características específicas de las computadoras, el promedio incluirá mucho ruido. Cuando Bill Gates viaja en un autobús, en promedio, cada pasajero en un autobús es multimillonario. Suena genial, pero es poco confort para una persona sin hogar que viaja en el mismo autobús. Una situación similar ocurre con las interrupciones: la operación de multiplicación toma nanosegundos, pero cuando toma muchas mediciones de tales operaciones, una de ellas inevitablemente tendrá una interrupción de dos milisegundos. La diferencia es de tres órdenes de magnitud y, sin embargo, los desarrolladores no siempre tienen esto en cuenta.
Entonces, repito: el ruido en las computadoras siempre es aditivo; para las personas, puede parecer insignificante, pero para microbenchmarking es significativo, y la media aritmética incluirá mucho ruido. En lugar del promedio, necesita un indicador que mida solo el tiempo en el que puede influir de alguna manera. Si abordamos este tema desde el punto de vista de las matemáticas, veremos que necesitamos encontrar un valor que corresponda al mayor número de mediciones que hemos realizado. En otras palabras, necesitamos un mod. Esto nos lleva inmediatamente al problema: ¿qué sucede si tomas el mod de clasificación rápida? Si el algoritmo es probabilístico o si los datos son aleatorios, casi nunca habrá una moda. La densidad de valores será casi la misma en todo el espectro. En este caso, simplemente descartamos el 5% de las mediciones más grandes y luego tomamos el valor promedio, o el máximo, en el último caso tendremos un techo que no se excederá en el 95% de los casos. Casi siempre habrá un sujeto sentado en el viejo sótano con un módem lento, en el que cada página se cargará durante una hora. Puramente humanos, por supuesto, simpatizamos con él, pero técnicamente no podemos ayudar a todos, por lo tanto, el 5% restante de los casos tiene que ser descuidado. En general, al resolver problemas de red, a menudo nos centramos en el percentil 95, porque es imposible concentrarse en el centésimo. El percentil cien significará el resultado más lento de todas las mediciones recopiladas; esto no es informativo.
Reemplazar ramas con aritmética
Cómo, espero, quedó claro que la medición no es un problema fácil. Veamos algunos ejemplos y comencemos tratando de reemplazar la ramificación con aritmética. Estamos hablando de casos en los que necesitamos una declaración if, pero usarla con demasiada frecuencia no es deseable. En su lugar, integraremos el resultado de la rama como un valor 0/1. El código se verá lineal, la computadora solo tendrá que revisarlo de principio a fin, sin pensar en qué paso debe seguir a continuación.
Intentemos resolver el siguiente problema: transfiera los mínimos de cada cuartil de la matriz al primer cuartil. En otras palabras, la matriz se debe dividir en cuatro partes y el valor mínimo de cada parte se debe colocar al comienzo de la matriz.
static void min4(double[] p) { int n = p.Length; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < n / 4; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Arriba está el código básico. Por cierto, puedo anunciar con orgullo que traduje estos ejemplos a C # y que se compilaron con éxito. El código en sí es bastante simple: a `m se le asigna el índice del menor de los dos valores ubicados en los índices 'i y` j, y luego una asignación similar se repite dos veces más, dependiendo de los otros dos índices. Finalmente, el valor en el índice `m se invierte en la matriz con el valor en el índice` i. Como puede ver, omitimos la matriz usando cuatro variables inductivas.
El problema de probar dicho algoritmo será interesante y no obvio. Tendremos que probarlo no en un conjunto de datos, sino en datos que podrían surgir en varios casos. Por ejemplo, en datos que parecen tubos de un órgano: primero aumenta, luego disminuye; en datos aleatorios con una distribución uniforme; en un conjunto aleatorio de ceros y unos: a partir de datos aleatorios aquí, la diferencia es que habrá muchos valores duplicados; en datos ya ordenados; finalmente, sobre datos obtenidos por mediciones reales de algún fenómeno físico. Este será un enfoque serio para medir la velocidad de un algoritmo, y generalmente se acepta entre las personas que estudian algoritmos.
Intentemos mejorar el código que acabamos de conocer.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4; for (; i < q; ++i, ++j, ++k, ++l) { int m = p[i] <= p[j] ? i : j; if (p[k] < p[m]) m = k; if (p[l] < p[m]) m = l; Swap(ref p[i], ref p[m]); } }
Como primera optimización, intentaremos evitar la repetición excesiva de operaciones, para esto sacamos varias operaciones de división del bucle: dividiendo `n por 2 y 4 y dividiendo 3 *` n por 4. Pero después de esta optimización, descubrimos que los cálculos no eran para El problema principal es nosotros: el código no será más rápido, aunque será más compacto. En el mejor de los casos, lograremos una mejora del medio por ciento.
static void min4(double[] p) { int q = p.Length / 4; int i = 0, j = q, k = 2 * q, l = 3 * q; for (; i < q; ++i, ++j, ++k, ++l) { int m0 = p[i] <= p[j] ? i : j; int m1 = p[k] <= p[l] ? k : l; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
El segundo cambio que haremos al código es reducir las dependencias. En la versión anterior del algoritmo, la asignación de 'ma' k o 'l depende del valor asignado a la línea' m anterior. Para reducir el número de dependencias `m, calculamos por separado` m0 y` m1, y luego las comparamos. Cuando realicé esta optimización, esperaba una mejora significativa en la velocidad del algoritmo, pero al final resultó ser cero. Pero, en mi opinión, es importante mantener el número de dependencias al mínimo, por eso guardé el código.
static void min4(double[] p) { int q = p.Length / 4; for (int i = 0; i < q; ++i) { int m0 = p[i] <= p[i + q] ? i : i + q; int m1 = p[i + 2 * q] <= p[i + 3 * q] ? i + 2 * q : i + 3 * q; Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Intentemos ahora reducir el número de variables inductivas de cuatro a uno, y calcularemos las tres restantes aritméticamente, ya que están en relación constante entre sí. Esto es bastante simple: en lugar de `k, tendremos` i + q, en lugar de las otras dos variables:` i + 2 * q y` i + 3 * q. También tenía grandes esperanzas para esta optimización, pero, como la anterior, no dio ningún resultado a tiempo. Esto demuestra nuevamente la importancia de las mediciones: sin ellas podría presumir de haber mejorado significativamente el funcionamiento del algoritmo y tendría argumentos muy significativos.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2: ++i) { int m0 = p[i - q] < p[i] ? i - q : i; int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q; Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Como cuarto intento, reestructuramos el ciclo para deshacernos de la multiplicación por 3. Esto nos dará una mejora del 3%. El resultado aún no es impresionante. A continuación, intente deshacerse de los operadores ternarios.
Para hacer esto, me gustaría presentarle una nueva función: `static int opcional (bool flag, int value). Convierte el valor booleano de entrada en Int32, lo multiplica por -1 y lo pasa al operador AND a nivel de bits junto con el segundo valor de entrada. Si el indicador de entrada era falso, en int32 será 0, y después de todas las conversiones en la salida todavía obtendremos 0. Si el indicador de entrada fue verdadero, en int32 será 1, cuando se multiplica por -1 obtenemos FFFFFFFF, que después del bit "Y" con cualquier número dará este segundo número. Tenga en cuenta que no hay una declaración if en ningún lado, el código no tiene ramificación, es aburrido para una computadora (aunque nos parece complicado).
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = q; i < q2; ++i) { int m0 = i - optional(p[i - q] <= p[i], q); int m1 = i + q + optional(p[i + q2] < p[i + q], q); Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]); } }
Reemplazaremos a los operadores ternarios con esta función opcional, la integraremos dentro del cálculo. Lo aplicamos dos veces y, en el tercer caso, dejamos el signo de interrogación. Por lo tanto, en lugar de cuatro controles en este ciclo, solo tendré uno.
A partir de los resultados de medición que ve en la diapositiva, queda claro cuán importante era probar el algoritmo en varios conjuntos de datos diferentes. En un set no entenderíamos nada. En datos aleatorios y reales, tenemos una aceleración de más del doble, en tubos de órganos y datos ordenados, tenemos una ligera desaceleración. Esto se debe al hecho de que en el caso de los datos ordenados para el predictor de transición no habrá sorpresas, predecirá con una precisión del 100%. En el caso de los tubos de órganos, tendremos una predicción incorrecta en el medio del conjunto de datos; nuevamente, una precisión muy alta. En contraste, con datos aleatorios, la diferencia entre nuestros dos enfoques será enorme. Reemplazamos todos los cheques impredecibles con lógica simple. Aquí volvemos a una verdad simple: las computadoras están diseñadas para la informática, como su nombre lo indica (informática - informática). Ramificando, mostrando imágenes en la pantalla, todo esto se desempeña mucho peor. Realizar bit a bit "Y" para ellos es mucho más simple que pasar la instrucción if.
static void min4(double[] p) { int q = p.Length / 4, q2 = q + q; for (int i = 0; i < q; ++i) { int m = i + optional(p[i + q] < p[i], q); m += optional(p[i + q2] < p[m], q); m += optional(p[i + q2 + q] < p[m], q); Swap(ref p[i], ref p[m]); } }
Habiendo logrado finalmente un resultado positivo de la optimización, intentaremos reemplazar el último operador ternario con nuestra función `opcional. Esta vez la ganancia en velocidad será pequeña. Para entender por qué sucede esto, debe mirar el código generado. En la versión anterior del código, donde el signo de interrogación todavía estaba presente, el compilador ya encontró una manera de ejecutar el código sin bifurcación. Y cuando llega al operador ternario, ya podía predecirlo. Reemplazar esta última pieza con `opcional dará un código algo peor. Por lo tanto, repito, es importante tomar medidas cada vez.
Otra característica que me gustaría recomendarle es `ifelse sin ramas, que ahora ve en la pantalla. Es cierto que no pude lograr con él las mejoras de rendimiento en nuestro ejemplo. Si se le pasa 0 como bandera, la primera línea será 0; en el segundo, restamos 1 de 0 en Int32 y obtenemos FFFFFFFF, después de lo cual este valor se pasa al bit "Y" junto con el argumento de función `v2, que nos dará este argumento en sí mismo sin cambios; finalmente, la primera y la segunda línea se pasan al bit "OR", que nuevamente nos dará `v2. Si la bandera es 1, entonces la primera línea será igual a `v1; en el segundo, restamos 1 de 1 y obtenemos 0, como resultado de lo cual toda la línea será 0, y 0 y 'v1 en el bit' OR 'dará' v1.
Espero que dicha función `ifelse sin ramificación interese a las personas que están involucradas en el backend; por ahora, los compiladores modernos por alguna razón no utilizan este enfoque. Con estas funciones, puede reorganizar los algoritmos para que los compiladores los entiendan por usted, porque usted es más inteligente y creativo que su compilador.
Gran conjunto de intersección
Cambia un poco el tema de nuestra conversación y pasa a la intersección de grandes conjuntos. Hasta ahora, hemos estado hablando de operadores individuales, ahora crearemos nuevos algoritmos, por lo que tendremos que distraernos de los detalles y abrir nuestras mentes a una perspectiva más amplia. Supongo que está familiarizado con la ordenación por fusión, multiplique dos vectores y busque elementos comunes de dos vectores ordenados. Se atraviesan dos conjuntos ordenados, y cuando hay elementos iguales en ellos, esto se considera una coincidencia. Si uno de los dos elementos que se compara es más pequeño, cambia. Este algoritmo es bastante simple, pero muy común, probablemente el más utilizado en el mundo. Se utiliza en todas las consultas de varias palabras, cada consulta es la intersección de dos conjuntos. Este algoritmo, en particular, usa Google, y también debe aplicarse en todas las consultas de la base de datos.
int Intersect(double[] a1, double[] a2, double[] t) { if (a1.Length == 0 || a2.Length == 0) return 0; int i1 = 0, i2 = 0, i = 0; for (;;) if (a1[i1] < a2[i2]) { if (++i1 == a1.Length) break; } else if (a2[i2] < a1[i1]) { if (++i2 == a2.Length) break; } else { t[i++] = a1[i1]; if (++i1 == a1.Length || ++i2 == a2.Length) break: } return i; }
Eche un vistazo a la implementación básica de este algoritmo. Si ambos conjuntos de entrada están vacíos, entonces, obviamente, devolvemos 0. Luego, comenzamos un ciclo infinito, en el cual, si hay una coincidencia, aumentamos el resultado en 1 y verificamos si el ciclo debe completarse. En lugar de un bucle infinito, uno podría usar la instrucción for y especificar la condición para finalizar el bucle en ella. Pero eso significaría trabajo extra. En la implementación que ve en la diapositiva, en la primera rama tenemos `if (a1 [i1] <a2 [i2]), después de lo cual hay un aumento de` i1 en 1, y solo podemos verificar` i1. Del mismo modo, en la segunda rama solo necesitamos verificar `i2. Ambos valores deben verificarse solo en la tercera rama. Si esta verificación fuera al comienzo del ciclo, entonces haríamos el trabajo extra.
Intentemos mejorar esta implementación. Por el momento, su complejidad algorítmica es lineal, dependiendo de dos argumentos de entrada. En el aprendizaje automático, a menudo uno tiene que encontrar la intersección de conjuntos que son muy diferentes entre sí en tamaño o en estadísticas. Por ejemplo, tiene un vector de entrada largo y un vector de función corto con el que está comprobando. En nuestro código, puede haber un millón de registros en `a1 y mil en` a2. En este caso, no estamos listos para seguir un millón de pasos para completar este algoritmo. La mayor carga aquí estará en la siguiente línea de código: `if (++ i1 == a1.length) break. Justo antes de esto, se produce una comparación, y luego en esta línea hay un incremento del valor; esto, en esencia, es una búsqueda lineal. Realizamos iteraciones sobre un vector largo en busca de elementos de uno corto. En el peor de los casos, realizaremos muchas de estas búsquedas, moviéndonos lentamente a lo largo del vector.
Intentemos mejorar este algoritmo. Bueno, si no es una búsqueda lineal, entonces binario es mejor, ¿verdad? Usemos binario. Su ventaja es que da el índice del más grande de los elementos más pequeños.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, a1[i1]); if (m == a2.Length) continue; --m; if (!(a2[m] < a1[i1])) t[i++] = a1[i1]; } return i; }
El código anterior es una implementación de nuestro algoritmo de búsqueda binaria. Pero no es muy efectivo. La peor situación aquí será cuando la búsqueda binaria fallará cada vez. Y surgirá en escenarios bastante importantes, por ejemplo, cuando ambos conjuntos son idénticos. Usted, como un tonto, corta círculos con búsqueda binaria, mientras que solo tenía que pasar por el primer algoritmo lineal. ¿Por qué la búsqueda binaria, cuando el elemento deseado - cada vez aquí, el primero en la lista?
¿Cómo hacer que el algoritmo funcione con éxito en datos idénticos y diferentes? Verificar todos los datos será demasiado costoso para los recursos. Haré una reserva de que no se trata de datos completamente idénticos, sino de datos muy similares, con estadísticas similares, los tamaños también pueden variar. Puede consultar los siguientes elementos. La solución obvia es reducir su búsqueda. Cuando realizamos una búsqueda binaria, luego de haber encontrado algún elemento, ya no estamos interesados en elementos más pequeños, ya que el segundo vector también está ordenado. Por lo tanto, cada vez podemos reducir nuestra área de búsqueda, descartando todos los elementos menos del elemento encontrado.
int Intersect(double[] a1, double[] a2, double[] t) { int i1 = 0, i2 = 0, i = 0; for (; i1 != a1.Length; ++i1) { auto m = Bsearch(a2, i2, a2.Length, a1[i1]); if (m == i2) continue; if (!(a2[m - 1] < a1[i1])) t[i++] = a1[i1]; i2 = m + 1; } return i; }
Aquí está la implementación de este enfoque. Verá que realizamos una búsqueda binaria cada vez de una parte de la matriz original que comienza con `i2 y termina con` a2.length. Como `i2 aumentará con cada búsqueda, el área de búsqueda se reducirá.
La próxima optimización que me gustaría implementar aquí está relacionada con el algoritmo de búsqueda al galope. En esencia, esta es una búsqueda binaria con un paso diferente. En el caso de la búsqueda binaria, comenzamos cada vez desde el medio, pero pensemos que cuando buscamos un nombre en la guía telefónica, ¿no lo abrimos en el medio? Si el apellido de una persona comienza, digamos, en "B", abriremos el libro más cerca del principio. Este principio se implementa en una búsqueda galopante: comenzamos a rastrear los datos en la dirección ascendente con un paso que aumenta exponencialmente después de cada verificación: primero 1, luego 2, luego 4. Esto nos da una buena complejidad algorítmica. Si el paso creciera linealmente, la complejidad sería cuadrática. Cuando "saltamos" el elemento que estamos buscando, realizamos una búsqueda binaria normal en el segmento restante, que será pequeño y no afectará significativamente el tiempo de ejecución del algoritmo. Por lo tanto, combinamos todas las ventajas de ambos enfoques. Implementación de tal algoritmo:
int GBsearch(double[] a, int i, int j, double v) { for (int step = 1;; step *= 2) { if (i >= j) break; if (a[i] > v) break; if (i + step >= j) return Bsearch(a, i + 1, J, v); if (a[i + step] > v) return Bsearch(a, i + 1, i + step, v); i += step + 1; } return i; }
Ahora discutimos la escala, es decir, tratamos de encontrar la intersección de más de dos conjuntos. Para cada búsqueda de varias palabras, necesitaremos encontrar la intersección de varios conjuntos. Para hacer esto, podemos, por ejemplo, comparar los dos primeros conjuntos, luego su intersección con el tercero y así sucesivamente. Pero esta no es una solución óptima. Necesitamos tomar los primeros elementos de todos los conjuntos y encontrar el más pequeño de ellos, que luego será necesario mover. Necesitamos una estructura de datos que nos permita encontrar el más pequeño de los muchos elementos y que tenga una complejidad constante. Tal estructura de datos es un montón. Pero será un grupo extraño, no se basará en una matriz física. Será imaginario, organizaremos en él solo los primeros elementos de nuestros conjuntos. Una vez que encontramos el elemento más pequeño en el montón, aún podemos buscar todos los demás conjuntos.
Trabajar en los temas que estamos discutiendo en la práctica hoy tiene una forma bastante artesanal. En la práctica, a menudo tendremos varios conjuntos, no solo dos, y se ha escrito mucho sobre este tema. El algoritmo clásico aquí es SVS, en el que agrupamos los conjuntos, tomamos los dos más pequeños y elegimos el más corto como candidato.
Aquí puede encontrar una buena descripción general sobre este tema. Los problemas asociados con los conjuntos de intersección, el producto escalar de vectores dispersos, la ordenación por fusión, cualquier forma de comparación con la imagen a lo largo del tiempo son cada vez más interesantes. El algoritmo que te mostré se ha establecido como muy útil. Gracias por su atencion
Andrei Alexandrescu no vendrá a DotNext 2018 Moscú, pero Jeffrey Richter, Greg Young, Pavel Yosifovich y otros estarán allí. Los nombres de los oradores y los temas de los informes se pueden encontrar aquí , y las entradas aquí . Únete ahora!