Hispanopedia Wiki
Articulo de referencia

Algoritmia empírica

En informática , la algorítmica empírica (o algorítmica experimental ) es la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos . La prácti...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , la algorítmica empírica (o algorítmica experimental ) es la práctica de utilizar métodos empíricos para estudiar el comportamiento de los algoritmos . La práctica combina el desarrollo de algoritmos y la experimentación: los algoritmos no solo se diseñan, sino que también se implementan y se prueban en una variedad de situaciones. En este proceso, se analiza un diseño inicial de un algoritmo para que el algoritmo pueda desarrollarse de manera gradual. [1]

Descripción general

Los métodos de la algorítmica empírica complementan los métodos teóricos para el análisis de algoritmos . [2] A través de la aplicación basada en principios de métodos empíricos, particularmente de la estadística , a menudo es posible obtener información sobre el comportamiento de algoritmos como algoritmos heurísticos de alto rendimiento para problemas combinatorios difíciles que son (actualmente) inaccesibles al análisis teórico. [3] Los métodos empíricos también se pueden utilizar para lograr mejoras sustanciales en la eficiencia algorítmica . [4]

La científica informática estadounidense Catherine McGeoch identifica dos ramas principales de la algorítmica empírica: la primera (conocida como análisis empírico ) se ocupa del análisis y la caracterización del comportamiento de los algoritmos , y la segunda (conocida como diseño de algoritmos o ingeniería de algoritmos ) se centra en los métodos empíricos para mejorar el rendimiento de los algoritmos . [5] La primera a menudo se basa en técnicas y herramientas de la estadística , mientras que la segunda se basa en enfoques de la estadística , el aprendizaje automático y la optimización . Las herramientas de análisis dinámico , típicamente los perfiladores de rendimiento , se utilizan comúnmente cuando se aplican métodos empíricos para la selección y el refinamiento de algoritmos de varios tipos para su uso en varios contextos. [6] [7] [8]

Las investigaciones sobre algoritmos empíricos se publican en varias revistas, entre ellas, ACM Journal on Experimental Algorithmics (JEA) y Journal of Artificial Intelligence Research (JAIR). Además de Catherine McGeoch, entre los investigadores más conocidos en algoritmos empíricos se incluyen Bernard Moret , Giuseppe F. Italiano , Holger H. Hoos , David S. Johnson y Roberto Battiti . [9]

Perfiles de rendimiento en el diseño de algoritmos complejos

En ausencia de algoritmos empíricos, el análisis de la complejidad de un algoritmo puede implicar varios métodos teóricos aplicables a varias situaciones en las que se puede utilizar el algoritmo. [10] Las consideraciones sobre la memoria y la memoria caché suelen ser factores importantes a tener en cuenta en la elección teórica de un algoritmo complejo, o el enfoque para su optimización, para un propósito determinado. [11] [12] La elaboración de perfiles de rendimiento es una técnica de análisis de programas dinámicos que se utiliza normalmente para encontrar y analizar cuellos de botella en el código de una aplicación completa [13] [14] [15] o para analizar una aplicación completa para identificar código de bajo rendimiento. [16] Un generador de perfiles puede revelar el código más relevante para los problemas de rendimiento de una aplicación. [17]

Un generador de perfiles puede ayudar a determinar cuándo elegir un algoritmo sobre otro en una situación particular. [18] Cuando se crea un perfil de un algoritmo individual, como en el análisis de complejidad, las consideraciones sobre la memoria y la caché suelen ser más importantes que los recuentos de instrucciones o los ciclos de reloj; sin embargo, los hallazgos del generador de perfiles se pueden considerar a la luz de cómo el algoritmo accede a los datos en lugar de la cantidad de instrucciones que utiliza. [19]

La elaboración de perfiles puede proporcionar una visión intuitiva del comportamiento de un algoritmo [20] al revelar los hallazgos de rendimiento como una representación visual. [21] La elaboración de perfiles de rendimiento se ha aplicado, por ejemplo, durante el desarrollo de algoritmos para hacer coincidir comodines . Los primeros algoritmos para hacer coincidir comodines, como el algoritmo wildmat de Rich Salz , [22] generalmente se basaban en la recursión , una técnica criticada por motivos de rendimiento. [23] El algoritmo de comodines de coincidencia de Krauss se desarrolló en base a un intento de formular una alternativa no recursiva utilizando casos de prueba [24] seguido de optimizaciones sugeridas a través de la elaboración de perfiles de rendimiento, [25] lo que resultó en una nueva estrategia algorítmica concebida a la luz de la elaboración de perfiles junto con otras consideraciones. [26] Los perfiladores que recopilan datos a nivel de bloques básicos [27] o que dependen de la asistencia de hardware [28] brindan resultados que pueden ser lo suficientemente precisos para ayudar a los desarrolladores de software a optimizar algoritmos para una computadora o situación en particular. [29] La elaboración de perfiles de rendimiento puede ayudar a los desarrolladores a comprender las características de los algoritmos complejos aplicados en situaciones complejas, como los algoritmos coevolutivos aplicados a problemas arbitrarios basados ​​en pruebas, y puede ayudar a generar mejoras en el diseño. [30]

Véase también

Referencias

  1. ^ Fleischer, Rudolf; et al., eds. (2002). Algoritmia experimental: del diseño de algoritmos al software robusto y eficiente. Springer International Publishing AG.
  2. ^ Moret, Bernard ME (1999). Hacia una disciplina de algorítmica experimental . Serie DIMACS en matemáticas discretas y ciencias de la computación teóricas. Vol. 59. Serie DIMACS en matemáticas discretas y ciencias de la computación teóricas. págs. 197–213. doi :10.1090/dimacs/059/10. ISBN 9780821828922. Número de identificación del sujeto  2221596.
  3. ^ Hromkovic, Juraj (2004). Algoritmia para problemas difíciles. Springer International Publishing AG.
  4. ^ Guzmán, John Paul; Limoanco, Teresita (2017). "Un enfoque empírico para el análisis de algoritmos que da como resultado aproximaciones a la complejidad temporal Big Theta" (PDF) . Journal of Software . 12 (12).
  5. ^ McGeoch, Catherine (2012). Una guía para la algorítmica experimental . Cambridge University Press. ISBN 978-1-107-00173-2.
  6. ^ Coppa, Emilio; Demetrescu, Camil; Finocchi, Irene (2014). "Perfiles sensibles a la entrada". Transacciones IEEE sobre ingeniería de software . 40 (12): 1185-1205. CiteSeerX 10.1.1.707.4347 . doi :10.1109/TSE.2014.2339825. 
  7. ^ Moret, Bernard ME; Bader, David A.; Warnow, Tandy (2002). "Ingeniería de algoritmos de alto rendimiento para la filogenética computacional" (PDF) . The Journal of Supercomputing . 22 (1): 99–111. doi :10.1023/a:1014362705613. S2CID  614550.
  8. ^ Zaparanuks, Dmitrijs; Hauswirth, Matthias (2012). Perfiles algorítmicos . 33.ª Conferencia ACM SIGPLAN sobre diseño e implementación de lenguajes de programación . Biblioteca digital ACM. págs. 67–76. CiteSeerX 10.1.1.459.4913 . 
  9. ^ "Sobre algorítmica experimental: una entrevista con Catherine McGeoch y Bernard Moret". Ubiquity . 2011 (agosto). Biblioteca Digital ACM. 2011.
  10. ^ Grzegorz, Mirek (2018). "Gran ambigüedad". código de rendimiento_.
  11. ^ Kölker, Jonas (2009). "¿Cuándo falla la notación Big-O?". Desbordamiento de pila .
  12. ^ Lemire, Daniel (2013). "Notación Big-O y rendimiento en el mundo real". WordPress.
  13. ^ "Cómo encontrar cuellos de botella en las aplicaciones". Ayuda de dotTrace 2018.1 . JetBrains. 2018.
  14. ^ Shmeltzer, Shay (2005). "Localización de cuellos de botella en el código con el generador de perfiles de eventos". Documentación de Oracle Technology Network JDeveloper . Oracle Corp.
  15. ^ Shen, Du; Poshyvanyk, Denys; Luo, Qi; Grechanik, Mark (2015). "Automatización de la detección de cuellos de botella en el rendimiento mediante la creación de perfiles de aplicaciones basados ​​en búsquedas" (PDF) . Actas del Simposio Internacional de 2015 sobre Pruebas y Análisis de Software . Biblioteca Digital ACM. págs. 270–281. doi :10.1145/2771783.2771816. ISBN . 9781450336208.S2CID8625903  .​
  16. ^ "Perfiles de rendimiento y memoria y cobertura de código". Centro de aprendizaje de perfiles . SmartBear Software. 2018.
  17. ^ Janssen, Thorben (2017). "11 consejos sencillos para optimizar el rendimiento de Java". Consejos, trucos y recursos para desarrolladores de Stackify .
  18. ^ O'Sullivan, Bryan; Stewart, Don; Goerzen, John (2008). "25. Creación de perfiles y optimización". Real World Haskell . O'Reilly Media.
  19. ^ Linden, Doug (2007). "Elaboración de perfiles y optimización". Wiki de Second Life.
  20. ^ Pattis, Richard E. (2007). "Análisis de algoritmos, Programación avanzada/Práctica, 15-200". Facultad de Ciencias de la Computación, Universidad Carnegie Mellon.
  21. ^ Wickham, Hadley (2014). "Optimización de código". Advanced R. Chapman y Hall/CRC.
  22. ^ Salz, rico (1991). "salvajemat.c". GitHub .
  23. ^ Cantatore, Alessandro (2003). "Algoritmos de coincidencia de comodines".
  24. ^ Krauss, Kirk (2008). "Coincidencia de comodines: un algoritmo". Diario del Dr. Dobb .
  25. ^ Krauss, Kirk (2014). "Coincidencia de comodines: una forma empírica de dominar un algoritmo". Diario del Dr. Dobb .
  26. ^ Krauss, Kirk (2018). "Coincidencia de comodines: un algoritmo mejorado para big data". Desarrollo para el rendimiento.
  27. ^ Grehan, Rick (2005). "Perfiles de código: elección de una herramienta para analizar el rendimiento" (PDF) . Freescale Semiconductor.Si, por otro lado, necesita recorrer su código con precisión microscópica, afinando instrucciones individuales de la máquina, entonces un generador de perfiles activo con conteo de ciclos es inmejorable.
  28. ^ Hough, Richard; et al. (2006). "Evaluación del rendimiento de la microarquitectura con precisión de ciclo". Actas del taller sobre arquitectura introspectiva . Instituto Tecnológico de Georgia. CiteSeerX 10.1.1.395.9306 . 
  29. ^ Khamparia, Aditya; Banu, Saira (2013). Análisis de programas con herramientas de rendimiento y pines de instrumentación dinámica. Conferencia internacional IEEE sobre tendencias emergentes en informática, comunicación y nanotecnología . Biblioteca digital IEEE Xplore.
  30. ^ Jaskowski, Wojciech; Liskowski, Pawel; Szubert, Marcin Grzegorz; Krawiec, Krzysztof (2016). "El perfil de desempeño: un método de evaluación del desempeño multicriterio para problemas basados ​​en pruebas" (PDF) . Matemática Aplicada e Informática . 26 . De Gruyter: 216.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Algoritmos_empíricos&oldid=1194883679"