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

[Kiko]

El 4 de marzo de 2010 16:27, Olemis Lang (Simelix)
<olemis+py en gmail.com<olemis%2Bpy en gmail.com>
> escribió:

> 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
>

Después de leeros a todos (muchas gracias, Juan Ignacio, Daniel, Pablo,
Olemis y Arnau)  he hecho unas pruebas para un caso que se acerca a lo que
necesito:

from datetime import datetime, timedelta
import bisect
import time

def generador(start, end, intervalo):
    fechas = []
    while start <= end:
        fechas.append(start)
        start += timedelta(minutes=intervalo)
    return [valores for valores in fechas]

start = datetime(1900,1,1,0,0)
end = datetime(1901,1,1,0,0)

conjunto = generador(start, end, 10)
subconjunto = generador (start, end, 30)


t0 = time.time()
indices = []
ultimo = -1
for i in subconjunto:
    ultimo = conjunto.index(i, ultimo+1)
    indices.append(ultimo)
    #yield ultimo
print time.time() - t0
print indices[0:25]

t0 = time.time()
indices1 = [conjunto.index(i) for i in subconjunto]
print time.time() - t0
print indices1[0:25]

t0 = time.time()
indices2 = [bisect.bisect(conjunto, i) for i in subconjunto]
print time.time() - t0
print indices2[0:25]

El yield me da error tal como lo he puesto ¿?.

Las salidas que obtengo son:

tiempo de la primera opción: 0.0149998664856
for i in subconjunto:
    ultimo = conjunto.index(i, ultimo+1)
    indices.append(ultimo)
Los primero 25 valores de indices = [0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30,
33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72]

tiempo de mi opción, la original: 41.2180001736
indices1 = [conjunto.index(i) for i in subconjunto]
Los primero 25 valores de indices1 = [0, 3, 6, 9, 12, 15, 18, 21, 24, 27,
30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72]

tiempo de la tercera opción: 0.0469999313354
indices2 = [bisect.bisect(conjunto, i) for i in subconjunto]
Los primero 25 valores de indices2 = [1, 4, 7, 10, 13, 16, 19, 22, 25, 28,
31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73]

Menos mal que he preguntado a los expertos.

Muchas gracias por las mejoras. Tanto la primera opción como la tercera son
infinitamente mejores que la mía y aceptables en tiempo usado.
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20100304/c8e1e27b/attachment.html>