2010/3/4 Pablo Angulo <pablo.ang...@uam.es>: > 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.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. > > 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.
Esto también es real. Por ejemplo, normalmente los algoritmos híbridos son los que se utilizan más frecuentemente. Por ejemplo, consideren lo siguiente [1]_ : {{{ In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.[6] Python uses timsort, another tuned hybrid of merge sort and insertion sort. }}} FWIW ;o) .. [1] Comparison with other sort algorithms (http://en.wikipedia.org/wiki/Mergesort#Comparison_with_other_sort_algorithms) -- 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/