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 continuo o repetido.
Para lograr la máxima eficiencia, deseamos 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 considere más importante.
Por ejemplo, el ordenamiento de burbujas y el ordenamiento temporal son algoritmos para ordenar una lista de elementos del más pequeño al más grande. La clasificación de burbujas ordena la lista en el tiempo proporcional al número de elementos al cuadrado (, vea 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 (). 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 las listas grandes deben ordenarse 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 de burbujas es una mejor opción.
Fondo
La importancia de la eficiencia con respecto al tiempo fue enfatizada por Ada Lovelace en 1843 como 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 de cálculo. Un objeto esencial es elegir el arreglo que tenderá a reducirse a un mínimo del tiempo necesario para completar el cálculo " [1]
Las primeras computadoras electrónicas estaban severamente limitadas tanto por la velocidad de las operaciones como por la cantidad de memoria disponible. En algunos casos se advirtió que existía una compensación de espacio-tiempo , por la cual una tarea podía manejarse usando un algoritmo rápido que usaba bastante memoria de trabajo, o usando un algoritmo más lento que usaba muy poca memoria de trabajo. . La compensación de la ingeniería fue entonces utilizar el algoritmo más rápido que cabría 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%, 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]
Descripción general
Un algoritmo se considera eficiente si su consumo de recursos, también conocido como costo computacional, es igual o inferior a un nivel aceptable. 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 la computadora 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 con frecuencia presentan 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 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 los 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 clasificación funcionan mal en datos que ya están clasificados o que están clasificados 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 problemas de optimización .
Análisis teorico
En el análisis teórico de algoritmos , la práctica habitual es estimar su complejidad en sentido asintótico. La notación más comúnmente utilizado para describir el consumo de recursos o "complejidad" es Donald Knuth 's notación Big O , lo 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 tiempo requerido para un algoritmo es proporcional a , omitiendo los términos de orden inferior que contribuyen menos de al crecimiento de la función como crece arbitrariamente grande . Esta estimación puede ser engañosa cuando es pequeño, pero generalmente lo suficientemente preciso 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 combinada cuando solo se van a ordenar unos pocos elementos; sin embargo, es probable que cualquiera de las implementaciones cumpla con los requisitos de desempeño para una lista pequeña. Por lo general, los programadores están interesados en algoritmos que escalan de manera eficiente a grandes tamaños de entrada, y se prefiere la clasificación por fusión sobre la clasificació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:
Notación | Nombre | Ejemplos de |
---|---|---|
constante | Encontrar la mediana a partir de una lista ordenada de medidas; Usando una tabla de búsqueda de tamaño constante ; Usar una función hash adecuada para buscar un artículo. | |
logarítmico | Encontrar un elemento 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 Binomial . | |
lineal | Encontrar un elemento en una lista sin clasificar o en un árbol con formato incorrecto (en el peor de los casos) o en una matriz sin clasificar; Sumando dos enteros de n bits por acarreo de ondulación . | |
lineal , loglineal o cuasilineal | Realización de una transformada rápida de Fourier ; heapsort , quicksort ( mejor y promedio de los casos ) o merge sort | |
cuadrático | Multiplicar dos números de n dígitos por un algoritmo simple ; clasificación de burbujas (en el peor de los casos o implementación ingenua), clasificación de Shell , clasificación rápida (en el peor de los casos ), clasificación por selección o clasificación por inserción | |
exponencial | Encontrar la solución óptima (no aproximada ) al problema del viajante de comercio utilizando programación dinámica ; determinar si dos declaraciones lógicas son equivalentes mediante la búsqueda de fuerza bruta |
Benchmarking: medir el desempeño
Para nuevas versiones de software o para proporcionar comparaciones con sistemas competitivos, 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 asegurarse de que al menos sea 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 del mainframe, ciertos productos de clasificació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 comparando 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 típicos de programación en varios lenguajes de programación.
Incluso la creación de evaluaciones 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 lo demuestra con el ejemplo un "Resumen de desempeño en nueve idiomas" de Christopher W. Cowell-Shah. [5]
Problemas de implementación
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 el algoritmo está realmente codificado, [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 está utilizando. 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 los problemas de tiempo o espacio, pero que pueden estar fuera del control del 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 , subprocesos múltiples (a nivel de hardware o software), multitarea simultánea y llamadas a subrutinas . [7]
Algunos procesadores tienen capacidades para el procesamiento de vectores , 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 los algoritmos diseñados para el procesamiento secuencial deban rediseñarse por completo para hacer uso del procesamiento en 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 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, 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 optimizar 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, lo que lo obliga a generar código o vincular una llamada de biblioteca externa para producir un resultado que de otro modo 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 los 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.
Medidas de uso de recursos
Las medidas se expresan normalmente en función del tamaño de la entrada. .
Las dos medidas más habituales son:
- Tiempo : ¿cuánto tarda el algoritmo en completarse?
- 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 en 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 la computadora.
- Consumo indirecto de energía : energía necesaria para refrigeración, iluminación, etc.
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 a menudo se conoce como informática ecológica .
Las medidas menos comunes de eficiencia computacional también pueden ser relevantes en algunos casos:
- Tamaño de transmisión : el ancho de banda podría ser un factor limitante. La compresión de datos se puede utilizar para reducir la cantidad de datos que se transmitirán. La visualización de una imagen o imagen (por ejemplo, el 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 informáticas vinculadas a E / S.
- Espacio externo : espacio necesario en un disco u otro dispositivo de memoria externo; esto podría ser para almacenamiento temporal mientras se lleva a cabo el algoritmo, o podría ser un almacenamiento a largo plazo que deba llevarse a cabo para referencia futura.
- 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.
Hora
Teoría
Analice el algoritmo, por lo general 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 se expresa normalmente utilizando Big O notación . 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 en paralelo pueden ser más difíciles de analizar .
Práctica
Utilice 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 los algoritmos de larga duración, el tiempo transcurrido también podría ser de interés. Por lo general, los resultados se deben promediar en varias pruebas.
Base de perfiles de gestión puede ser muy sensible a la configuración de hardware y la posibilidad de otros programas o tareas que se ejecutan al mismo tiempo en un multi-proceso y multi-programación medio ambiente.
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 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, 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 se expresa normalmente utilizando Big O notación .
Hay hasta cuatro aspectos del uso de la memoria a considerar:
- La cantidad de memoria necesaria para contener 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 la clasificación, a menudo reorganizan los datos de entrada y no necesitan espacio adicional para los datos de salida. Esta propiedad se conoce como 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 algoritmos que utilizan técnicas recursivas .
Las primeras computadoras electrónicas y las primeras computadoras hogareñas tenían cantidades relativamente pequeñas de memoria de trabajo. Por ejemplo, la Calculadora Automática de Almacenamiento con Retraso 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, es habitual 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.
Jerarquía de memoria caché y
Las computadoras actuales pueden tener cantidades relativamente grandes de memoria (posiblemente Gigabytes), por lo que tener que apretar 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 de registros , la más rápida de las tecnologías de memoria de computadora con la menor cantidad de espacio de almacenamiento. La mayoría de la computación directa en las computadoras modernas ocurre con los operandos de origen y destino en los registros antes de actualizarse a la caché, la memoria principal y la memoria virtual si es necesario. En un núcleo de procesador , hay típicamente del orden de cientos de bytes o menos de disponibilidad de registros, 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 caché es la segunda memoria más rápida y la segunda más pequeña disponible en la jerarquía de memoria. Los cachés están presentes en CPU, GPU, unidades de disco duro y periféricos externos, y generalmente se implementan en RAM estática . Los cachés de memoria tienen varios niveles ; los niveles inferiores son más grandes, más lentos y, por lo general, se comparten entre los núcleos de los procesadores de varios núcleos . Para procesar operandos en la memoria caché, una unidad de procesamiento debe recuperar los datos de la caché, realizar la operación en los registros y volver a escribir los datos en la caché. Esto opera a velocidades comparables (alrededor de 2 a 10 veces más lentas) con la unidad lógica aritmética o la unidad de punto flotante de la CPU o GPU si se encuentra en la caché L1 . [8] Es aproximadamente 10 veces más lento si hay un error de caché L1 y debe recuperarse y escribirse en el caché L2 , y 10 veces más lento si hay un error de caché L2 y debe recuperarse de un L3 caché , 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 (típicamente 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[actualizar], La RAM se implementa cada vez más en el chip de los procesadores, como CPU o memoria GPU .
- La memoria virtual se implementa con mayor frecuencia en términos de almacenamiento secundario , como un disco duro , y es una extensión de la jerarquía de memoria que tiene un espacio de almacenamiento mucho más grande pero una latencia mucho mayor, generalmente alrededor de 1000 veces más lenta que una pérdida de caché por un valor en RAM . [8] Aunque originalmente estaba motivado para crear la impresión de que había más memoria disponible de la que realmente estaba disponible, la memoria virtual es más importante en el uso contemporáneo por su compensación espacio-temporal 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 encajen en la memoria caché será mucho más rápido que un algoritmo que encaje 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 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 informática electrónica, si un algoritmo y sus datos no cabían en la memoria principal, el algoritmo no podía utilizarse. 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. Esto se denomina principio de localidad y se puede subdividir en localidad de referencia , localidad espacial y localidad temporal . Un algoritmo que no quepa completamente en la memoria caché pero que exhibe una localidad de referencia puede funcionar razonablemente bien.
Críticas al estado actual de la programación
- David May FRS, científico informático británico y actualmente profesor de informática en la Universidad de Bristol y fundador y director de tecnología de XMOS Semiconductor , cree que uno de los problemas es que se depende de la ley de Moore para resolver ineficiencias. Ha propuesto una "alternativa" a la ley de Moore (la ley de May ) declarada de la siguiente manera: [9]
La eficiencia del software se reduce a la mitad cada 18 meses, compensando la Ley de Moore
- May continúa diciendo:
En los sistemas ubicuos, reducir a la mitad las instrucciones ejecutadas puede duplicar la duración de la batería y los conjuntos de big data brindan grandes oportunidades para un mejor software y algoritmos: Reducir el número de operaciones de N x N a N x log (N) tiene un efecto dramático cuando N es grande ... para N = 30 mil millones, este cambio equivale a 50 años de mejoras tecnológicas.
- El autor de software Adam N. Rosenburg en su blog " El fracaso de la computadora digital ", ha descrito el estado actual de la programación como cercano al "horizonte de eventos del software", (en alusión al " horizonte de eventos del calzado " ficticio descrito por Douglas Adams en su Guía del autoestopista galáctico libro [10] ). Estima que ha habido un factor de 70 dB de pérdida de productividad o "99,99999 por ciento, de su capacidad para entregar los productos", desde la década de 1980, "Cuando Arthur C. Clarke comparó la realidad de la informática en 2001 con la computadora HAL 9000 en su libro 2001: A Space Odyssey , señaló lo maravillosamente pequeñas y poderosas que eran las computadoras, pero lo decepcionante que se había vuelto la programación de computadoras ".
Concursos por los mejores algoritmos
Los siguientes concursos invitan a participar para los mejores algoritmos basados en algunos criterios arbitrarios decididos por los jueces:
- Revista con cable [11]
Ver también
- Análisis de algoritmos: cómo determinar los recursos que necesita un algoritmo.
- Codificación aritmética: una forma de codificación de entropía de longitud variable para una compresión de datos eficiente
- Matriz asociativa: una estructura de datos que se puede hacer más eficiente utilizando árboles Patricia o matrices Judy
- 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
- Algoritmo de búsqueda binaria: una técnica simple y eficiente para buscar arreglos ordenados
- Tabla de ramas: una técnica para reducir la longitud de la ruta de instrucción, el tamaño del código de máquina (y, a menudo, también la memoria).
- Comparación de paradigmas de programación : consideraciones de rendimiento específicas del paradigma
- Optimización del compilador: optimización derivada del compilador
- Complejidad computacional de operaciones matemáticas
- Teoría de la complejidad computacional
- Rendimiento de la computadora : métricas de hardware de la computadora
- Compresión de datos: reducción del ancho de banda de transmisión y el almacenamiento en disco
- Índice de base de datos: una estructura de datos que mejora la velocidad de las operaciones de recuperación de datos en una tabla de base de datos.
- Codificación de entropía: codificación de datos de manera eficiente utilizando la frecuencia de aparición de cadenas como criterio de sustitución.
- Recolección de basura: liberación automática de memoria después de su uso
- Computación verde: un movimiento para implementar tecnologías 'más ecológicas', consumiendo menos recursos
- Algoritmo de Huffman: un algoritmo para una codificación de datos eficiente
- Mejora del rendimiento del código administrado: Microsoft MSDN Library
- Localidad de referencia: para evitar retrasos en el almacenamiento en caché causados por el acceso a la memoria no local.
- Optimización de bucle
- Gestión de la memoria
- Optimización (informática)
- Análisis de rendimiento: métodos para medir el rendimiento real de un algoritmo en tiempo de ejecución.
- Computación en tiempo real: otros ejemplos de aplicaciones de tiempo crítico
- Análisis del tiempo de ejecución: estimación de los tiempos de ejecución esperados y la escalabilidad de un algoritmo
- Múltiples subprocesos simultáneos
- Algoritmo de clasificación § Comparación de algoritmos
- Ejecución especulativa o ejecución ansiosa
- Predicción de rama
- Superhilo
- Hyper-threading
- Código enhebrado: similar a la tabla de método virtual o la tabla de rama
- Tabla de métodos virtuales: tabla de sucursales con punteros asignados dinámicamente para el envío.
Referencias
- ^ Green, Christopher, Classics in the History of Psychology , consultado el 19 de mayo de 2013
- ^ Knuth, Donald (1974), "Programación estructurada con declaraciones de referencia" (PDF) , Computing Surveys , 6 (4): 261–301, CiteSeerX 10.1.1.103.6084 , doi : 10.1145 / 356635.356640 , S2CID 207630080 , archivado desde el original (PDF) el 24 de agosto de 2009 , consultado el 19 de mayo de 2013
- ^ a b "Punto de referencia de punto flotante: comparación de idiomas (Fourmilog: Ninguno se atreve a llamarlo razón)" . Fourmilab.ch. 4 de agosto de 2005 . Consultado el 14 de diciembre de 2011 .
- ^ "Historia de referencia de Whetstone" . Roylongbottom.org.uk . Consultado el 14 de diciembre de 2011 .
- ^ Personal de OSNews. "Resumen de rendimiento de nueve idiomas: evaluación comparativa de matemáticas y E / S de archivos" . www.osnews.com . Consultado el 18 de septiembre de 2018 .
- ^ Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación en tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Sistemas de conocimiento e información . 52 (2): 341–378. doi : 10.1007 / s10115-016-1004-2 . ISSN 0219-1377 . S2CID 40772241 .
- ^ Guy Lewis Steele, Jr. "Desmentir el mito de 'Llamada a procedimiento costoso', o implementaciones de llamadas a procedimiento consideradas perjudiciales, o Lambda: The Ultimate GOTO". Laboratorio de IA del MIT. Nota de laboratorio de IA AIM-443. Octubre de 1977. [1]
- ^ a b c d Hennessy, John L; Patterson, David A; Asanović, Krste; Bakos, Jason D; Colwell, Robert P; Bhattacharjee, Abhishek; Conte, Thomas M; Duato, José; Franklin, Diana; Goldberg, David; Jouppi, Norman P ; Li, Sheng; Muralimanohar, Naveen; Peterson, Gregory D; Pinkston, Timothy Mark; Ranganathan, Prakash; Wood, David Allen; Young, Clifford; Zaky, Amr (2011). Arquitectura informática: un enfoque cuantitativo (Sexta ed.). ISBN 978-0128119051. OCLC 983459758 .
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 3 de marzo de 2016 . Consultado el 23 de febrero de 2009 .CS1 maint: copia archivada como título ( enlace )
- ^ "El fracaso de la computadora digital" .
- ^ Fagone, Jason (29 de noviembre de 2010). "Los matemáticos adolescentes batallan en los Juegos Olímpicos de algoritmos" . Cableado .
enlaces externos
- Animación del algoritmo de Boyer-Moore ( Java Applet )
- "Cómo los algoritmos dan forma a nuestro mundo". Una charla TED (conferencia) de Kevin Slavin.
- Conceptos erróneos sobre la eficiencia algorítmica en las escuelas secundarias