Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Arnau Sanchez 

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
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Olemis Lang (Simelix) 
2010/3/4 Arnau Sanchez pyar...@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
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Kiko 
El 4 de marzo de 2010 16:27, Olemis Lang (Simelix)
olemis...@gmail.comolemis%2...@gmail.com
 escribió:

 2010/3/4 Arnau Sanchez pyar...@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.046313354
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.
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Olemis Lang (Simelix) 
2010/3/4 Kiko kikocorre...@gmail.com:
 El 4 de marzo de 2010 16:27, Olemis Lang (Simelix) olemis...@gmail.com
 escribió:
 2010/3/4 Arnau Sanchez pyar...@gmail.com:
  On 04/03/10 14:02, Pablo Angulo wrote:
 

[...]

 tiempo de la tercera opción: 0.046313354
 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]


Evidentemente hay que ajustar este ;o)

-- 
Regards,

Olemis.

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

Featured article:
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Olemis Lang (Simelix) 
2010/3/4 Pablo Angulo pablo.ang...@uam.es:
 Olemis Lang (Simelix) escribió:
 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)


 index no es O(1), sino que tarda tanto como tenga que buscar. Si tiene
 que recorrer toda la lista, será O(n). En este caso, el tiempo total es
 O(n) porque no se pasa dos veces por el mismo elemento de conjunto, pero
 eso no significa que index sea O(1).

Si no es O(1) entonces sospecho que en

{{{
#!python

ultimo = -1
 for v in subconjunto:
 ultimo = conjunto.index(v, ultimo+1)
 yield ultimo
}}}

hay un ciclo `for` explícito más un ciclo implícito `index`, lo que me
hace pensar que el desempeño en el peor caso puede ser O(M * N) y en
el mejor sospecho que sea O(M^2), solo que hay una realidad, el ciclo
implícito es mucho más eficiente pues está implementado directamente
en (C)Python

CMIIW

;o)

-- 
Regards,

Olemis.

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

Featured article:
Support micro-seconds as added by Trac in revision 9210 for upcoming
0.12... - http://bitbucket.org/osimons/trac-rpc-mq/changeset/62ffe719a84a/
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Kiko 
El 4 de marzo de 2010 17:33, Pablo Angulo pablo.ang...@uam.es escribió:

 Kiko escribió:
  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.046313354
  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.
 Las mediciones de tiempo hay que tomarlas con cautela: si subconjunto es
 mucho más pequeño que conjunto, entonces Mlog(N) es menor que N, y te
 interesa usar el tercer método.
 ___
 Python-es mailing list
 Python-es@python.org
 http://mail.python.org/mailman/listinfo/python-es
 FAQ: http://python-es-faq.wikidot.com/


De acuerdo contigo.

Pero con este ejercicio, lo que queda claro es que cualquiera de las dos
propuestas es infinitamente mejor que la inicial (la mía) en tiempo de
cálculo y ambas aceptables para lo que necesito ahora mismo.
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/

Re: [Python-es] Buscar índices de un array (que cu mple condición) de forma eficiente

2010-03-04 Por tema Arnau Sanchez 

On 04/03/10 16:43, Kiko wrote:


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



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


Claro, un yield sólo funciona dentro de un generador. Supongo que nunca has 
trabajado con ellos, busca información por google, por ejemplo:


http://docs.python.org.ar/tutorial/classes.html#generadores

De verdad que vale la pena, los generadores son una de las herramientas más 
potentes de Python. Para crear un generator tendrás que definirlo (también con 
def, aunque no es una función). En nuestro ejemplo:


def gen():
  ultimo = -1
  for v in subgroup:
  ultimo = group.index(v, ultimo+1)
  yield ultimo

Si haces gen() verás que devuelve (inmediatamente, ya que no lo ha ejecutado 
todavía) un objeto generador, no una lista; siempre puedes obtener el resultado 
completo en forma de lista, así: list(gen()). Pero muchas veces uno no quiere 
tener toda la lista, sólo iterar (una vez) sobre el resultado. En ese caso:


for item in gen():
  # hacer algo con item

Por último: Daniel proponía usar bisect; con la misma idea, y refactorizando un 
pelín, quedaría así:


def get_positions(group, subgroup):
  index = 0
  for element in subgroup:
  index = bisect.bisect(group, element, index)
  yield index-1

arnau
___
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/