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 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ón	Nombre	Ejemplos
O()1){displaystyle O(1)}	constante	Encontrar 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)}	logaritmic	Encontrar 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)}	lineal	Encontrar 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 quasilinear	Realización de una transformación rápida Fourier; heapsort, quicksort (mejor y caso promedio), o combinar tipo
O()n2){displaystyle O(n^{2}}	quadratic	Multiplicando 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;"/>	exponencial	Encontrar 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:

• Hora: ¿Cuánto tarda en completar el algoritmo?
• Espacio: ¿Cuánta memoria de trabajo (normalmente RAM) es necesaria por el algoritmo? Esto tiene dos aspectos: la cantidad de memoria necesaria por el código (utilización del espacio de la joyería), y la cantidad de memoria necesaria para los datos sobre los que funciona el código (utilización del 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 de energía directo: energía necesaria directamente para operar el ordenador.
• Consumo de energía indirecto: energía necesaria para enfriamiento, iluminación, etc.

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:

• Tamaño de la transmisión: ancho de banda podría ser un factor limitante. La compresión de datos se puede utilizar para reducir la cantidad de datos a transmitir. Mostrando una imagen o imagen (por ejemplo, logotipo de Google) puede resultar en la transmisión de decenas de miles de bytes (48K en este caso) en comparación con la transmisión de seis bytes para el texto "Google". Esto es importante para las tareas de computación I/O.
• Espacio externo: espacio necesario en un disco u otro dispositivo de memoria externo; esto podría ser para almacenamiento temporal mientras se está llevando a cabo el algoritmo, o podría ser almacenamiento a largo plazo necesario para llevar adelante 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.
• Costo total de propiedad: particularmente si una computadora está dedicada a un algoritmo en particular.

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:

• La cantidad de memoria necesaria para mantener el código para el algoritmo.
• La cantidad de memoria necesaria para los datos de entrada.
• La cantidad de memoria necesaria para los datos de salida.
  • Algunos algoritmos, como la clasificación, a menudo reorganizan los datos de entrada y no necesitan espacio adicional para los datos de salida. Esta propiedad se denomina operación "en su lugar".
• La cantidad de memoria necesaria como espacio de trabajo durante el cálculo.
  • Esto incluye variables locales y cualquier espacio de pila necesario por rutinas llamadas durante un cálculo; este espacio de pila puede ser significativo para algoritmos que utilizan técnicas recursivas.

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:

• Procesador registra, el más rápido de las tecnologías de memoria informática con la menor cantidad de espacio de almacenamiento. La mayor parte de la computación directa en computadoras modernas se produce con fuente y destino operands en registros antes de ser actualizado a la caché, memoria principal y memoria virtual si es necesario. En un núcleo de procesador, generalmente hay en el orden de cientos de bytes o menos de disponibilidad de registro, aunque un archivo de registro puede contener más registros físicos que registros arquitectónicos definidos en la arquitectura del conjunto de instrucciones.
• La memoria de caché es la segunda memoria más rápida y segunda más pequeña disponible en la jerarquía de memoria. Las jaulas están presentes en CPU, GPUs, discos duros y periféricos externos, y normalmente se implementan en RAM estática. Los caches de memoria son multinivel; los niveles más bajos son mayores, más lentos y normalmente compartidos entre núcleos de procesadores en procesadores multi-core. Para procesar operados en memoria de caché, una unidad de procesamiento debe buscar los datos de la caché, realizar la operación en registros y escribir los datos de vuelta al caché. Esto opera a velocidades comparables (aproximadamente 2-10 veces más lentas) con la unidad de lógica aritmética de la CPU o GPU o unidad de punto flotante si en la caché L1. Es aproximadamente 10 veces más lento si hay una falta de caché L1 y debe ser recuperada y escrita al caché L2, y 10 veces más lenta si hay una falta de caché L2 y debe ser recuperada de un caché L3, si está presente.
• La memoria física principal se implementa con más frecuencia en RAM dinámica (DRAM). La memoria principal es mucho más grande (normalmente gigabytes en comparación con ♥8 megabytes) que un caché de CPU L3, con retrasos de lectura y escritura típicamente 10-100 veces más lento. A partir de 2018, RAM se implementa cada vez más en el chip de procesadores, como memoria CPU o GPU.
• La memoria virtual se implementa con más frecuencia en términos de almacenamiento secundario como un disco duro, y es una extensión a la jerarquía de memoria que tiene mucho espacio de almacenamiento más grande pero latencia mucho mayor, típicamente alrededor de 1000 veces más lento que una falta de caché para un valor en RAM. Si bien originalmente motivado para crear la impresión de cantidades más altas de memoria disponibles que estaban realmente disponibles, la memoria virtual es más importante en el uso contemporáneo para su intercambio espacio-tiempo y permitiendo el uso de máquinas virtuales. Cache falta de memoria principal se llaman fallas de página, e incurren enormes sanciones 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á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

• David May FRS a British computer scientific and currently Professor of Computer Science at University of Bristol and fundador and CTO of XMOS Semiconductor, believes one of the problems is that there is a reliance on Moore's law to solve inefficiencies. Ha avanzado un 'alternativo' a la ley de Moore (la ley de mayo) declaró lo siguiente:

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.

• Autor de software Adam N. Rosenburg en su blog "El fracaso de la computadora digital", ha descrito el estado actual de programación como cerca del "espacio de eventos Software", (incluyendo al ficticio "Zapato horizonte"descrita por Douglas Adams en su Guía de Hitchhiker para la galaxia libro). Estima que ha habido una pérdida de 70 dB factor de productividad o "99.99999 por ciento, de su capacidad para entregar las mercancías", desde los años 80 "Cuando Arthur C. Clarke comparó la realidad de la informática en 2001 al ordenador HAL 9000 en su libro 2001: Un Space Odyssey, señaló lo maravillosamente pequeños y poderosos ordenadores eran pero lo decepcionante que la programación informática se había convertido".

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:

• Revista Wired