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

[Daniel Garcia Moreno]

2010/3/4 Kiko <kikocorreoso en gmail.com>:
> Hola a todos.
>
> Estoy intentando buscar los indices de un subconjunto dentro de un conjunto
> y quiero saber si existe algo más eficiente que lo que he pensado.
>
> Me explico, por ejemplo, yo tengo:
>
> conjunto = range(1000, 1100, 1)
> subconjunto = range(1000, 1100, 3)
>
> Quiero saber la posición que tendría cada valor del subconjunto en el
> conjunto, es decir, subconjunto[0] tendría el índice 0 en conjunto
> (conjunto[0])), subconjunto[1] tendría el índice 3 en conjunto
> (conjunto[3])) y así.
>
> Estoy obteniendo los índices así
> indices = [conjunto.index(valor) for valor in subconjunto]
>
> Pero si conjunto y subconjunto son muy grandes se toma su tiempo.
>
> ¿Existe una forma más eficiente de obtener los índices?
>
> Muchas gracias a todos.
>

Según mis conocimientos en computación, esta búsqueda es de orden n^2.
Si el primer conjunto está ordenado, puede llegar a ser de orden
n*log(n) puesto que puedes hacer una búsqueda binaria en lugar de
conjunto.index(valor). Y creo que no vas a poder optimizar más por
ahí, porque la complejidad del problema es esa.