[Python-es] OT: El límite entre la teoría y la práctica con Python WAS: Buscar índices de un array (que cumple condición) de forma eficiente

[Olemis Lang (Simelix)]

2010/3/4 Olemis Lang (Simelix) <olemis+py en gmail.com>:
> 2010/3/4 Pablo Angulo <pablo.angulo en uam.es>:
>> Daniel Garcia Moreno escribió:
>>>
>>>> Si la lista grande tiene N elementos y la pequeña M, puedes elegir entre
>>>> O(Mlog(N)), usando bisect. o O(N), con la técnica que te decía antes.
>>>>
>>> O puedes combinar las dos, buscar desde el último indice en adelante
>>> pero hacerlo con busqueda binaria.
>> Yo diría que ésto es también es O(M log(N)) en el peor caso (cuando el
>> subconjunto son los M primeros valores de conjunto)
>>
>> log(N)+log(N-1)+...+log(N-M)=O(M log(N))
>
[...]
>
> PD: De todas formas mi sugerencia muy particular es que no confíen
> demasiado en los análisis teóricos del tipo mencionado por Pablo (o
> mejor dicho, que desconfíen hasta que no tengan la seguridad
> irrefutable que les da un profiler ;o) . Este hilo me ha recordado un
> artículo que tengo pendiente para mi blog que ilustra esto muy bien (y
> que resulta realmente sorprendente, créanme ;o). Trataré de publicarlo
> mañana (o pasado, o ...), y así tendrán más argumentos para juzgar
> ustedes por su cuenta
>

Como les había comentado ya, acabo de publicar un artículo [1]_ que
ilustra porque es preciso tener mucho cuidado con los análisis
teóricos al estimar posibles tiempos de ejecución en entornos
prácticos (esto es sólo una parte de todo el posible análisis, claro
;o)

Espero que les sea interesante, y que les sirva para tener más
precisión cuando estimen la eficiencia de cierto(s) algoritmos

;o)

.. [1] La cara oculta de Fibonacci (en Python)
         (http://simelo-es.blogspot.com/2010/03/la-cara-oculta-de-fibonacci-en-python.html)

-- 
Regards,

Olemis.

Blog ES: http://simelo-es.blogspot.com/
Blog EN: http://simelo-en.blogspot.com/

Featured article:
Comienza la era de la televisión 3D (el 10 de marzo ;o) -
http://feedproxy.google.com/~r/simelo-es/~3/mPcmLbduWJU/despues-del-gran-exito-del-largometraje.html