[Python-es] Buscar índices de un array (que cumple condición) de forma eficiente

[Olemis Lang (Simelix)]

2010/3/4 Pablo Angulo <pablo.angulo en 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