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.
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.
Mbpfernand0's Blog 