Como otros han señalado, los algoritmos puros no son necesariamente específicos de un idioma. Pero, en el espíritu de la pregunta …
Primero, comenzaré con un fragmento de código del que estaba demasiado orgulloso: una implementación de árbol AVL que escribí en C para mi clase de estructuras de datos. Claro, la mayoría del algoritmo central siguió el libro de texto bastante de cerca. Pero, se nos pidió que descubrieramos cómo implementar una operación de eliminación nosotros mismos.
Fui más allá de los requisitos de la clase y escribí mi árbol AVL como un contenedor que podía contener estructuras de datos arbitrarias, y tomé un puntero de función para la función de comparación. También tenía funciones para caminar sobre todo el árbol, aplicar una operación a todos los nodos, o para eliminar el árbol sin eliminar los objetos (en caso de que los objetos se mantuvieran en más de una estructura, por ejemplo), y así sucesivamente. Estaba bastante orgulloso de su reutilización.
- ¿Cuál es la explicación intuitiva para agregar flujo en bordes inversos en el algoritmo de flujo máximo? ¿Por qué necesitamos eso?
- ¿Cuál es un ejemplo de un bucle infinito?
- ¿Cómo pueden uno y qué algoritmos podrían usarse para entrenar una red neuronal profunda con una cantidad limitada de datos desaprender sus representaciones mal aprendidas?
- ¿Alguien puede dar un ejemplo en Java de pasar una matriz unidimensional, una matriz bidimensional y una matriz tridimensional por referencia y luego manipularlos?
- ¿Cuáles son las mejores visualizaciones de algoritmos de aprendizaje automático?
Y así, lo reutilicé durante años para implementar tablas de símbolos y otros tipos de cosas. Todavía está en uso en un par de mis proyectos personales más de 20 años después. En retrospectiva, ¿es un gran código? Realmente no. Pero lo pensé en ese momento. Si hubiera estado usando C ++, podría haber obtenido todo eso y más, con un simple:
#include
Cue el trombón triste.
(Para ser justos, el STL no fue realmente una cosa popular en 1994. Pero, lo ha sido durante la mayoría de los últimos 23 años).
Bien, ¿qué pasa con algo más reciente / más impresionante?
Hace unos 10 años, me enfrenté a un interesante desafío de verificación de diseño: lanzamos una nueva generación de procesadores para nuestro DSP basado en caché hace aproximadamente un año. Los clientes comenzaron a notar que la memoria caché podría bloquear la actividad de DMA en el sistema durante largos períodos de tiempo en ciertos casos. La DMA luego pierde los plazos en tiempo real. En realidad, comenzaríamos a eliminar muestras del ADC, por ejemplo, lo cual es realmente malo.
La tarea que se me ocurrió fue simple de enunciar: escribir una serie de casos de prueba que desencadenarían varias combinaciones de aciertos y errores de caché (con y sin víctimas) en los cachés L1 y L2. Además de la diversión, teníamos RAM y caché en el nivel L2. Además, nuestros cachés no eran estrictamente inclusivos. Entonces, L1 podría tener una mezcla de datos de la memoria externa que se almacena en caché en L2, la memoria externa no se almacena en caché en L2 o la RAM L2.
Intenté escribir algunos de estos casos de prueba a mano, pero rápidamente descubrí que era tedioso y propenso a errores. Además, los escenarios de bloqueo de DMA parecían ser una función no solo del estado de la memoria caché, sino también del estado de la tubería L2 en cualquier momento dado. El espacio de estado para cubrir era enorme y no estaba bien definido.
Rápidamente me di por vencido escribiendo pruebas a mano, y escribí un modelo simple de una porción del caché en Perl. Si Perl Por segmento de la caché, me refiero a 2 conjuntos de caché en L1 y 1 conjunto en L2. Luego escribí un pequeño solucionador (también en Perl), para buscar iterativamente las secuencias del programa para encontrar secuencias de instrucciones mínimas que pondrían la tubería de caché L2 a través de un conjunto de estados únicos, en términos de una ventana de tiempo de 2 transacciones.
Este pequeño programa de Perl luego generó un buen conjunto de alrededor de 160 casos de prueba de código de ensamblaje (si la memoria funciona), y fue el primer conjunto de casos de prueba para demostrar la pérdida de rendimiento en tiempo real que no provino de uno de nuestros clientes.
Envalentonado por esa prueba de concepto, escribí una versión mucho más sofisticada en C que aumentó la ventana de transacciones examinadas en L2, y la variedad / complejidad de transacciones que intentó generar. Debido a que incrementé enormemente el espacio de estado que se estaba examinando, terminé necesitando una serie de enfoques inteligentes para generar una base de datos de prueba exhaustiva en un período de tiempo razonable:
- Una búsqueda de primer orden para examinar muchos casos de prueba potenciales en paralelo.
- Una cola de prioridad dinámica para calificar posibles casos de prueba de cuán fructíferos parecen ser (en términos de cubrir un nuevo espacio de estado).
- Un modelo de caché de alta fidelidad para modelar todas las transiciones de estado internas con precisión.
- Una función de ‘canonicalización de estado’ para reconocer cuándo dos estados de caché son efectivamente equivalentes entre sí.
- Una función de filtrado para evitar volver sobre los mismos espacios de estado y secuencias de transacciones repetidamente. Terminé redescubriendo los filtros de Bloom aquí.
El código resultante terminó generando una gran base de datos de unas 100 millones de líneas de código de ensamblaje divididas en ~ 14,000 casos de prueba. Esta base de datos de prueba dio a nuestros diseñadores ajustes durante unos meses, pero limpió de manera bastante efectiva nuestra tubería de caché. También condujo a casa cuán complejas pueden ser las pruebas de este tipo de tubería. En base a esa experiencia general, implementamos algunos cambios en la metodología de verificación de diseño bastante austeros para nuestra próxima generación de procesadores.
También me enganchó a dos generaciones más de ese generador de prueba, como una doble verificación de nuestros diseños. 🙂
¿Qué tal algo en C ++?
Hace aproximadamente 2 años, tuve la tarea de escribir un generador de prueba para un procesador VLIW. Sin embargo, lo que lo hace especial es que se parecía más a un compilador que a cualquier otra cosa. En lugar de proponer las pruebas en sí, implementó un lenguaje de restricción que permitió a los diseñadores escribir una serie de patrones de alto nivel dirigidos a alguna característica de hardware, y luego el generador de prueba necesitaba encontrar secuencias de código de ensamblaje válidas para que coincidan con esas restricciones. Y luego, una vez que encontró esas secuencias, tenía que programar opcionalmente las instrucciones para que coincida con la tubería VLIW.
Ah, y tenía que ser rápido . Estaba reemplazando una generación anterior de la misma herramienta que no se adaptaba a nuestras necesidades. La herramienta anterior a veces podría atascarse durante horas o días en ciertos conjuntos de restricciones de aspecto sencillo. Tomaría una mala decisión mientras buscaba una solución, y luego pasaría horas tropezando consigo mismo.
Para este, terminé aplicando una serie de técnicas interesantes. Usé un estilo de programación semifuncional para gran parte del código, lo que resulta ser sorprendentemente útil para este tipo de solucionador de restricciones. La mayoría de mis objetos de seguimiento de restricciones eran inmutables una vez creados. Si tuviera que encontrar la intersección de dos restricciones, es decir, [matemática] A \ cap B \ Rightarrow C [/ matemática], no modificaría ninguno de los objetos originales. Más bien, crearía un nuevo objeto para capturar la intersección y llevarlo hacia adelante. Esto hace que el retroceso sea muy sencillo de implementar: si alguna vez me vuelven a arrinconar, todavía tengo todos los objetos que representan el estado del que llegué.
Ahora podría estar pensando “¡Eso usaría una tonelada de RAM!” Y tendría razón. Pero, hay un par de trucos más bajo la manga.
Debido a que todos estos objetos son inmutables una vez creados, cualquier instancia de una restricción dada puede reemplazar a todas las demás instancias. Por ejemplo, si tengo la restricción “entero en el rango de 1 a 10”, solo necesito una instancia de ese objeto de restricción en toda la ejecución del programa, sin importar cuántas veces aparezca en el sistema de restricción. Entonces, el primer truco es aplicar un patrón de peso mosca a estos objetos. Almacene los objetos completos en una tabla en algún lugar y luego use enteros pequeños para referirse a ellos. Encajone los enteros en una clase de contenedor que reenvíe todo al objeto original y listo: ¡ Mucha memoria guardada!
Una vez que lo hubiera hecho, podría implementar el siguiente truco realmente bueno de manera eficiente: la memorización . Resulta que el número de producciones únicas [matemáticas] A \ cap B \ Rightarrow C [/ matemáticas] en una prueba dada es bastante limitado, por lo que una vez que lo ha calculado una vez, no necesita volver a calcularlo. Como [math] A [/ math] y [math] B [/ math] ya están convertidos en índices enteros, es muy sencillo crear un unordered_map en estos para buscar [math] C [/ math]. Eso cuesta un poco de memoria, pero realmente acelera las cosas.
Y luego está el solucionador recursivo en sí. Mantuve el sabor recursivo del original, pero implementé un par de técnicas para reducir drásticamente el espacio de búsqueda:
- Primero preescaneé todo el conjunto de restricciones buscando cualquier restricción que pudiera aplicar por adelantado, y lo usé para filtrar estáticamente las alternativas que examinaría en cada etapa de la recursión por adelantado. Esto a menudo redujo el espacio de búsqueda en órdenes de magnitud incluso antes de que comenzara la recursión.
- Calculé una tabla de saltos hacia atrás para permitir desenrollar varios niveles de recursión en los casos en que descubro tarde que una restricción dada no puede ser satisfecha. Simplificar demasiado un poco: si tengo alguna variable de restricción [matemáticas] X [/ matemáticas] que no se puede satisfacer en el paso 10, pero el último lugar [matemáticas] X [/ matemáticas] o cualquier cosa que pueda afectar a [matemáticas] X [ / math] apareció en el paso 5, es probable que no haya una buena razón para explorar opciones alternativas en los pasos 6 al 10. La tabla de backjump me permite relajarme de manera eficiente cuando eso sucede.
Otra estrategia que empleé fue la evaluación diferida. En cada paso de reducir las restricciones, mantuve una lista de alternativas que satisfacen las restricciones. Aplicar una restricción equivalía a filtrar entre alternativas. Evité reducir a código concreto el mayor tiempo posible.
Esto me permitió tomar las especificaciones de restricción originales y reducirlas a una forma resuelta que luego almacené en caché. Una vez que se resolvieron todas las restricciones en términos de alternativas válidas, el solucionador solo genera código directamente de las soluciones, escogiendo aleatoriamente entre las alternativas ya calculadas. No había necesidad de seguir resolviendo las mismas restricciones repetidamente.
El solucionador resultante funcionó extremadamente rápido, resolviendo algunos sistemas de restricción en milisegundos que anteriormente habían tomado horas. En lugar de obtener docenas de pruebas por día, podríamos generar 100s o 1000s de pruebas por hora, dependiendo de la complejidad. En algunos casos, podría generar hasta 1 millón de instrucciones por segundo (aunque es cierto que a menudo era mucho más lento que eso).
Ah, y debido a que fue escrito desde cero en C ++ 14, basándose en gran medida en contenedores estándar, RAII, punteros inteligentes, etc., esencialmente no tenía pérdidas de memoria. La new palabra clave solo apareció 5 veces en todo el programa, todo enfocado en lugares donde el código C ++ necesitaba interactuar con algún código C. La gran mayoría de las fallas de segmentación que experimenté durante el desarrollo también provienen de errores en las tablas estáticas que estaba generando fuera de línea para conducir el motor, en lugar de cualquier puntero colgante o problemas de por vida en el código central de C ++.
Estaba bastante orgulloso de ese código.
