Leía hace unos días el artículo algorithmic complexity attacks and libc qsort() donde se hace un análisis del Quick Sort, lo que pueden costar algunas de sus implementaciones y fantasea con la posiblidad de utilizarlo para algún tipo de ataque de denegación de servicio (o al menos ralentización).
Son de esas cosas que nos trae el software libre e internet.
Una de las diferencias entre alguien que resuelve problemas y un buen desarrollador está en si es capaz de analizar cómo de buena es la solución que propone o no. A veces nos mareamos (y mareamos a otros) haciendo micro-optimizaciones sin habernos parado a pensar dónde ni cómo es la forma más adecuada de hacerlo.
En A Gentle Introduction to Algorithm Complexity Analysis podemos leer las ideas básicas sobre el tema, que nos abrirían la puerta a empezar a pensar en un algoritmo como un todo y no como un conjunto de instrucciones más o menos afortunadas.
La optimización del código que se ejecuta en nuestros programas es un tema clave (y con el que hay que tener cuidado sobre todo antes de tiempo).
Por eso me gustó leer A Python Optimization Anecdote donde nos cuentan los pasos seguidos para mejorar una función para evitar Cross-Sie scripting en Dropbox.
En resumen: probar, medir (y para eso hay que tener casos de prueba *nuestras pruebas, nuestros datos*) y ver cómo afecta a nuestro código con nuestros datos los cambios que hagamos:
Conclusions
The first, most basic conclusion is that the basic facts of Python
optimization inline functions, use implicit loops, move computation into C
if possible are perfectly valid. Another fact: Python dictionaries are
*fast*. The WHITELIST set and the CACHE_HTML_ESCAPES dict both rely on the
superb hash table implementation for their performance gains.Other “common wisdom”, like using locals instead of globals, yields
relatively little gain.Optimizing inner loops in a high-level loops requires lots of trial and
error. It was absolutely amazing that moving to string concatenation from
string interpolation gave such a huge boost to performance.Finally, measurement is key. It was measurement that told us that HTML
escaping was slow to begin with; and without measuring performance, we
would never have guessed that string interpolation was so slow.
La respuesta en why GNU grep is fast y lo explica haciendo referencia a los aspectos técnicos pero sin meterse mucho en los detalles.
Esencialmente:
Se utiliza el algoritmo de Boyer-Moore, que tiene como ventaja que evita mirar los bytes uno a uno, porque es capaz de evitar algunos basándose en información sobre lo que se busca (letra final, tamaño y aprovechándolo para dar saltos más grandes).
Pocas operaciones sobre cada byte de los que realmente se miran.
Además, el bucle interno está ‘desenrollado‘, lo que le evita algunas operaciones extra (las de control del propio bucle, claro). También evita pensar en líneas (salvo cuando ‘cree’ que ha podido encontrar lo que buscaba y trata de gestionar mejor la memoria para que la lectura sea más eficiente.
¿Alguien se anima a echarle un ojo al código?
En Galactic Algorithms nos hablan de una forma de llamar a esos algoritmos que tienen un buen coste asintótico pero que no los usarísmoa para calcular nada: Dick Lipton comenta como es un gran avance el ser capaces de predecir el comportamiento de un algoritmo sin ejecutarlo. También que hay algoritmos que son un gran descubrimiento aunque luego no se utilicen en el ‘mundo real’, por motivos como: descubrir nuevas técnicas, ser utilizables en el futuro si algunos paradigmas de computación cambian, abrir la puerta a otros algoritmos que sí son utilizables, o descubrirnos que algunos cotas temporales de algunos son excesivas (un programa costoso, pero con una cota polinómica cambiaría las ideas previas sobre determinados problemas, por ejemplo).
Uno que entra en esta categoría podría ser el de divide y vencerás para multiplicar matrices grandes, el algoritmo de Strassen.
En You Don’t Need Math Skills To Be A Good Developer But You Do Need Them To Be A Great One hablan justamente de eso: no es lo mismo alguien que programa sistemas sencillo que alguien que puede enfrentarse a otros tipos de problemas y enfrentarse a nuevos retos. Naturalmente, las matemáticas son importantes pero también (y aquí barro para casa) algoritmia y otros problemas que no son sólo programar razonablemente, sino que tienen otro contenido más amplio.
Vi la referencia en Math Skills For Programmers — Necessary Or Not?.
Y me viene bien para completarla la entrada del otro día en Informáticos en riesgo de exclusión social donde se abunda en el tema, hablando de los problemas de adaptación de algunos profesionales:
Está claro que, tanto como si estás empezando tu carrera profesional, como si estás en mitad de ella, tienes que tener en cuenta cual va a ser tu plan de carrera para el final de la misma o te arriesgas a quedarte en una situación bastante complicada para conseguir terminar tu carrera como informático. Parece que estamos condenados a meternos en gestión, a dirigirnos al área comercial o el marketing, si no, nos convertiremos en un sector de riesgo de exclusión social.
Aunque no veo la gestión o las otras áreas una condena sino una evolución que dan tantos otros profesionales de otros perfiles técnicos que descubren nuevas vocaciones en su contacto con la empresa.
De hecho, pienso que otro gallo le cantaría a la informática si más informáticos (con formación técnica sólida) dieran el paso a puestos de gestión.
Eso sí, si preferimos la parte técnica, desde luego ya podemos olvidarnos de vivir toda la vida de la misma tecnología.
Mbpfernand0's Blog 