[bcn-pm] Complejidad de algoritmos

[Salvador Fandiño]

Enrique Nell wrote:
> Hola Alex
> 
>> Jo conec un profiler que segurament no és tan potent com el que
>> tu vols però que potser et serveix per començar (és útil per saber
>> en quins punts del codi es perd més temps i per tant quins punts
>> caldria optimitzar):  http://search.cpan.org/dist/DProf/
> 
> Sí, pero lo que me interesa es obtener una estimación del tiempo
> aproximado que tardará en ejecutarse un algoritmo, independientemente
> de su eficiencia. Por ejemplo, si hago un programa que realiza algún
> tipo de operación con arrays de cadenas y lo pruebo con tamaños de
> arrays razonables, quiero poder indicar al típico individuo arrojado
> (como yo en mi juventud) cuánto tardará en procesar un tamaño
> razonable x 1000 antes de que lo intente, por si no le conviniera, o
> directamente impedírselo.

Hola Enrique,

Puedes, establecer un modelo matematico para la complejidad de tu 
algoritmo y con algunos benchmarks ajustarlo.

Por ejemplo, si tienes un script que ordena algo, tipicamente su 
complejidad sera O(NlogN), osea, que el tiempo que tardara en ejecutarse 
es una funcion

    t(n) = A + B * n + C * n log n

Si mides los tiempos de ejecucion del script para distintos valores de 
n, tendras un conjunto de pares (n1, t1), (n2, t2)...(nm, tm) con los 
cuales podras ajustar los valores de A, B y C minimizando el error.

Luego, podras calcular el tiempo de ejecucion estimado de tu script, sin 
mas que calcular t(n) para el n que quieras.

De todas formas, al final se trata de una extrapolacion, y como el 
modelo matematico utilizado es muy simple los resultados solo seran 
validos en un entorno limitado. Osea, que si haces benchmarks para n = 
1, 2, 4, 8, 16, 32, 64 y 128, probablemente, el resultado que obtengas 
para n = 256, 512 o 1024 no se aleje mucho de la realidad, pero para n = 
1_000_000 es probable que no tenga nada que ver.

Tambien tienes que considerar que como comentaban en otro correo, los 
tama~nos de memoria de cache, RAM y swap tambien afectan a la velocidad 
de un algoritmo. La misma aproximacion que comentaba antes puede ser 
utilizada para estimar el consumo de memoria.

- Salva




> 
> Enric
> _______________________________________________
> llista dels Barcelona-pm
> Barcelona-pm en pm.org
> http://mail.pm.org/mailman/listinfo/barcelona-pm
> BCN Perl Mongers: http://barcelona.pm.org
>