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/