[Python-es] Eficiencia de las listas

[Antonio Beamud Montero]

El 05/08/13 21:54, Chema Cortes escribió:
> Últimamente, estoy realizando estudios sobre la eficiencia de
> distintos códigos python. Mirando qué tipo de colección podía ser más
> eficiente según qué tareas, me encuentro con el siguiente párrafo en
> la documentación de ["deque"][1]:
>
> "Deques support thread-safe, memory efficient appends and pops from
> either side of the deque with approximately the same O(1) performance
> in either direction.
>
> Though list objects support similar operations, they are optimized for
> fast fixed-length operations and incur O(n) memory movement costs for
> pop(0) and insert(0, v) operations which change both the size and
> position of the underlying data representation."
>
> He comprobado que, efectivamente, el costo de insertar elementos al
> principio de una lista es mucho mayor que añadir elementos al final de
> la lista (x10000).
>
> En estos momentos , necesito trabajar con listas de números muy largas
> (> 10e6 elementos) para trocear en dos pedazos, invertir uno de ellos
> y volverlos a empalmar (método "2-opt"). Una forma de expresarlo:
>
>     L[i+1:j+1] = L[j:i:-1]   con i+1<j
>
> que equivale a:
>
>     L[:i] + L[j:i:-1] + L[j+1:]
>
> Esta última expresión, aunque más clara, es poco eficiente al tener
> que crear una nueva lista partiendo de tres sublistas intermedias.
>
> Los elementos no cambian de valor y tampoco cambia el tamaño de la
> lista. Parece que la "lista" es la estructura más eficiente para esta
> tarea (por lo que cuenta la documentación) siempre que no se modifique
> en tamaño. Pero me pregunto si hay algún modo de hacer este manejo más
> eficiente, tal vez usando alguna otra estructura, en python o numpy,
> que mejore estas tareas de corte y empalme. Intuyo que con "arrays" se
> reducen las necesidades de memoria, pero en estos momentos, la memoria
> es lo que menos me preocupa. Busco un método genérico que pueda valer
> para cualquier otro tipo de datos (eg: lista de vectores).
>
>

Yo me decanté por usar numpy para resolver este tipo de problemas, 
aunque mis listas eran un orden de magnitud más pequeñas, después de 
hacer varias pruebas, el uso de las listas para operaciones simples, es 
tanto o más eficiente usando listas de python que crear arrays en numpy 
(bueno dependiendo de la operación), pero yo necesitaba métodos como 
'diff', 'where', etc.. que si que marcaban diferencias respecto a mis 
anteriores implementaciones.

Estaré muy atento a las conclusiones que llegues :-)

Un saludo.