En informática , la eficiencia algorítmica es una propiedad de un algoritmo que se relaciona con la cantidad de recursos computacionales utilizados por el algoritmo. Se debe analizar un algoritmo para determinar su uso de recursos y la eficiencia de un algoritmo se puede medir en función del uso de diferentes recursos. La eficiencia algorítmica puede considerarse análoga a la productividad de la ingeniería para un proceso repetitivo o continuo.
Para lograr la máxima eficiencia es deseable minimizar el uso de recursos. Sin embargo, diferentes recursos, como la complejidad del tiempo y el espacio , no se pueden comparar directamente, por lo que cuál de los dos algoritmos se considera más eficiente a menudo depende de qué medida de eficiencia se considera más importante.
Por ejemplo, bubble sort y timsort son algoritmos para ordenar una lista de elementos de menor a mayor. La clasificación de burbujas ordena la lista en el tiempo proporcional al número de elementos al cuadrado ( , ver notación O grande ), pero solo requiere una pequeña cantidad de memoria adicional que es constante con respecto a la longitud de la lista ( ). Timsort ordena la lista en tiempo linealítmico (proporcional a una cantidad multiplicada por su logaritmo) en la longitud de la lista ( ), pero tiene un requisito de espacio lineal en la longitud de la lista ( ). Si se deben ordenar listas grandes a alta velocidad para una aplicación determinada, timsort es una mejor opción; sin embargo, si es más importante minimizar la huella de memoria de la clasificación, la clasificación por burbujas es una mejor opción.
La importancia de la eficiencia con respecto al tiempo fue enfatizada por Ada Lovelace en 1843 aplicada a la máquina analítica mecánica de Charles Babbage :
"En casi todos los cálculos es posible una gran variedad de arreglos para la sucesión de los procesos, y varias consideraciones deben influir en las selecciones entre ellos para los propósitos de una máquina de cálculo. Un objetivo esencial es elegir aquel arreglo que tienda a reducirse a un mínimo del tiempo necesario para completar el cálculo" [1]
Las primeras computadoras electrónicas tenían velocidad limitada y memoria de acceso aleatorio limitada . Por lo tanto, se produjo una compensación espacio-temporal . Una tarea podría utilizar un algoritmo rápido que utilice mucha memoria, o podría utilizar un algoritmo lento que utilice poca memoria. La solución de ingeniería fue entonces utilizar el algoritmo más rápido que pudiera caber en la memoria disponible.
Las computadoras modernas son significativamente más rápidas que las primeras y tienen una cantidad mucho mayor de memoria disponible ( Gigabytes en lugar de Kilobytes ). Sin embargo, Donald Knuth destacó que la eficiencia sigue siendo una consideración importante:
"En las disciplinas de ingeniería establecidas, una mejora del 12%, que se obtiene fácilmente, nunca se considera marginal y creo que el mismo punto de vista debería prevalecer en la ingeniería de software" [2]
Un algoritmo se considera eficiente si su consumo de recursos, también conocido como costo computacional, está en un nivel aceptable o por debajo de él. En términos generales, "aceptable" significa: se ejecutará en una cantidad de tiempo o espacio razonable en una computadora disponible, generalmente en función del tamaño de la entrada. Desde la década de 1950, las computadoras han experimentado aumentos dramáticos tanto en la potencia computacional disponible como en la cantidad de memoria disponible, por lo que los niveles aceptables actuales habrían sido inaceptables incluso hace 10 años. De hecho, gracias a la duplicación aproximada de la potencia de las computadoras cada 2 años , las tareas que son aceptablemente eficientes en los teléfonos inteligentes y sistemas integrados modernos pueden haber sido inaceptablemente ineficientes para los servidores industriales hace 10 años.
Los fabricantes de ordenadores lanzan con frecuencia nuevos modelos, a menudo con mayor rendimiento . Los costos del software pueden ser bastante altos, por lo que en algunos casos la forma más sencilla y económica de obtener un mayor rendimiento podría ser simplemente comprar una computadora más rápida, siempre que sea compatible con una computadora existente.
Hay muchas formas de medir los recursos utilizados por un algoritmo: las dos medidas más comunes son la velocidad y el uso de memoria; otras medidas podrían incluir velocidad de transmisión, uso temporal del disco, uso del disco a largo plazo, consumo de energía, costo total de propiedad , tiempo de respuesta a estímulos externos, etc. Muchas de estas medidas dependen del tamaño de la entrada al algoritmo, es decir, la cantidad de datos a procesar. También podrían depender de la forma en que estén ordenados los datos; por ejemplo, algunos algoritmos de clasificación funcionan mal con datos que ya están ordenados o que están ordenados en orden inverso.
En la práctica, existen otros factores que pueden afectar la eficiencia de un algoritmo, como los requisitos de precisión y/o confiabilidad. Como se detalla a continuación, la forma en que se implementa un algoritmo también puede tener un efecto significativo en la eficiencia real, aunque muchos aspectos de esto se relacionan con cuestiones de optimización .
En el análisis teórico de algoritmos , la práctica normal es estimar su complejidad en sentido asintótico. La notación más comúnmente utilizada para describir el consumo de recursos o la "complejidad" es la notación O grande de Donald Knuth , que representa la complejidad de un algoritmo en función del tamaño de la entrada . La notación O grande es una medida asintótica de la complejidad de la función, donde aproximadamente significa que el requisito de tiempo para un algoritmo es proporcional a , omitiendo términos de orden inferior que contribuyen menos que al crecimiento de la función a medida que crece arbitrariamente . Esta estimación puede ser engañosa cuando es pequeña, pero generalmente es suficientemente precisa cuando es grande, ya que la notación es asintótica. Por ejemplo, la ordenación por burbujas puede ser más rápida que la ordenación por combinación cuando solo se van a ordenar unos pocos elementos; sin embargo, es probable que cualquiera de las implementaciones cumpla con los requisitos de rendimiento para una lista pequeña. Por lo general, los programadores están interesados en algoritmos que escalan eficientemente a tamaños de entrada grandes, y se prefiere la ordenación por fusión a la ordenación por burbujas para las listas de longitud que se encuentran en la mayoría de los programas con uso intensivo de datos.
Algunos ejemplos de notación Big O aplicada a la complejidad del tiempo asintótico de los algoritmos incluyen:
Para nuevas versiones de software o para proporcionar comparaciones con sistemas de la competencia, a veces se utilizan puntos de referencia , que ayudan a medir el rendimiento relativo de un algoritmo. Si se produce un nuevo algoritmo de clasificación , por ejemplo, se puede comparar con sus predecesores para garantizar que al menos sea eficiente como antes con datos conocidos, teniendo en cuenta cualquier mejora funcional. Los clientes pueden utilizar puntos de referencia al comparar varios productos de proveedores alternativos para estimar qué producto se adaptará mejor a sus requisitos específicos en términos de funcionalidad y rendimiento. Por ejemplo, en el mundo de los mainframes , ciertos productos patentados de compañías de software independientes, como Syncsort , compiten por la velocidad con productos de los principales proveedores, como IBM .
Algunos puntos de referencia brindan oportunidades para producir un análisis que compara la velocidad relativa de varios lenguajes compilados e interpretados, por ejemplo [3] [4] y The Computer Language Benchmarks Game compara el rendimiento de implementaciones de problemas de programación típicos en varios lenguajes de programación.
Incluso la creación de puntos de referencia " hágalo usted mismo " puede demostrar el rendimiento relativo de diferentes lenguajes de programación, utilizando una variedad de criterios especificados por el usuario. Esto es bastante simple, como lo demuestra con el ejemplo un "Resumen del desempeño en nueve idiomas" de Christopher W. Cowell-Shah. [5]
Los problemas de implementación también pueden tener un efecto en la eficiencia, como la elección del lenguaje de programación, o la forma en que se codifica realmente el algoritmo, [6] o la elección de un compilador para un lenguaje en particular, o las opciones de compilación utilizadas, o incluso el sistema operativo que se utiliza. En muchos casos, un lenguaje implementado por un intérprete puede ser mucho más lento que un lenguaje implementado por un compilador. [3] Consulte los artículos sobre compilación justo a tiempo y lenguajes interpretados .
Hay otros factores que pueden afectar cuestiones de tiempo o espacio, pero que pueden estar fuera del control de un programador; estos incluyen alineación de datos , granularidad de datos , localidad de caché , coherencia de caché , recolección de basura , paralelismo a nivel de instrucciones , subprocesos múltiples (ya sea a nivel de hardware o software), multitarea simultánea y llamadas a subrutinas . [7]
Algunos procesadores tienen capacidades de procesamiento vectorial , que permiten que una sola instrucción opere en múltiples operandos ; Puede que sea fácil o no para un programador o compilador utilizar estas capacidades. Es posible que sea necesario rediseñar completamente los algoritmos diseñados para el procesamiento secuencial para utilizar el procesamiento paralelo , o podrían reconfigurarse fácilmente. A medida que la informática paralela y distribuida gana importancia a finales de la década de 2010, se están realizando más inversiones en API eficientes de alto nivel para sistemas informáticos paralelos y distribuidos como CUDA , TensorFlow , Hadoop , OpenMP y MPI .
Otro problema que puede surgir en la programación es que los procesadores compatibles con el mismo conjunto de instrucciones (como x86-64 o ARM ) pueden implementar una instrucción de diferentes maneras, de modo que instrucciones que son relativamente rápidas en algunos modelos pueden ser relativamente lentas en otros modelos. . Esto a menudo presenta desafíos para la optimización de los compiladores , que deben tener una gran cantidad de conocimiento de la CPU específica y otro hardware disponible en el destino de la compilación para optimizar mejor el rendimiento de un programa. En el caso extremo, un compilador puede verse obligado a emular instrucciones que no son compatibles con una plataforma de destino de compilación, lo que le obliga a generar código o vincular una llamada de biblioteca externa para producir un resultado que de otro modo no sería computable en esa plataforma, incluso si es compatible de forma nativa. y más eficiente en hardware en otras plataformas. Este suele ser el caso en sistemas integrados con respecto a la aritmética de punto flotante , donde los microcontroladores pequeños y de baja potencia a menudo carecen de soporte de hardware para la aritmética de punto flotante y, por lo tanto, requieren rutinas de software computacionalmente costosas para producir cálculos de punto flotante.
Las medidas normalmente se expresan en función del tamaño de la entrada .
Las dos medidas más comunes son:
Para computadoras cuya energía es suministrada por una batería (por ejemplo, computadoras portátiles y teléfonos inteligentes ), o para cálculos muy largos/grandes (por ejemplo, supercomputadoras ), otras medidas de interés son:
A partir de 2018 [actualizar], el consumo de energía está creciendo como una métrica importante para tareas computacionales de todo tipo y en todas las escalas, desde dispositivos integrados de Internet de las cosas hasta dispositivos de sistema en chip y granjas de servidores . Esta tendencia suele denominarse informática verde .
En algunos casos también pueden ser relevantes medidas menos comunes de eficiencia computacional:
Analice el algoritmo, normalmente utilizando el análisis de complejidad del tiempo para obtener una estimación del tiempo de ejecución en función del tamaño de los datos de entrada. El resultado normalmente se expresa utilizando la notación O grande . Esto es útil para comparar algoritmos, especialmente cuando se va a procesar una gran cantidad de datos. Se necesitan estimaciones más detalladas para comparar el rendimiento del algoritmo cuando la cantidad de datos es pequeña, aunque es probable que esto sea de menos importancia. Los algoritmos que incluyen procesamiento paralelo pueden ser más difíciles de analizar .
Utilice un punto de referencia para cronometrar el uso de un algoritmo. Muchos lenguajes de programación tienen una función disponible que proporciona uso del tiempo de CPU . Para algoritmos de larga duración, el tiempo transcurrido también podría ser de interés. Por lo general, los resultados deben promediarse entre varias pruebas.
La creación de perfiles basada en ejecución puede ser muy sensible a la configuración del hardware y a la posibilidad de que otros programas o tareas se ejecuten al mismo tiempo en un entorno de multiprocesamiento y multiprogramación .
Este tipo de prueba también depende en gran medida de la selección de un lenguaje de programación, un compilador y las opciones del compilador en particular, por lo que todos los algoritmos que se comparan deben implementarse en las mismas condiciones.
Esta sección se ocupa del uso de los recursos de memoria ( registros , caché , RAM , memoria virtual , memoria secundaria ) mientras se ejecuta el algoritmo. En cuanto al análisis de tiempo anterior, analice el algoritmo, normalmente utilizando el análisis de complejidad espacial para obtener una estimación de la memoria de tiempo de ejecución necesaria en función del tamaño de los datos de entrada. El resultado normalmente se expresa utilizando la notación O grande .
Hay hasta cuatro aspectos del uso de la memoria a considerar:
Las primeras computadoras electrónicas y las primeras computadoras domésticas tenían cantidades relativamente pequeñas de memoria de trabajo. Por ejemplo, la calculadora automática de almacenamiento con retardo electrónico (EDSAC) de 1949 tenía una memoria de trabajo máxima de 1024 palabras de 17 bits, mientras que la Sinclair ZX80 de 1980 venía inicialmente con 1024 bytes de memoria de trabajo de 8 bits. A finales de la década de 2010, lo habitual es que las computadoras personales tengan entre 4 y 32 GB de RAM, un aumento de más de 300 millones de veces más memoria.
Las computadoras actuales pueden tener cantidades relativamente grandes de memoria (posiblemente Gigabytes), por lo que tener que comprimir un algoritmo en una cantidad limitada de memoria es un problema mucho menor de lo que solía ser. Pero la presencia de cuatro categorías diferentes de memoria puede ser significativa:
Un algoritmo cuyas necesidades de memoria quepan en la memoria caché será mucho más rápido que un algoritmo que quepa en la memoria principal, que a su vez será mucho más rápido que un algoritmo que tenga que recurrir a la memoria virtual. Debido a esto, las políticas de reemplazo de caché son extremadamente importantes para la informática de alto rendimiento, al igual que la programación con reconocimiento de caché y la alineación de datos . Para complicar aún más el problema, algunos sistemas tienen hasta tres niveles de memoria caché, con diferentes velocidades efectivas. Los diferentes sistemas tendrán diferentes cantidades de estos distintos tipos de memoria, por lo que el efecto de las necesidades de memoria del algoritmo puede variar mucho de un sistema a otro.
En los primeros días de la informática electrónica, si un algoritmo y sus datos no cabían en la memoria principal, entonces no se podía utilizar el algoritmo. Hoy en día el uso de memoria virtual parece proporcionar mucha memoria, pero a costa del rendimiento. Si un algoritmo y sus datos caben en la memoria caché, entonces se puede obtener una velocidad muy alta; en este caso minimizar el espacio también ayudará a minimizar el tiempo. A esto se le llama principio de localidad , y puede subdividirse en localidad de referencia , localidad espacial y localidad temporal . Un algoritmo que no quepa completamente en la memoria caché pero que muestre localidad de referencia puede funcionar razonablemente bien.
