Re: [Python-es] Buscar índices de un array (que cump le condición) de forma eficiente
2010/3/4 Kiko : > 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. ___ 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 cump le condición) de forma eficiente
2010/3/4 Kiko : > > El 4 de marzo de 2010 13:18, Juan Ignacio escribió: >> >> Oppps, me falto la interrogante, era una pregunta :-) ¿Conjunto y >> subconjunto están (o pueden estar) ordenados? > > Están ordenados para lo que quiero hacer. > Pues entonces puedes usar bisect en lugar de index: import bisect indices = [bisect.bisect(conjunto, valor) for valor in subconjunto] ___ 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 cump le condición) de forma eficiente
Kiko escribió: > 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? si sabes que los elementos del subconjunto están ordenados dentro del conjunto, no necesitas buscar en toda la lista cada vez, sino sólo desde la última búsqueda indices = [] ultimo = 0 for v in subconjunto: ultimo += conjunto[ultimo:].index(v) indices.append(ultimo) [conjunto[j] for j in indices]==subconjunto > True También te puede interesar usar conjuntos, si no necesitas el orden de los elementos. Un saludo ___ 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 cump le condición) de forma eficiente
Te escribo a tí directamente porque la lista parece que no me acepta!! Si los elementos de subconjunto están ordenados dentro de conjunto, la búsqueda es O(n): si sabes que los elementos del subconjunto están ordenados dentro del conjunto, no necesitas buscar en toda la lista cada vez, sino sólo desde la última búsqueda indices = [] ultimo = 0 for v in subconjunto: ultimo += conjunto[ultimo:].index(v) indices.append(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 cump le condición) de forma eficiente
Daniel Garcia Moreno escribió: > > 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. > 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. ___ 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 cump le condición) de forma eficiente
2010/3/4 Pablo Angulo : > Daniel Garcia Moreno escribió: >> >> 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. >> > 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. ___ 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 cump le condición) de forma eficiente
Pablo Angulo escribió: > indices = [] > ultimo = 0 > for v in subconjunto: > ultimo += conjunto[ultimo:].index(v) > indices.append(ultimo) > > [conjunto[j] for j in indices]==subconjunto > > Lamento ser pesado, pero hay que hacer un cambio: indices = [] ultimo = 0 for v in subconjunto: ultimo += conjunto.index(v,ultimo) indices.append(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 cump le condición) de forma eficiente
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)) ___ 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 cump le condición) de forma eficiente
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). ___ 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 cump le condición) de forma eficiente
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/
Re: [Python-es] Buscar índices de un array (que cump le condición) de forma eficiente
Olemis Lang (Simelix) escribió:
> 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`
No lo sospeches: tiene que haber un bucle para encontrar el índice, pero
en cuanto encuentras el primer índice con ese valor, te sales del bucle.
¿Cuántas iteraciones haces del bucle en total? Bueno, puede que para
algún caso particular hagan falta muchas iteraciones, pero la suma de
todas las iteraciones no puede superar N: La primera iteración del bucle
"for v in subconjunto", recorres desde 0 hasta indice[0], luego desde
indice[1] hasta indice[2],... si sumas todas esas cantidades tienes:
(indice[0] - 0) + (indice[1]-indice[0]) + ... + (indice[M-1] -
indice[M-2]) = indice[M-1] < N
___
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 cump le condición) de forma eficiente
Olemis Lang (Simelix) escribió: > No me parece que `index` recuerde el último índice de la lista (no > estamos hablando de iteradores ;o) entre dos llamadas diferentes para > recomenzar la búsqueda de un nuevo elemento (¿ o es que funciona así > internamente ?) ... Normalmente, index comienza desde el principio, pero justo por eso le pasamos otro argumento más a index: ultimo = conjunto.index(v, ultimo+1) ___ Python-es mailing list Python-es@python.org http://mail.python.org/mailman/listinfo/python-es FAQ: http://python-es-faq.wikidot.com/
