Eficiencia algorítmica

En Ciencias de la Computación, el término eficiencia algorítmica es usado para describir aquellas propiedades de los algoritmos que están relacionadas con la cantidad de recursos utilizados por el algoritmo. Un algoritmo debe ser analizado para determinar el uso de los recursos que realiza. La eficiencia algorítmica puede ser vista como análogo a la ingeniería de productividad de un proceso repetitivo o continuo.

Con el objetivo de lograr una eficiencia máxima se quiere minimizar el uso de recursos. Sin embargo, varias medidas (e.g. complejidad temporal, complejidad espacial) no pueden ser comparadas directamente, luego, cuál de dos algoritmos es considerado más eficiente, depende de cuál medida de eficiencia se está considerando como prioridad, e.g. la prioridad podría ser obtener la salida del algoritmo lo más rápido posible, o que minimice el uso de la memoria, o alguna otra medida particular.

Note que este artículo no trata de optimización, concepto que es abordado en optimización de programas, compiladores de optimización, optimización de bucles, optimización de códigos orientados a objetos, etc. El término optimización en sí puede causar confusión, ya que todo lo que generalmente se puede hacer es en realidad una 'mejora'.

Conocimiento previo

La importancia de la eficiencia con respecto a la complejidad temporal fue enfatizada por Ada Lovelace en 1843 como resultado de su trabajo con el motor analítico mecánico de Charles Babbage:

"En casi todo cómputo son posibles una gran variedad de configuraciones para la sucesión de un proceso, y varias consideraciones pueden influir en la selección de estas según el propósito de un motor de cálculos. Un objetivo esencial es escoger la configuración que tienda a minimizar el tiempo necesario para completar el cálculo."​

Las primeras computadoras electrónicas estaban considerablemente limitadas tanto por la velocidad de procesamiento como por la cantidad de memoria disponible. En algunos casos se notó que existía una renunciación espacio-tiempo (tradeoff), por lo cual una tarea podía ser tratada usando tanto un algoritmo eficiente en cuanto a tiempo pero que utiliza gran cantidad de memoria activa como un algoritmo más lento pero que utiliza poca memoria activa. La ingeniería de 'tradeoff' fue entonces para usar el algoritmo más rápido que se acomodara en la memoria disponible.

Las computadoras modernas son mucho más rápidas que las primeras computadoras, y cuentan con cantidades muy superiores de memoria disponible (Gigabytes en vez de Kilobytes). No obstante, Donald Knuth enfatizó que la eficiencia sigue siendo un tema importante a considerar:

"En disciplinas de ingeniería establecidas, un 12% de mejoría obtenido con facilidad, nunca es considerado un resultado marginal, y creo que el mismo punto de vista prevalece para la ingeniería de software."​

Introducción

Un algoritmo es considerado eficiente si su consumo de recursos está en la media o por debajo de los niveles aceptables. Hablando a grandes rasgos, 'aceptable' significa: que el algoritmo corre en un tiempo razonable en una computadora dada. Desde 1950 hasta la actualidad las computadoras han tenido un avance impresionante tanto en poder computacional como en la capacidad de memoria disponible, lo que indica que los niveles aceptables de eficiencia en la actualidad hubieran sido inadmisibles 10 años atrás.

Los fabricantes de computadoras están frecuentemente lanzando nuevos modelos, normalmente con mejor rendimiento. El costo de mejorar el software puede ser bastante caro, por ello en muchos casos la forma más simple y barata de alcanzar un mejor rendimiento es comprar una computadora con mejor rendimiento de por sí.

Existen muchas maneras para medir la cantidad de recursos utilizados por un algoritmo: las dos medidas más comunes son la complejidad temporal y espacial; otras medidas a tener en cuenta podrían ser la velocidad de transmisión, uso temporal del disco duro, así como uso del mismo a largo plazo, consumo de energía, tiempo de respuesta ante los cambios externos, etc. Muchas de estas medidas dependen del tamaño de la entrada del algoritmo (i.e. la cantidad de datos a ser procesados); además podrían depender de la forma en que los datos están organizados (e.g. algoritmos de ordenación necesitan hacer muy poco en datos que ya están ordenados o que están ordenados de forma inversa).

En la práctica existen otros factores que pueden afectar la eficiencia de un algoritmo, tales como la necesidad de cierta precisión y/o veracidad. La forma en que un algoritmo es implementado también puede tener un efecto de peso en su eficiencia, muchos de los aspectos asociados a la implementación se vinculan a problemas de optimización.

Análisis Teórico

En el estudio teórico de un algoritmo, lo normal es estimar su complejidad de forma asintótica, i.e. usar notación O grande para representar la complejidad de un algoritmo como una función que depende del tamaño de la entrada n, esto es generalmente acertado cuando n es lo suficientemente grande, pero para n pequeños podría ser erróneo (e.g. bubble sort puede ser más rápido que quicksort cuando solo unos pocos valores deben ser ordenados).

Algunos ejemplos de notación de O grande incluyen:

Notación	Nombre	Ejemplos
$O(1)\,$	constante	Determinar si un número es par o impar. Usar una tabla de consulta que asocia constante/tamaño. Usar una función hash para obtener un elemento.
$O(\log n)\,$	logarítmico	Buscar un elemento específico en un array utilizando un árbol binario de búsqueda o un árbol de búsqueda balanceado, así como todas las operaciones en un Heap binomial.
$O(n)\,$	lineal	Buscar un elemento específico en una lista desordenada o en un árbol degenerado (peor caso).
$O(n\log n)\,$	loglinear o quasilinear	Ejecutar una transformada rápida de Fourier; heapsort, quicksort (caso mejor y promedio), o merge sort
$O(n^{2})\,$	cuadrático	Multiplicar dos números de n dígitos por un algoritmo simple. bubble sort (caso peor o implementación sencilla), Shell sort, quicksort (caso peor).
$O(c^{n}),\;c>1$	exponencial	Encontrar la solución exacta al problema del viajante utilizando programación dinámica. Determinar si dos sentencias lógicas son equivalentes utilizando una búsqueda por fuerza bruta

Benchmarking: midiendo la eficiencia

Benchmarks (desc. estándar de comparación, cota de referencia, punto de referencia, conjunto de procedimientos para avaluar el rendimiento de un ordenador) son usados para realizar comparaciones entre programas en competencia o para probar versiones nuevas de software que se quiera liberar, y sirve como indicador relativo para medir la eficiencia de un algoritmo. Si un nuevo algoritmo de ordenación es implementado, por ejemplo puede ser comparado con su predecesor para asegurar su eficiencia al menos con los datos conocidos o recopilados por este último, teniendo en cuenta claro las mejoras funcionales del nuevo algoritmo. Los benchmarks pueden ser utilizados por los clientes para comparar varios productos de diferentes proveedores con el objetivo de estimar cuál producto satisface sus necesidades en términos de eficiencia.

Algunos benchmarks prestan servicios para producir comparaciones detalladas sobre la velocidad relativa de varios lenguajes compilados e interpretados, por ejemplo,​​ The Computer Language Benchmarks Game​ compara la eficiencia entre una gran variedad de lenguajes sobre la implementación de problemas típicos de programación.

Detalles de implementación

Los detalles de implementación también tienen un efecto sobre la eficiencia, como la elección de un lenguaje de programación, o la forma en que el algoritmo está actualmente implementado, o la elección de un compilador para un lenguaje particular, incluso el sistema operativo que se está usando. En algunos casos un lenguaje interpretado pudiera ser mucho más lento que uno compilado.​

Existen otros factores que pueden afectar la eficiencia temporal y espacial, y que pueden estar fuera del control del programador, entre estos están: granularidad de los datos, recolector de basura, paralelismo a nivel de instrucción, y llamadas a subprocesos.​

Algunos procesadores tienen la capacidad de procesado vectorial, lo que permite que una instrucción se capaz de operar sobre varios datos; puede ser fácil o no para un programador o un compilador usar estas herramientas. Los algoritmos diseñados para ser procesados de forma secuencial necesitarían ser completamente rediseñados para hacer uso del procesamiento en paralelo.

Otro detalle de implementación importante referente a los procesadores aparece cuando estos implementan una instrucción de forma diferente, o sea que una instrucción que es relativamente rápida en algunos modelos podría ser más lenta en otros, esto hace difícil el trabajo para un compilador guiado a la optimización.

Medidas del uso de recursos

Las medidas de eficiencia son normalmente expresadas en función del tamaño de la entrada n.

Las dos medidas más comunes son:

• Complejidad temporal: cuanto se demora un algoritmo en terminar.
• Complejidad espacial: cuanta memoria operativa (RAM usualmente) es requerida por el algoritmo. Esto tiene dos apartados, la cantidad de memoria que necesita el código y la cantidad que necesitan los datos sobre los que opera el algoritmo.

Para computadoras cuya energía es por batería (e.g. laptops), o para grandes cálculos (e.g. supercomputadoras) otras medidas también son de interés:

• Consumo directo de energía: energía requerida por la computadora.
• Consumo indirecto de energía: energía requerida para el enfriamiento, la iluminación, etc.

En algunos casos otras medidas podrían ser relevantes:

• Capacidad de transmisión: el ancho de banda puede llegar a ser un factor limitante. La compresión de datos es utilizada para reducir la cantidad de datos a transmitir.
• Espacio externo: cantidad de espacio requerido en disco o algún otro dispositivo externo; esto podría ser solo una necesidad temporal, o sea solo se requiere dicho espacio mientras está corriendo e algoritmo o podría ser una necesidad a largo plazo para futuras referencias.
• Tiempo de respuesta: Esto es particularmente relevante en tiempo real para una aplicación cuando el sistema de la computadora debe responder de forma rápida a los eventos externos.

Complejidad temporal

Teoría

Para analizar un algoritmo generalmente se usa la complejidad temporal para obtener un estimado del tiempo de ejecución expresado en función del tamaño de la entrada. El resultado es típicamente expresado en notación O grande. Esto suele ser útil para comparar algoritmos, especialmente cuando se necesita procesar una gran cantidad de datos. Estimaciones más detalladas se requieren para comparar algoritmos que procesan pequeñas cantidades de datos (de todas formas en estos casos el tiempo no debería ser un problema). Algoritmos implementados para usar procesamiento paralelo de los datos son mucho más difíciles de analizar.

En la práctica

Se utilizan benchmarks para medir el uso de un algoritmo. Muchos lenguajes de programación presentan funciones para medir el tiempo de uso del procesador. En casos de algoritmos que se ejecutan en un tiempo considerablemente largo, dicho tiempo pudiera resultar de interés. El resultado es generalmente un promedio de los resultados de varias pruebas consecutivas aplicadas sobre el objetivo.

Este tipo de pruebas son altamente sensibles a configuraciones de hardware y existe la posibilidad de que otros programas se estén ejecutando al mismo tiempo en un ambiente capaz de procesar varias tareas a la vez.

Dichas pruebas también dependen intrínsecamente del lenguaje de programación, el compilador y las opciones del compilador, lo que implica que dos algoritmos que se comparan deberán estar implementados bajo las mismas condiciones.

Complejidad espacial

Esta sección se enfoca en el uso de memoria (usualmente RAM) por los algoritmos mientras son ejecutados. Así como la complejidad temporal, explicado anteriormente, parte del análisis de un algoritmo se hace vía la complejidad espacial para obtener un estimado del uso de memoria principal expresado mediante una función según el tamaño de la entrada. El resultado es expresado usualmente en notación O grande.

Existen 4 aspectos relevantes a considerar:

• La cantidad de memoria requerida por el código del algoritmo.
• La cantidad de memoria requerida para almacenar los datos de entrada.
• La cantidad de memoria requerida para los datos de salida (algoritmos como los de ordenación suelen reorganizar los datos de entrada y por ello no necesitan memoria extra para la salida).
• La cantidad de memoria requerida en cuanto a espacio de trabajo del algoritmo para realizar los cálculos y asignaciones (tanto para variables como cualquier espacio necesario en la pila para almacenar llamadas a subrutinas, este espacio es particularmente significativo para algoritmos que utilizan técnicas recursivas).

Las primeras computadoras electrónicas y computadoras de escritorio, contaban con muy poca capacidad de memoria operativa. E.g. la EDSAC 1949 tenía un máximo de 1024 17-bit words, mientras que la Sinclair ZX80 1980 surgió con solo 1024 8-bit bytes de memoria operativa.

Las computadoras actuales cuentan con una memoria operativa suficientemente grande (16 Gb y más), o sea que obligar a un algoritmo a ejecutarse reducidamente en cierta cantidad de memoria ya no representa el mismo problema que solía ser. Pero la presencia de tres categorías diferentes de memoria pudiera ser significativa:

• Memoria Caché (usualmente RAM-estática): esta opera a una velocidad comparable a la del CPU.
• Memoria física principal (usualmente RAM-dinámica): esta opera un tanto más lenta que el CPU.
• Memoria virtual (usualmente en disco): esta da la impresión de una gran cantidad de memoria utilizable y opera en el orden de los miles más lenta que el CPU.

Un algoritmo cuyas necesidades pueden ser satisfechas con la memoria caché será mucho más rápido que uno que necesite de la memoria principal y en consecuencia mucho más rápido que uno que necesita recurrir a la memoria virtual. Si se quiere profundizar aún más dicho problema, existen sistemas que tienen hasta tres niveles de memoria caché, con diferentes y variadas velocidades. Sistemas diferentes tendrán diferentes cantidades asignadas a los tipos de memoria comentados, lo que conlleva a que las necesidades de memoria de un algoritmo varíen significativamente entre un sistema y otro.

En los días veteranos de las computadoras electrónicas si un algoritmo requería más memoria que la brindada por la memoria principal, dicho algoritmo no podía ser utilizado. En nuestros días la memoria virtual resuelve dichos problemas, bajo un costo de eficiencia. Un algoritmo que se suple solo de la memoria caché presenta excelentes resultados en cuanto a velocidad, en estos casos la optimización del espacio repercute de forma relevante en la optimización del tiempo.

Ejemplos de algoritmos eficientes

• quicksort El primer algoritmo de ordenación con un orden de $O(n\log n)\,$.
• heapsort Otro algoritmo de rápida ejecución.
• Búsqueda binaria Búsqueda en una tabla ordenada
• Algoritmo de Boyer-Moore para búsqueda de cadenas Buscar una cadena dentro de otra.

Críticas al estado actual de la programación

• David May FRS un Científico de la Computación Británico, actualmente Profesor de Ciencias de la Computación en la Universidad de Bristol además de ser fundador y CTO de XMOS Semiconductor, cree que la confianza en la Ley de Moore para resolver ineficiencias es uno de los problemas que existen. Él ha avanzado en una 'alternativa' a la ley de Moore (la ley de May), expresada como sigue:​

  La eficiencia del software se divide a la mitad cada 18 meses compensando la ley de Moore

  Continua expresando

  En sistemas ubicuos, dividiendo a la mitad el número de instrucciones ejecutadas se puede duplicar la vida de la batería y los grandes conjuntos de datos brindan grandes oportunidades para mejores softwares y algoritmos: Reducir el número de operaciones de N x N a N x log(N) tiene un efecto dramático para un N grande... para N = 30 billones, este cambio es equivalente a 50 años de mejoras tecnológicas

• El creador de Software Adam N. Roseenburge en su blog "The failure of the Digital computer", describió el estado actual de la programación como cercano al "Software event horizon"(Horizonte de eventos del Software), (aludiendo al ficticio "shoe event horizon"(horizonte del evento zapato o horizonte del zapato) descrito por Douglas Adams en su libro Hitchhiker's Guide to the Galaxy​).

Él estima que ha habido un factor de 70dB en pérdida de productividad o ""99.99999%, en su capacidad para funcionar correctamente"", desde los 1980—"Cuando Arthur C. Clarke comparó el estado de la computación en el 2001 a la computadora HAL en su libro 2001: A Space Odyssey, señaló cuan increíblemente pequeñas y poderosas computadoras había, pero cuan decepcionante se había vuelto la programación".

• Conrad Weisert brinda ejemplos, algunos de los cuales fueron publicados en el ACM SIGPLAN (Special Interest Group on Programming Languages (Grupo con interés especial en los lenguajes de programación)). Nótese en diciembre de 1995 en: "Atrocious Programming Thrives"​
• Marc Andreessen cofundador de Netscape es citado en "Mavericks at Work" (ISBN 0-06-077961-6) diciendo "Cinco programadores geniales pueden completamente superar a 1000 programadores mediocres."

Competencias por el mejor algoritmo

Las siguientes competiciones dan admisión para los mejores algoritmos basados en algunos criterios arbitrarios decididos por los jueces:-

• Wired​

Véase también

• Análisis de algoritmos - como determinar los recursos necesitados por un algoritmo
• Algoritmos de búsqueda binaria— una técnica simple y eficiente para búsqueda en arrays ordenados
• Benchmark— un método para medir la ejecución comparativa de los tiempos de ejecución para casos definidos
• Caso mejor, caso peor y caso average— Consideraciones para estimar los tiempos de ejecución en los tres casos
• Tabla de saltos— una técnica para reducir la longitud del camino de las instrucciones, el tamaño del código de máquina, (y usualmente el uso de memoria)
• Optimización del compilador— optimización referente al compilador
• Teoría de la complejidad computacional
• Indexado de Bases de datos— una estructura de datos que mejora la velocidad de recuperación de datos en una tabla de base de datos
• Codificación entrópica— Codificar los datos de manera eficiente usando la frecuencia de ocurrencia de cadenas como un criterio para sustitución
• Computación verde— una migración hacia tecnologías más 'verdes' consumiendo menos recursos
• Algoritmo de Huffman— un algoritmo para la codificación eficiente de datos
• Localidad de referencia— para evitar que el cache de la CPU se retrase por el acceso a memoria no local
• Manejo de Memoria
• Optimización
• Análisis de rendimiento— métodos para medir el rendimiento real de un algoritmo en tiempo de ejecución
• Computación en tiempo real— más ejemplos de aplicaciones que son dependientes del tiempo de manera crítica
• Análisis del tiempo de ejecución— estimación del tiempo esperado de ejecución y de la escalabilidad de los algoritmos
• Super-threading
• Ejecución especulativa o Ejecución impaciente
• Código con hilos— similar al método de tabla virtual o tabla de ramas

Enlaces externos

• Animation of the Boyer-Moore algorithm (Applet Java)
• "How algorithms shape our world". A TED Talk by Kevin Slavin.
• Misconceptions about algorithmic efficiency in high-schools

• Datos: Q1296251