A veces escucho a la gente decir que debido a la velocidad de los procesadores y la cantidad de memoria disponible, la eficiencia del algoritmo y el tiempo de ejecución no son, en la práctica, una gran preocupación.
Pero imagino que todavía hay áreas donde tales consideraciones siguen siendo de suma importancia. Dos que vienen a la mente son el comercio algorítmico, donde se deben realizar miles de transacciones en fracciones de segundo, y la programación de sistemas integrados, donde la memoria y el poder a menudo son escasos. ¿Estoy en lo cierto acerca de estos ejemplos? ¿Y qué otras áreas también serían ejemplos?
algorithms
cocojambles
fuente
fuente
O(n*log(n))algoritmo terminará más rápido en una de 30 años que un equipoO(n!)oO(n*n)en un hardware más caro de hoy sines lo suficientemente grande.O(c * f(n))Donde la constantecse basa en la ineficiencia del hardware. Puede tener un sistema 1000 veces más rápido, ya quenhasta el infinito, importará cada vez menos. Elegiría un enO(10000 * log(n))lugar deO(n)cualquier día si sospecho quenpuede ser grande.Respuestas:
La velocidad siempre está en demanda. Supongo que tienes razón. Aquí hay algunos ejemplos donde se demandan algoritmos limpios:
Criptografía
Buscando grandes bases de datos
Ordenar y fusionar
Búsqueda de texto (no indexada), incluidos comodines
Problemas matemáticos con cálculos intensivos
Simulación
Aplicaciones de minería de datos
Animación
AI
Visión por computador
fuente
Hay algunos casos en los que el tiempo de ejecución del algoritmo podría no ser un gran problema, porque hemos llegado al punto de que simplemente puede atravesar un algoritmo de ejecución más larga con hardware más potente. Pero definitivamente hay algunos lugares donde las aceleraciones son esenciales.
En términos generales, cualquier cosa que use grandes conjuntos de datos será un problema. Cuando tienes algo que se escala mal con n, y luego haces un número realmente enorme, tienes un problema. Sospecho que si fue al sitio beta de Computational Science y examinó un poco, podría encontrar muchos problemas que necesitan algoritmos mejores y más rápidos. Algunas áreas con las que me he encontrado:
En términos generales, la computación científica generalmente parece ser un área donde la complejidad de lo que se está programando genera oportunidades para retrasos serios si su algoritmo es lento (muchos de ellos sufren de n muy grandes). Y, como mencionaste, hay aplicaciones financieras. Cuando milisegundos pueden determinar si usted gana o pierde dinero en una operación, los algoritmos "suficientemente buenos" no lo reducirán si hay algo mejor que se pueda hacer.
fuente
Tómelo con un grano de sal. Más potencia de cómputo básicamente significa que tu n puede ser mucho más grande antes de que disminuya significativamente. Para la mayoría de los problemas cotidianos, este n ahora es lo suficientemente grande como para que no necesite preocuparse. Sin embargo, aún debe conocer las complejidades de sus algoritmos.
Con más recursos disponibles, es posible que necesite procesar más datos más adelante. Hoy debe analizar un archivo de registro de 10 MB con 100.000 líneas. En un año, puede tener un archivo de registro de 100GB con 1,000,000,000 de líneas. Si la cantidad de datos crece más rápido que la potencia de los recursos, más tarde tendrá problemas.
Con más recursos disponibles, se apilan más capas entre sí. Sistema operativo, marco de sistema operativo, marco de terceros, intérprete de idiomas y finalmente su propia herramienta. Todas las ineficiencias innecesarias en las diferentes capas se multiplican. Mañana su herramienta puede ejecutarse en un nuevo sistema operativo con más campanas y silbatos, que a su vez consume más ciclos y más memoria, dejando menos para usted.
Por lo tanto, para responder a su pregunta, aún debe preocuparse por dónde se deben procesar cada vez más datos (se dan suficientes ejemplos en las otras respuestas) y dónde no proporciona la herramienta final, sino otra capa de abstracción para otras herramientas.
fuente
Hace unos años tuve que escribir un algoritmo que clasificara los tubos de ensayo dispuestos en
nbastidores en dos particiones distintas: es decir, un subconjunto de los tubos fueron "elegidos" y el resto fueron "no elegidos" y el resultado final sería que no había bastidor tendría un tubo 'elegido' y 'no elegido' (había algunos requisitos adicionales como la compresión). Cada estante contenía un máximo de 100 tubos.El algoritmo debía usarse para conducir un robot de clasificación de tubos en un laboratorio farmacéutico.
Cuando me dieron la especificación original, me asignaron aproximadamente 1 minuto de tiempo de cálculo para clasificar alrededor de 2000 tubos, ya que pensamos que la usabilidad no era demasiado dolorosa. Se requería que el número de movimientos fuera mínimo en todas las combinaciones posibles ya que el robot en sí era lento .
La suposición implícita era que la complejidad sería exponencial con el número de tubos. Sin embargo, mientras trabajaba en el diseño del algoritmo descubrí que hay un
O(n)algoritmo rápido en el que senencuentra el número de bastidores que realizaron una división óptima de los tubos. El resultado de eso fue que el tiempo de clasificación del algoritmo fue instantáneo, por lo que la pantalla de clasificación se actualizaría en tiempo real a medida que el usuario configurara su operación de clasificación.Para mí, la diferencia entre el usuario sentado durante un minuto después de cada cambio y tener una GUI de respuesta instantánea fue la diferencia entre una pieza de software que era funcionalmente suficiente y una pieza de software que fue un placer usar.
fuente
Otras áreas incluyen muchos tipos de procesamiento de señales en tiempo real, sistemas de control de retroalimentación, deconvolución de exploración de petróleo, compresión de video, trazado de rayos y renderizado de cuadros de películas, sistemas de realidad virtual, juegos donde la alta velocidad de cuadros puede ser una ventaja competitiva significativa, y teléfonos inteligentes y otros aplicaciones de dispositivos móviles, donde un gran número de ciclos de CPU consumirá la batería de los usuarios más rápido.
Estoy bastante sorprendido de que esta pregunta se haga, ya que para cualquier supercomputadora Top-500 jamás construida, es probable que haya una lista de espera de investigadores que puedan maximizarla y deseen magnitudes más potencia de cómputo o mejores algoritmos para resolver algún problema. (doble un poco de proteína para descifrar el cáncer, etc.) antes de retirarse.
fuente
Creo que los motores de búsqueda como Google y Bing son una de las áreas más grandes donde se utilizan algoritmos complejos y juegan un papel clave en acelerar los resultados con relevancia (clasificación de páginas) que brindan más utilidad a los usuarios.
fuente
La eficiencia del algoritmo no es una preocupación importante hoy en día porque estamos usando algoritmos eficientes. Si usara un algoritmo O (n!), Sería lento en cualquier tipo de hardware.
fuente
La complejidad del algoritmo es cada vez más importante a medida que aumenta la gran cantidad de datos. Afortunadamente, se incluyen soluciones genéricas eficientes para problemas de programación comunes (búsqueda y clasificación, principalmente) en casi todas las bibliotecas estándar de los lenguajes de programación modernos, por lo que normalmente, un programador no tiene que preocuparse demasiado por estas cosas. La desventaja es que muchos programadores no saben en absoluto lo que sucede debajo del capó y cuáles son las características de los algoritmos que utilizan.
Esto se vuelve especialmente problemático ya que muchas aplicaciones no están debidamente probadas: las personas escriben código que funciona bien para pequeños conjuntos de datos de prueba, pero cuando se enfrentan a unos miles de veces más de datos, el código se detiene. Algo que funciona bien para diez registros explota rápidamente cuando crece el conjunto de datos. Ejemplo del mundo real: un código que se suponía que debía limpiar elementos que ya no estaban vinculados a ninguna categoría utilizaba un bucle anidado de tres niveles, que es O (n ^ 3). Con solo 10 registros en la base de datos de prueba, esto significó 1000 comprobaciones, perfectamente factibles, y no introduce un retraso notable. Sin embargo, la base de datos de producción se llenó rápidamente con alrededor de 1000 filas, y de repente el código hace mil millones de cheques cada vez.
Entonces: No, no necesita conocer los entresijos de la implementación de todo tipo de algoritmos limpios, y no necesita poder inventar los suyos, pero sí necesita un conocimiento básico de algoritmos comunes, cuáles son sus los puntos fuertes y débiles son cuándo y cuándo no usarlos, y debe ser consciente del posible impacto de la complejidad algorítmica, para poder decidir qué nivel de complejidad es aceptable.
fuente
No se trata de qué dominios de aplicación son sensibles al tiempo de ejecución. Cualquier programa, en cualquier lugar, tiene un rendimiento mínimo por debajo del cual no tiene ningún valor. El punto de la complejidad del algoritmo es cómo varía al aumentar el tamaño de entrada. En otras palabras, las áreas donde la velocidad es particularmente importante son aquellas en las que espera tener que escalar más allá del tamaño del problema actual, sino también del orden de magnituddel tamaño de su problema actual. Si procesa las solicitudes de impuestos de los ciudadanos de un departamento de Francia, la tarea puede ser grande, pero no es probable que el tamaño de la población o la complejidad del procesamiento de un registro se incremente diez o cien veces, por lo que lo que funcione para usted ahora, probablemente seguirá trabajando. Pero si intenta crear algo que despegue en los volúmenes de Internet, la complejidad del algoritmo es clave: cualquier cosa que dependa más que linealmente o log-linealmente del tamaño de entrada se volverá mucho más costoso muy rápido, y eventualmente la velocidad del procesador simplemente no puede mantenerse al día con el crecimiento.
fuente
En mi campo (VFX, que cubre cosas como trazado de ruta, animación por computadora, simulación de partículas, dinámica de fluidos, procesamiento de imágenes, etc.), la complejidad algorítmica es fundamental. No hay forma de que algo que funcione en peor tiempo que el lineal lineal pueda esperar completarse en un tiempo razonable en entradas que comúnmente alcanzan millones de vértices, polígonos, vóxeles, partículas, texels, especialmente cuando muchas de estas cosas deben completarse muchas veces por segundo para proporcionar retroalimentación interactiva en tiempo real.
Dicho esto, no hay un fuerte énfasis en la complejidad algorítmica en la discusión, por lo general entre colegas, tal vez porque se da por sentado y es "rudimentario". Por lo general, se supone que si está escribiendo un trazado de ruta, va a operar en tiempo logarítmico o mejor, y que las estructuras de datos como las jerarquías de volumen límite son familiares y relativamente triviales de implementar para el lector. Incluso tuve un colega experto que seguía diciendo que los subprocesos múltiples y SIMD son más importantes que los algoritmos, y no creo que quisiera decir eso en el sentido de que se podría esperar sacar mucho provecho de la paralelización de un tipo de burbuja. Creo que dijo eso porque dio por sentado que aplicaríamos algoritmos sensibles,
A menudo, gran parte del enfoque en estos días es tomar muchos de estos algoritmos familiares y hacer que exploten mejor las características subyacentes del hardware, como el caché de la CPU, los registros e instrucciones SIMD, las GPU y los núcleos múltiples. Por ejemplo, a Intel se le ocurrió una forma novedosa de tomar el antiguo y conocido BVH e idear el concepto de "paquetes de rayos", básicamente probando múltiples rayos coherentes a la vez con un tipo recursivo de recorrido de árbol (que podría sonar así) Venía con su cuota de complejidad y gastos generales, excepto que está más que compensado por el hecho de que esos rayos ahora se pueden probar simultáneamente para las intersecciones de rayos / AABB y rayos / triángulos a través de las instrucciones y registros SIMD).
Algo similar con la subdivisión catmull-clark, que es algo muy rudimentario en los gráficos por computadora. Pero hoy en día lo que es competitivo, atractivo y súper eficiente son las implementaciones de GPU que se aproximan a la subdivisión CC utilizando parches Gregory, como popularizó Charles Loop y más tarde adoptó Pixar. La implementación más directa de la CPU ahora es bastante obsoleta, no necesariamente porque fue reemplazada en términos de complejidad algorítmica, sino porque fue reemplazada por algo que funciona bien con la GPU.
Y ese es generalmente un gran desafío en estos días: no encontrar el mejor algoritmo de una manera que sea relativamente independiente de las características subyacentes del hardware. De hecho, puse mi pie en la industria al crear una novedosa estructura de aceleración que aceleró significativamente la detección de colisiones para animar personajes y otros cuerpos blandos en los años 90 utilizando un enfoque de segmentación jerárquica en lugar de un índice espacial, lo que me dio una gran cantidad de ofertas de trabajo, pero en estos días ya no es tan impresionante ya que lo publiqué mucho antes de que tuviéramos cachés de CPU tan impresionantes y múltiples núcleos y GPU programables y qué no, y hoy en día uso un enfoque completamente diferente como resultado de los cambios significativos en el hardware subyacente
fuente
Una vez me encontré con un problema en el que un algoritmo generalmente se ejecutaba en O (n), pero en circunstancias raras y extremadamente improbables necesitaría tiempo O (n ^ 3): las circunstancias "raras" eran un directorio que contenía archivos con nombres que eran válidos en un sistema operativo pero no en otro.
Nadie nunca tuvo problemas. Luego, un cliente utilizó una estrategia para nombrar archivos que se ejecutarían sistemáticamente en el caso O (n ^ 3), y con unos 100 archivos, el sistema se detuvo virtualmente. El resultado fue que el algoritmo tuvo que ser cambiado.
fuente
Tres más que no se han mencionado:
1) Muchos juegos de estrategia en tiempo real. Mira aquellos que tienen unidades que no pueden compartir una posición. Observe lo que sucede con la búsqueda de caminos cuando un gran grupo de unidades se mueve a través de terreno restringido. Todavía tengo que encontrar un juego sin algún tipo de problema sustancial con esto porque simplemente no hay suficiente potencia de CPU disponible.
2) Muchos problemas de optimización. (Editar: desde que escribí esta respuesta, he tocado una. Mi objetivo era podar las rutas redundantes para dejar todos los nodos conectados con el peso mínimo de las rutas de conexión. Mi enfoque original funcionó bastante bien hasta que moví más podas para esa rutina, entonces me di cuenta de que era 2 ^ n. Ahora es n ^ 2, aunque a veces eso puede producir un resultado ligeramente no óptimo).
3) Cosas que deben operar en grandes cantidades de datos en tiempo real. Considere un DVD: por lo general, obtiene 2 horas de video en 4.7 gb. Considere un archivo de video típico con la misma resolución: esas 2 horas de video generalmente tendrán menos de 1 gb. La razón de esto es que cuando se establecieron las especificaciones de DVD, no se pudo hacer un reproductor de DVD a un precio razonable que pudiera decodificar los formatos más modernos lo suficientemente rápido.
fuente
Bueno, cualquier aplicación que normalmente se ejecuta en una supercomputadora ( lista de las máquinas más grandes ) califica. Estos son diversos, pero una gran subclase de ellos son las simulaciones físicas:
Estos son solo los temas principales de mi cabeza, pero solo lea la lista de las diferentes supercomputadoras y comprenda que todas y cada una de ellas están creadas para permitir algunos tipos de cálculos que no serían posibles sin estas máquinas gigantescas.
Y, una vez que vea que realmente necesitamos estas máquinas, comprenda cuántos costos se pueden ahorrar, simplemente acelerando estas aplicaciones en un 10% . Cualquier optimización de estos códigos aumenta directamente la cantidad de resultados que podemos obtener de estas máquinas.
fuente