python - tutorial - para que se usa elastic search

¿Por qué una lista ordenada es más grande que una lista sin clasificar?

Question

Tengo una lista my_list (la lista contiene cadenas utf8):

>>> len(my_list)
8777
>>> getsizeof(my_list)                     #  <-- note the size
77848

Por alguna razón, una lista ordenada ( my_sorted_list = sorted(my_list) ) usa más memoria:

>>> len(my_sorted_list)
8777
>>> getsizeof(my_sorted_list)              #  <-- note the size
79104

¿Por qué se sorted devolver una lista que ocupa más espacio en la memoria que la lista inicial sin clasificar?

Answer 1

Como señala Ignacio , esto se debe a que Python asigna un poco más de memoria de la necesaria. Esto se hace para realizar O(1) .appends en listas.

sorted crea una nueva lista fuera de la secuencia proporcionada, la ordena en su lugar y la devuelve. Para crear la nueva lista, Python extiende una lista de tamaño vacía con la que se aprobó ; que da como resultado el exceso de asignación observado (que ocurre después de llamar a list_resize ). Puede corroborar el hecho de que la clasificación no es la culpable utilizando list.sort ; el mismo algoritmo se usa sin que se cree una nueva lista (o, como se sabe, se realiza en el lugar ). Los tamaños allí, por supuesto, no difieren .

Vale la pena señalar que esta diferencia está principalmente presente cuando:

• La lista original se creó con una lista comp (donde, si hay espacio disponible y el append final no genera un cambio de tamaño , el tamaño es menor).

• Cuando se utilizan listas literales. Allí se crea un PyList_New basado en el número de valores en la pila y no se hacen apéndices. Se realiza la asignación directa a la matriz subyacente ) que no activa ningún tamaño y mantiene el tamaño al mínimo:

Entonces, con una lista comp.

l = [i for i in range(10)]

getsizeof(l)          # 192
getsizeof(sorted(l))  # 200

O una lista literal:

l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

getsizeof(l)          # 144
getsizeof(sorted(l))  # 200

Los tamaños son más pequeños (más aún con el uso de literales).

Al crear a través de la list , la memoria siempre está sobre asignada; Python conoce los tamaños y anticipa las modificaciones futuras mediante la asignación excesiva de un bit según el tamaño:

l = list(range(10))

getsizeof(l)          # 200
getsizeof(sorted(l))  # 200

Por lo tanto, no se observan diferencias en los tamaños de la (s) lista (s).

Como nota final, debo señalar que este es un comportamiento específico de la implementación C de Python, es decir, CPython. Es un detalle de cómo se implementó el lenguaje y, como tal, no debe depender de él de forma extravagante.

Jython, IronPython, PyPy y cualquier otra implementación podrían / ​​no tener el mismo comportamiento.

Answer 2

La lista cambia el tamaño de la operación en generalocates para amortizar la adición a la lista en lugar de comenzar con una lista preasignada por el compilador.