Eficiencia algorítmica

Ajustar Compartir Imprimir Citar
Propiedad de un algoritmo

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 ingeniería para un proceso repetitivo o continuo.

Para lograr la máxima eficiencia, es deseable minimizar el uso de recursos. Sin embargo, los 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, el tipo de burbujas y el timsort son ambos algoritmos para ordenar una lista de elementos de menor a mayor. La burbuja clasifica la lista en tiempo proporcional al número de elementos cuadrados (O()n2){textstyle O(n^{2}}, ver Big O notación), pero sólo requiere una pequeña cantidad de memoria extra que es constante con respecto a la longitud de la lista (O()1){textstyle O(1)}). Timsort clasifica la lista en tiempo linearitmico (proporcional a una cantidad de veces su logaritmo) en la longitud de la lista (O()nlog⁡ ⁡ n){textstyle O(nlog n)}), pero tiene un requisito espacial lineal en la longitud de la lista (O()n){textstyle O(n)}). Si las listas grandes deben ser clasificadas a alta velocidad para una aplicación dada, timsort es una mejor opción; sin embargo, si minimizar la huella de memoria de la clasificación es más importante, el tipo de burbuja es una mejor opción.

Antecedentes

La importancia de la eficiencia con respecto al tiempo fue enfatizada por Ada Lovelace en 1843 aplicada al motor analítico mecánico 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 un motor calculador. Un objeto esencial es elegir ese arreglo que tenderá a reducir al mínimo el tiempo necesario para completar el cálculo"

Las primeras computadoras electrónicas tenían una velocidad limitada y una memoria de acceso aleatorio limitada. Por lo tanto, se produjo un intercambio de espacio-tiempo. Una tarea podría usar un algoritmo rápido usando mucha memoria, o podría usar un algoritmo lento usando poca memoria. La compensació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 enfatizó que la eficiencia sigue siendo una consideración importante:

"En las disciplinas de ingeniería establecidas una mejora del 12%, obtenida fácilmente, nunca se considera marginal y creo que el mismo punto de vista debe prevalecer en la ingeniería de software"

Resumen

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 visto aumentos dramáticos tanto en el poder 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 informática 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 computadoras 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 simple 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 la 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, el 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 en 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 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 problemas de optimización.

Análisis teórico

En el análisis teórico de algoritmos, la práctica normal es estimar su complejidad en el sentido asintotico. La notación más utilizada para describir el consumo de recursos o "complejidad" es la notación de Donald Knuth Big O, que representa la complejidad de un algoritmo como función del tamaño de la entrada n{textstyle n}. Grande O notación es una medida asintotica de la complejidad de la función, donde f()n)=O()g()n)){textstyle f(n)=O{bigl (}g(n){bigr)} aproximadamente significa que el requisito de tiempo para un algoritmo es proporcional a g()n){displaystyle g(n)}, omitiendo términos de orden inferior que contribuyen menos que g()n){displaystyle g(n)} al crecimiento de la función como n{textstyle n} crece arbitrariamente grande. Esta estimación puede ser engañosa cuando n{textstyle n} es pequeño, pero es generalmente suficientemente preciso cuando n{textstyle n} es grande como la notación es asintotica. Por ejemplo, el tipo de burbujas puede ser más rápido que el tipo de fusión cuando sólo unos pocos elementos deben ser ordenados; sin embargo, es probable que la implementación satisfaga los requisitos de rendimiento para una pequeña lista. Por lo general, los programadores están interesados en algoritmos que escalan eficientemente a grandes tamaños de entrada, y fusionar tipo es preferido sobre tipo de burbuja para listas de longitud encontradas en la mayoría de los programas intensivos de datos.

Algunos ejemplos de notación Big O aplicada a algoritmos' La complejidad asintótica del tiempo incluye:

NotaciónNombreEjemplos
O()1){displaystyle O(1)}constanteEncontrar la mediana de una lista ordenada de mediciones; Usar una tabla de búsqueda de tamaño constante; Usar una función de hash adecuada para buscar un artículo.
O()log⁡ ⁡ n){displaystyle O(log n)}logaritmicEncontrar un artículo en una matriz ordenada con una búsqueda binaria o un árbol de búsqueda equilibrado, así como todas las operaciones en un montón de binomial.
O()n){displaystyle O(n)}linealEncontrar un artículo en una lista sin surtido o un árbol malformado (caso inferior) o en un array sin surtido; Agregar dos n-bit enteros por carga ondulada.
O()nlog⁡ ⁡ n){displaystyle O(nlog n)}linearithmic, loglinear, or quasilinearRealización de una transformación rápida Fourier; heapsort, quicksort (mejor y caso promedio), o combinar tipo
O()n2){displaystyle O(n^{2}}quadraticMultiplicando dos n- números de dígitos por un simple algoritmo; tipo de burbuja (caso peor o aplicación ingenua), Tipo de casco, rápido (caso peor), tipo de selección o tipo de inserción
1}" xmlns="http://www.w3.org/1998/Math/MathML">O()cn),c■1{displaystyle O(c^{n}),;c confianza1}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89f4ecbe75f2424973437985768adfe6652b1650" style="vertical-align: -0.838ex; width:12.755ex; height:2.843ex;"/>exponencialEncontrar la solución óptima (no aproximada) al problema del vendedor que viaja utilizando programación dinámica; determinar si dos declaraciones lógicas son equivalentes mediante búsqueda de fuerza bruta

Evaluación comparativa: medir el rendimiento

Para las 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 tan eficiente como antes con datos conocidos, teniendo en cuenta cualquier mejora funcional. 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 las computadoras centrales, ciertos productos de clasificación patentados de compañías de software independientes, como Syncsort, compiten con los 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. y The Computer Language Benchmarks Game compara el rendimiento de las implementaciones de problemas típicos de programación en varios lenguajes de programación.

Incluso creando "hágalo usted mismo" Los puntos de referencia pueden demostrar el rendimiento relativo de diferentes lenguajes de programación, utilizando una variedad de criterios especificados por el usuario. Esto es bastante simple, como un "resumen de rendimiento en nueve idiomas" por Christopher W. Cowell-Shah demuestra con el ejemplo.

Problemas de implementación

Los problemas de implementación también pueden afectar la eficiencia, como la elección del lenguaje de programación, la forma en que se codifica el algoritmo, la elección de un compilador para un lenguaje en particular, 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. Consulte 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 alineación de datos, granularidad de datos, localidad de caché, coherencia de caché, recolección de basura, paralelismo a nivel de instrucción, subprocesamiento múltiple (ya sea a nivel de hardware o software), multitarea simultánea y llamadas a subrutinas.

Algunos procesadores tienen capacidades para el procesamiento de vectores, lo que permite que una sola instrucción opere en múltiples operandos; puede o no ser fácil para un programador o compilador usar estas capacidades. Es posible que los algoritmos diseñados para el procesamiento secuencial deban rediseñarse 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 eficientes de alto nivel para sistemas de computación 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, por lo 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 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 objetivo de compilación para optimizar mejor el rendimiento de un programa. En el caso extremo, un compilador puede verse obligado a emular instrucciones no admitidas en una plataforma de destino de compilación, obligándolo 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 los sistemas integrados con respecto a la aritmética de coma flotante, donde los microcontroladores pequeños y de baja potencia a menudo carecen de soporte de hardware para la aritmética de coma flotante y, por lo tanto, requieren rutinas de software computacionalmente costosas para producir cálculos de coma flotante.

Medidas de uso de recursos

Las medidas se expresan normalmente como función del tamaño de la entrada n{displaystyle scriptstyle {n}.

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, el consumo de energía está creciendo como una métrica importante para las tareas informáticas 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 a menudo se denomina computación verde.

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

Tiempo

Teoría

Analice el algoritmo, normalmente utilizando el análisis de complejidad de 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 Big O. 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 menor importancia. Los algoritmos que incluyen procesamiento paralelo pueden ser más difíciles de analizar.

Practica

Use un punto de referencia para cronometrar el uso de un algoritmo. Muchos lenguajes de programación tienen una función disponible que proporciona el uso del tiempo de la CPU. Para algoritmos de ejecución prolongada, el tiempo transcurrido también podría ser de interés. Por lo general, los resultados deben promediarse en varias pruebas.

La creación de perfiles basada en ejecución puede ser muy sensible a la configuración del hardware y 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, compilador y opciones de compilador en particular, por lo que todos los algoritmos que se comparan deben implementarse en las mismas condiciones.

Espacio

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, generalmente utilizando el análisis de complejidad de espacio 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 Big O.

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 de 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 fines de la década de 2010, es típico 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.

Caché y jerarquía de 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 alineación de datos y la programación con reconocimiento de caché. Para complicar aún más el problema, algunos sistemas tienen hasta tres niveles de memoria caché, con distintas velocidades efectivas. Los 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 mucho de un sistema a otro.

En los primeros días de la computación electrónica, si un algoritmo y sus datos no cabían en la memoria principal, entonces el algoritmo no podía usarse. Hoy en día, el uso de la memoria virtual parece proporcionar mucha memoria, pero a costa del rendimiento. Si un algoritmo y sus datos caben en la memoria caché, 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 encaje completamente en la memoria caché pero que muestre una localidad de referencia puede funcionar razonablemente bien.

Crítica al estado actual de la programación

La eficiencia del software es la mitad cada 18 meses, compensando la ley de Moore

Puede continuar diciendo:

En sistemas ubicuos, reducir las instrucciones ejecutadas puede duplicar la vida de la batería y los grandes conjuntos de datos traen grandes oportunidades para un mejor software y algoritmos: Reducción del número de operaciones de N×N a N×log(N) tiene un efecto dramático cuando N es grande... para N = 30 mil millones, este cambio es tan bueno como 50 años de mejoras tecnológicas.

Concursos para los mejores algoritmos

Los siguientes concursos invitan a participar para los mejores algoritmos en función de algunos criterios arbitrarios decididos por los jueces: