2010/3/4 Pablo Angulo <pablo.ang...@uam.es>:
> 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))
Por las características del problema y del contexto (dos listas
ordenadas ;o) me parece que lo más adecuado en este caso es un
algoritmo de mezcla como MergeSort [1]_ [2]_ que AFAICR debe ser O(n
log(n)) siendo n = min(N, M) en el peor caso, pero O(n) si están
ordenados (para más detalles consulten los enlaces ;o). Realmente en
este caso ni siquiera hace falta el mergesort completo, solo la
función de mezcla y simplificada , lo cual resultaría más eficiente
todavía, se puede lograr más aún si se sabe que una lista es un
subelemento de la otra -pero todas esas quedan de tarea para el OP-
;o)
{{{
#!python
>>> conjunto = range(1000, 1100, 1)
>>> subconjunto = range(1000, 1100, 3)
>>> from itertools import count
>>> def setidx(sub, full): # a.k.a merge()
... idxs = count()
... while sub and full :
... if sub[0] == full[0] :
... yield idxs.next()
... full.pop(0); sub.pop(0)
... elif sub[0] < full[0] :
... sub.pop(0)
... else :
... full.pop(0)
... idxs.next()
...
>>> list(setidx(subconjunto, conjunto))
[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, 75, 78, 81, 84, 87, 90, 93, 96, 99]
}}}
Uso de memoria adicional ~= 0
.. [1] MergeSort
(http://en.wikipedia.org/wiki/Mergesort)
.. [2] Ordenamiento por mezcla
(http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla)
PD: De todas formas mi sugerencia muy particular es que no confíen
demasiado en los análisis teóricos del tipo mencionado por Pablo (o
mejor dicho, que desconfíen hasta que no tengan la seguridad
irrefutable que les da un profiler ;o) . Este hilo me ha recordado un
artículo que tengo pendiente para mi blog que ilustra esto muy bien (y
que resulta realmente sorprendente, créanme ;o). Trataré de publicarlo
mañana (o pasado, o ...), y así tendrán más argumentos para juzgar
ustedes por su cuenta
Y para terminar, los algs de mezcla tienden a ser más fácilmente
paralelizables y trabajan mejor con medios secuenciales, por lo que si
la cantidad de datos es *REALMENTE* grande entonces pueden resultar
bastante atractivos , pues tienden además a tener la virtud de ser
estables ... bueno y si de algo sirve, pues, no contaminan el medio
ambiente, ¿ vale ? :P )
;o)
--
Regards,
Olemis.
Blog ES: http://simelo-es.blogspot.com/
Blog EN: http://simelo-en.blogspot.com/
Featured article:
Comienza la era de la televisión 3D (el 10 de marzo ;o) -
http://feedproxy.google.com/~r/simelo-es/~3/mPcmLbduWJU/despues-del-gran-exito-del-largometraje.html
_______________________________________________
Python-es mailing list
Python-es@python.org
http://mail.python.org/mailman/listinfo/python-es
FAQ: http://python-es-faq.wikidot.com/
