Eficiencia algorítmica

En informática , la eficiencia algorítmica es una propiedad de un algoritmo que se relaciona con la cantidad de recursos computacionales que utiliza. La eficiencia algorítmica puede considerarse análoga a la productividad de ingeniería para un proceso repetitivo o continuo.

Para lograr la máxima eficiencia, es conveniente minimizar el uso de recursos. Sin embargo, no es posible comparar directamente distintos recursos, como la complejidad temporal y espacial , 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, tanto el método de ordenación de burbuja como el de ordenación temporal son algoritmos para ordenar una lista de elementos del más pequeño al más grande. El método de ordenación de burbuja organiza la lista en un tiempo proporcional al número de elementos al cuadrado ( , consulte la notación Big O ), pero solo requiere una pequeña cantidad de memoria adicional que es constante con respecto a la longitud de la lista ( ). El método de ordenación temporal ordena la lista en un tiempo lineal (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, el método de ordenación temporal es una mejor opción; sin embargo, si es más importante minimizar la huella de memoria de la ordenación, el método de ordenación de burbuja es una mejor opción. ${\textstyle O(n^{2})}$${\textstyle O(1)}$${\textstyle O(n\log n)}$${\textstyle O(n)}$

La importancia de la eficiencia con respecto al tiempo fue enfatizada por Ada Lovelace en 1843 al aplicarla a la máquina analítica mecánica de Charles Babbage :

"En casi todos los cálculos es posible una gran variedad de disposiciones para la sucesión de los procesos, y diversas consideraciones deben influir en la selección de una de ellas para los fines de una máquina de cálculo. Un objetivo esencial es elegir aquella disposición que tienda a reducir al mínimo el tiempo necesario para completar el cálculo" ^[1]

Las primeras computadoras electrónicas tenían una velocidad y una memoria de acceso aleatorio limitadas . Por lo tanto, se producía un equilibrio entre el espacio y el tiempo . Una tarea podía utilizar un algoritmo rápido que utilizara mucha memoria, o podía utilizar un algoritmo lento que utilizara poca memoria. Por lo tanto, el equilibrio de ingeniería consistía en utilizar el algoritmo más rápido que pudiera caber en la memoria disponible.

Los ordenadores modernos son mucho más rápidos que los antiguos y tienen una cantidad de memoria disponible mucho mayor ( gigabytes en lugar de kilobytes ). Sin embargo, Donald Knuth destacó que la eficiencia sigue siendo un factor importante:

"En las disciplinas de ingeniería establecidas, una mejora del 12%, fácilmente obtenida, 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 razonable de tiempo o espacio 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 modernos y los sistemas integrados 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 un mayor rendimiento . Los costes de software pueden ser bastante elevados, por lo que en algunos casos la forma más sencilla y barata de conseguir un mayor rendimiento puede ser simplemente comprar un ordenador más rápido, siempre que sea compatible con un ordenador existente.

Existen 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 la velocidad de transmisión, el uso temporal del disco, el uso del disco a largo plazo, el consumo de energía, el costo total de propiedad , el 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 pueden depender de la forma en que se organizan los datos; por ejemplo, algunos algoritmos de ordenación funcionan mal con datos que ya están ordenados o que están ordenados en orden inverso.

En la práctica, hay 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 "complejidad" es la notación Big O de Donald Knuth , que representa la complejidad de un algoritmo como una función del tamaño de la entrada . La notación Big O 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 los términos de orden inferior que contribuyen menos que al crecimiento de la función a medida que crece arbitrariamente grande . Esta estimación puede ser engañosa cuando es pequeño, pero generalmente es suficientemente precisa cuando es grande ya que la notación es asintótica. Por ejemplo, la ordenación de burbuja puede ser más rápida que la ordenación por fusión cuando solo se deben ordenar unos pocos elementos; sin embargo, es probable que cualquiera de las dos implementaciones cumpla con los requisitos de rendimiento para una lista pequeña. Por lo general, los programadores están interesados ​​en algoritmos que se escalen de manera eficiente a tamaños de entrada grandes, y la ordenación por fusión se prefiere a la ordenación de burbuja para listas de la longitud que se encuentran en la mayoría de los programas con uso intensivo de datos. ${\textstyle n}$${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$${\displaystyle g(n)}$${\displaystyle g(n)}$${\textstyle n}$ ${\textstyle n}$${\textstyle n}$

Algunos ejemplos de notación Big O aplicados a la complejidad temporal asintótica de los algoritmos incluyen:

En el caso de las nuevas versiones de software o para ofrecer 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 crea un nuevo algoritmo de ordenación , por ejemplo, se puede comparar con sus predecesores para garantizar que, al menos, es tan eficiente como antes con los datos conocidos, teniendo en cuenta las mejoras funcionales. Los clientes pueden utilizar los 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 de ordenación patentados de empresas de software independientes, como Syncsort, compiten con productos de los principales proveedores, como IBM , por la velocidad.

Algunos puntos de referencia brindan oportunidades para producir un análisis que compare la velocidad relativa de varios lenguajes compilados e interpretados, por ejemplo, ^{[3] [4]} y The Computer Language Benchmarks Game compara el rendimiento de las implementaciones de problemas de programación típicos en varios lenguajes de programación.

Incluso la creación de pruebas comparativas " 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 demuestra con un ejemplo el "Resumen del rendimiento de nueve lenguajes" de Christopher W. Cowell-Shah. ^[5]

Los problemas de implementación también pueden tener un efecto sobre 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] Véanse los artículos sobre compilación justo a tiempo y lenguajes interpretados .

Hay otros factores que pueden afectar las cuestiones de tiempo o espacio, pero que pueden estar fuera del control de un programador; estos incluyen la alineación de datos , la granularidad de los datos , la localidad de caché , la coherencia de caché , la recolección de basura , el paralelismo a nivel de instrucción , el multihilo (ya sea a nivel de hardware o software), la multitarea simultánea y las 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. Los algoritmos diseñados para el procesamiento secuencial pueden necesitar ser rediseñados por completo para hacer uso del procesamiento paralelo , o podrían reconfigurarse fácilmente. A medida que la computación paralela y distribuida crece en importancia a fines de la década de 2010, se están realizando más inversiones en API de alto nivel eficientes para sistemas de computación paralela y distribuida 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 las instrucciones que son relativamente rápidas en algunos modelos pueden ser relativamente lentas en otros modelos. Esto a menudo presenta desafíos para optimizar los compiladores , que deben tener un amplio conocimiento de la CPU específica y otro hardware disponible en el destino de compilación para optimizar mejor un programa para el rendimiento. En el caso extremo, un compilador puede verse obligado a emular instrucciones no admitidas en una plataforma de destino de compilación, lo que lo obliga a generar código o vincular una llamada de biblioteca externa para producir un resultado que de otra manera sería incomputable 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 bajo consumo 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 . ${\displaystyle \scriptstyle {n}}$

Las dos medidas más comunes son:

• Tiempo : ¿cuánto tiempo tarda en completarse el algoritmo?
• Espacio : ¿Cuánta memoria de trabajo (normalmente RAM) necesita el algoritmo? Esto tiene dos aspectos: la cantidad de memoria que necesita el código (uso de espacio auxiliar) y la cantidad de memoria necesaria para los datos sobre los que opera el código (uso de espacio intrínseco).

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:

• Consumo directo de energía : energía necesaria directamente para operar el ordenador.
• Consumo indirecto de energía : energía necesaria para refrigeración, iluminación, etc.

A partir de 2018 ^[update], el consumo de energía se ha convertido en 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 se conoce a menudo como computación verde .

Medidas menos comunes de eficiencia computacional también pueden ser relevantes en algunos casos:

• Tamaño de transmisión : el ancho de banda puede ser un factor limitante. La compresión de datos se puede utilizar para reducir la cantidad de datos que se van a transmitir. Mostrar una imagen (por ejemplo, el logotipo de Google ) puede dar como resultado la transmisión de decenas de miles de bytes (48 K en este caso) en comparación con la transmisión de seis bytes para el texto "Google". Esto es importante para las tareas informáticas limitadas por E/S .
• Espacio externo : espacio necesario en un disco u otro dispositivo de memoria externa; podría ser para almacenamiento temporal mientras se ejecuta el algoritmo, o podría ser un almacenamiento a largo plazo necesario para futuras referencias.
• Tiempo de respuesta ( latencia ): esto es particularmente relevante en una aplicación en tiempo real cuando el sistema informático debe responder rápidamente a algún evento externo .
• Coste total de propiedad : especialmente si una computadora está dedicada a un algoritmo particular.

El análisis de algoritmos , que normalmente utiliza conceptos como la complejidad temporal , se puede utilizar 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 Big O. Esto es útil para comparar algoritmos, especialmente cuando se debe 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 menor importancia. Los algoritmos paralelos pueden ser más difíciles de analizar .

Se puede utilizar un punto de referencia para evaluar el rendimiento de un algoritmo en la práctica. Muchos lenguajes de programación tienen una función disponible que proporciona el uso del tiempo de CPU . En el caso de algoritmos de larga duración, el tiempo transcurrido también puede ser de interés. Por lo general, los resultados deben promediarse a lo largo de 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 particular, un compilador y las opciones del compilador, por lo que los algoritmos que se comparan deben implementarse todos 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. Al igual que en el análisis de tiempo anterior, se analiza el algoritmo, generalmente mediante 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 mediante la notación Big O.

Hay hasta cuatro aspectos del uso de la memoria a tener en cuenta:

• La cantidad de memoria necesaria para almacenar el código del algoritmo.
• La cantidad de memoria necesaria para los datos de entrada .
• La cantidad de memoria necesaria para cualquier dato de salida .
  • Algunos algoritmos, como el de ordenación, suelen reorganizar los datos de entrada y no necesitan espacio adicional para los datos de salida. Esta propiedad se denomina operación " in situ ".
• La cantidad de memoria necesaria como espacio de trabajo durante el cálculo.
  • Esto incluye variables locales y cualquier espacio de pila necesario para las rutinas llamadas durante un cálculo; este espacio de pila puede ser significativo para los algoritmos que utilizan técnicas recursivas .

Los primeros ordenadores electrónicos y los primeros ordenadores domésticos 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 8 bits de memoria de trabajo. A finales de la década de 2010, lo habitual es que los ordenadores personales tengan entre 4 y 32 GB de RAM, lo que supone un aumento de más de 300 millones de veces la cantidad de memoria.

Las computadoras modernas pueden tener cantidades relativamente grandes de memoria (posiblemente gigabytes), por lo que tener que comprimir un algoritmo en una cantidad limitada de memoria ya no es el tipo de problema que solía ser. Sin embargo, los diferentes tipos de memoria y sus velocidades de acceso relativas pueden ser significativos:

• Los registros del procesador son la memoria más rápida y ocupan menos espacio. La mayor parte de los cálculos directos en las computadoras modernas se realizan con operandos de origen y destino en registros antes de actualizarlos en la memoria caché, la memoria principal y la memoria virtual, si es necesario. En un núcleo de procesador , normalmente hay cientos de bytes o menos de disponibilidad de registros, aunque un archivo de registros puede contener más registros físicos que registros arquitectónicos definidos en la arquitectura del conjunto de instrucciones.
• La memoria caché es la segunda más rápida y la segunda más pequeña disponible en la jerarquía de memoria. Las cachés están presentes en procesadores como CPU o GPU, donde normalmente se implementan en RAM estática , aunque también se pueden encontrar en periféricos como unidades de disco. Las cachés de procesador a menudo tienen su propia jerarquía de varios niveles ; los niveles inferiores son más grandes, más lentos y normalmente se comparten entre los núcleos del procesador en procesadores multinúcleo . Para procesar operandos en la memoria caché, una unidad de procesamiento debe obtener los datos de la caché, realizar la operación en registros y escribir los datos de nuevo en la caché. Esto funciona a velocidades comparables (aproximadamente 2-10 veces más lentas) con la unidad lógica aritmética o la unidad de punto flotante de la CPU o GPU si está en la caché L1 . ^[8] Es aproximadamente 10 veces más lento si hay una falla de caché L1 y se debe recuperar y escribir en el caché L2 , y otras 10 veces más lento si hay una falla de caché L2 y se debe recuperar de un caché L3 , si está presente.
• La memoria física principal se implementa con mayor frecuencia en RAM dinámica (DRAM). La memoria principal es mucho más grande (normalmente gigabytes en comparación con ≈8 megabytes ) que una caché de CPU L3, con latencias de lectura y escritura típicamente 10-100 veces más lentas. ^[8] A partir de 2018 ^[update], la RAM se implementa cada vez más en el chip de los procesadores, como memoria de CPU o GPU . ^{[ cita requerida ]}
• La memoria paginada , a menudo utilizada para la gestión de memoria virtual , es memoria almacenada en un almacenamiento secundario como un disco duro , y es una extensión de la jerarquía de memoria que permite el uso de un espacio de almacenamiento potencialmente más grande, a costa de una latencia mucho mayor, típicamente alrededor de 1000 veces más lenta que una falla de caché para un valor en RAM. ^[8] Si bien originalmente estaba motivada para crear la impresión de que había mayores cantidades de memoria disponibles de las que realmente estaban disponibles, la memoria virtual es más importante en el uso contemporáneo por su equilibrio entre tiempo y espacio y por permitir el uso de máquinas virtuales . ^[8] Las fallas de caché de la memoria principal se denominan fallas de página e incurren en enormes penalizaciones de rendimiento en los programas.

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ápida que un algoritmo que tenga que recurrir a la paginación. Debido a esto, las políticas de reemplazo de caché son extremadamente importantes para la computación de alto rendimiento, al igual que la programación consciente de la memoria 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. Diferentes sistemas tendrán diferentes cantidades de estos diversos tipos de memoria, por lo que el efecto de las necesidades de memoria del algoritmo puede variar en gran medida de un sistema a otro.

En los primeros tiempos de la informática electrónica, si un algoritmo y sus datos no cabían en la memoria principal, no se podía utilizar. Hoy en día, el uso de memoria virtual parece proporcionar mucha más memoria, pero a costa del rendimiento. Se puede obtener una velocidad mucho mayor si un algoritmo y sus datos caben en la memoria caché; en este caso, minimizar el espacio también ayudará a minimizar el tiempo. Esto se denomina principio de localidad y se puede subdividir en localidad de referencia , localidad espacial y localidad temporal . Un algoritmo que no cabe completamente en la memoria caché pero que muestra localidad de referencia puede funcionar razonablemente bien.

• Análisis de algoritmos : cómo determinar los recursos que necesita un algoritmo
• Benchmark : un método para medir tiempos de ejecución comparativos en casos definidos
• Caso mejor, peor y promedio : consideraciones para estimar los tiempos de ejecución en tres escenarios
• Optimización del compilador: optimización derivada del compilador
• Teoría de la complejidad computacional
• Rendimiento de la computadora : métricas del hardware de la computadora
• Algoritmia empírica : la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos.
• Optimización (informática)
• Análisis de rendimiento : métodos para medir el rendimiento real de un algoritmo en tiempo de ejecución