[Python-es] Buscar índices de un array (que cumple condición) de forma eficiente

[Olemis Lang (Simelix)]

2010/3/4 Arnau Sanchez <pyarnau en gmail.com>:
> On 04/03/10 14:02, Pablo Angulo wrote:
>
>> indices = []
>> ultimo = 0
>> for v in subconjunto:
>>     ultimo += conjunto.index(v,ultimo)
>>     indices.append(ultimo)
>
> Creo que el += sobra, list.index() devuelve el índice absoluto:
>
>  ultimo = conjunto.index(v, ultimo)
>
> Y si no me equivoco el índice podría ser ultimo+1. Con tu propuesta, y
> usando generadores queda realmente simple:
>
>  ultimo = -1
>  for v in subconjunto:
>      ultimo = conjunto.index(v, ultimo+1)
>      yield ultimo

Aquí por ejemplo hay un caso que ilustra el hecho de no confiar
demasiado en las estimaciones teóricas . Las estimaciones de Pablo et
al se pueden ver afectadas por la eficiencia de la implementación del
método index (el cual no me parece que sea muy O(1) que digamos, pero
no tengo los detalles en la mano ...) . E.g. si fuera O(n), O(log(n))
... en el peor caso entonces todos los análisis anteriores no serían
del todo precisos (CMIIW)

PD: JFYI, la implementación que envié anteriormente no sufre de este
potencial problema (de todas formas sería bueno saber si `index` es
O(1) o no ;o)

-- 
Regards,

Olemis.

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

Featured article:
Robots activos para Google Wave: introducción a la versión 2 de la API
- http://feedproxy.google.com/~r/simelo-es/~3/ltPGNuqYzOM/google-wave-developer-blog-introducing.html