A veces, solo tienes algoritmos que no pueden ser mejores que el tiempo lineal para los que todavía hay una fuerte demanda de rendimiento.
Un ejemplo es el procesamiento de video donde no se puede hacer que una imagen / cuadro sea más brillante como un ejemplo básico sin recorrer cada píxel (bueno, supongo que puede hacerlo con algún tipo de estructura jerárquica que indique las propiedades heredadas por los niños que finalmente descienden en mosaicos de imagen para nodos de hoja, pero luego diferiría un mayor costo de bucle a través de cada píxel al renderizador y el código probablemente sería más difícil de mantener que incluso el filtro de imagen más micro optimizado).
Hay muchos casos así en mi campo. Tiendo a hacer bucles de complejidad más lineal que tienen que tocar todo o leer todo lo que se beneficia de cualquier tipo de algoritmo o estructura de datos sofisticada. No hay trabajo que se pueda omitir cuando hay que tocar todo. Por lo tanto, en ese momento, si inevitablemente se trata de una complejidad lineal, debe hacer que el trabajo realizado por iteración sea más barato y más barato.
Entonces, en mi caso, las optimizaciones más importantes y comunes son a menudo representaciones de datos y diseños de memoria, subprocesos múltiples y SIMD (normalmente en este orden, siendo la representación de datos la más importante, ya que afecta la capacidad de hacer las dos últimas). No estoy teniendo tantos problemas que se resuelvan con árboles, tablas hash, algoritmos de clasificación y cosas de ese tipo. Mi código diario está más en la vena de, "para cada cosa, hacer algo".
Por supuesto, es otro caso para hablar sobre cuándo son necesarias las optimizaciones (y, lo que es más importante, cuando no lo son), micro o algorítmica. Pero en mi caso particular, si una ruta de ejecución crítica necesita optimización, las ganancias de velocidad 10x + a menudo se logran mediante optimizaciones de micro-nivel como multihilo, SIMD y reorganización de diseños de memoria y patrones de acceso para mejorar la localidad de referencia. No es tan frecuente que pueda, digamos, reemplazar un tipo de burbuja con un introsort o un tipo de radix o una detección de colisión de complejidad cuadrática con un BVH, tanto como encontrar puntos de acceso que, por ejemplo, se benefician de la división en campo frío / caliente. p>
Ahora, en mi caso, mi campo es tan crítico para el rendimiento (ráfaga de rayos, motores de física, etc.) que un rayo de rayos lento pero perfectamente correcto que demora 10 horas en renderizar una imagen a menudo se considera inútil o más rápido que uno completamente interactivo, pero produce las imágenes más feas con rayos que se filtran por todas partes debido a la falta de intersección de rayos / tri impermeable. Podría decirse que la velocidad es la principal medida de calidad de dicho software, incluso más que la corrección hasta cierto punto (ya que "corrección" es una idea difusa con el trazado de rayos ya que todo se aproxima, siempre que no se bloquee o algo así). Y cuando ese es el caso, si no pienso en la eficiencia por adelantado, tengo que cambiar el código en el nivel de diseño más caro para manejar diseños más eficientes. Entonces, si no pienso suficientemente en la eficiencia al momento de diseñar algo como un trazador de rayos o un motor de física, es probable que tenga que volver a escribir todo el maldito asunto antes de que pueda ser considerado lo suficientemente útil en producción y por los usuarios reales, no por los ingenieros.
El juego es otro campo similar al mío. No importa qué tan correcta sea la lógica de tu juego o qué tan fácil de mantener y brillante esté tu código base si tu juego se ejecuta a 1 cuadro por segundo como una presentación de diapositivas. En ciertos campos, la falta de velocidad podría inutilizar la aplicación a sus usuarios. A diferencia de los juegos, no hay una métrica "suficientemente buena" en áreas como el trazado de rayos. Los usuarios siempre quieren más velocidad, y la competencia industrial es predominantemente en la búsqueda de soluciones más rápidas. Nunca será lo suficientemente bueno hasta que sea en tiempo real, momento en el cual los juegos usarán trazadores de ruta. Y es probable que aún no sea lo suficientemente bueno para VFX, ya que los artistas podrían querer cargar miles de millones de polígonos y realizar simulaciones de partículas con autocolisión entre miles de millones de partículas a más de 30 FPS.
Ahora, si es de alguna comodidad, a pesar de eso, todavía escribo alrededor del 90% del código en un lenguaje de scripting (Lua) sin ninguna preocupación sobre el rendimiento en absoluto. Pero tengo una cantidad inusualmente grande de código que realmente necesita recorrer millones a miles de millones de cosas, y cuando lo haces de millones a miles de millones de cosas, empiezas a notar una diferencia épica entre el código ingenuo de un solo hilo que invoca una falla de caché con cada iteración frente a, digamos, un vector vectorizado que se ejecuta en paralelo y accede a bloques contiguos donde no se cargan datos irrelevantes en una línea de caché.