Rendimiento de la lista (...). Insertar (...)

Question

Pensé en la siguiente pregunta sobre la arquitectura de la computadora. Supongamos que yo hago en Python

from bisect import bisect 
index = bisect(x, a)  # O(log n) (also, shouldn't it be a standard list function?) 
x.insert(index, a)  # O(1) + memcpy() 

que tiene log n, además, si yo lo entiendo correctamente, una operación de copia de memoria para x[index:]. Ahora leí recientemente que el cuello de botella suele estar en la comunicación entre el procesador y la memoria, por lo que la copia de memoria podría ser hecha por RAM bastante rápido. ¿Es así como funciona?

Answer 1

Python es un idioma. Multiple implementations exist, y ellos pueden tienen implementaciones diferentes para las listas. Entonces, sin mirar el código de una implementación real, no se puede saber con certeza cómo se implementan las listas y cómo se comportan bajo ciertas circunstancias.

Mi apuesta sería que las referencias a los objetos en una lista se almacenan en la memoria contigua (ciertamente no como una lista vinculada ...). Si eso es así, entonces la inserción usando x.insert hará que se muevan todos los elementos detrás del elemento insertado. El hardware puede hacer esto de manera eficiente, pero la complejidad aún sería O (n).

Para listas pequeñas la operación bisect puede llevar más tiempo que x.insert, a pesar de que el primero es O (log n) mientras que el último es O (n). Para las listas largas, sin embargo, me arriesgaría a suponer que x.insert es el cuello de botella. En tales casos, debe considerar usar una estructura de datos diferente.

Answer 2

Las listas de CPython son matrices contiguas. Cuál de las inserciones O (log n) bisect y O (n) domina su perfil de rendimiento depende del tamaño de su lista y también de los factores constantes dentro de O(). Particularmente, la función de comparación invocada por bisect puede ser algo costoso dependiendo del tipo de objetos en la lista.

Si necesita mantener secuencias clasificables mutables potencialmente grandes, la matriz lineal subyacente al tipo de lista de pitones no es una buena opción. Dependiendo de sus montones de necesidades, los árboles o las listas de omisiones pueden ser apropiados.

Answer 3

Utilice blist module si necesita una lista con un mejor rendimiento de inserción.