У меня есть список my_list (список содержит строки utf8):
>>> len(my_list)
8777
>>> getsizeof(my_list) # <-- note the size
77848
По какой-то причине отсортированный список (my_sorted_list = sorted(my_list)) использует больше памяти:
>>> len(my_sorted_list)
8777
>>> getsizeof(my_sorted_list) # <-- note the size
79104
Почему sorted возвращает список, который занимает больше места в памяти, чем исходный несортированный список?
Как Ignacio указывает на, это связано с тем, что Python выделяет немного больше памяти, чем требуется. Это делается для выполнения O(1) .appends в списках.
sorted создает новый список из предоставленной последовательности сортирует его на месте и возвращает его. Чтобы создать новый список, Python расширяет список пустых размеров с переданным; что приводит к наблюдаемому перераспределению (что происходит после вызова list_resize). Вы можете подтвердить тот факт, что сортировка не является виновником, используя list.sort; тот же алгоритм используется без создания нового списка (или, как известно, он выполняется на месте). Размеры там, конечно, не отличаются.
Стоит отметить, что эта разница в основном присутствует, когда:
Исходный список был создан с помощью list-comp (где, если пространство доступно и окончательный append не вызывает изменить размер, размер меньше).
Когда используются литералы списка. Там a PyList_New создается на основе количества значений в стеке и никаких добавлений не производится. Выполняется прямое присвоение базовому массиву), который не вызывает никаких изменений и сохраняет минимальный размер:
Итак, со списком-comp:
l = [i for i in range(10)]
getsizeof(l) # 192
getsizeof(sorted(l)) # 200
Или литерал списка:
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
getsizeof(l) # 144
getsizeof(sorted(l)) # 200
размеры меньше (тем более с использованием литералов).
При создании через list память всегда перераспределяется; Python знает размеры и преувеличивает будущие изменения, перераспределяя бит в зависимости от размера:
l = list(range(10))
getsizeof(l) # 200
getsizeof(sorted(l)) # 200
Таким образом, вы не видите различий в размерах списка (ов).
В качестве последней заметки я должен указать, что это специфическая для поведения реализация C Python i.e CPython. Это деталь того, как язык был реализован и как таковой, вы не должны зависеть от него каким-либо дурацким способом.
Jython, IronPython, PyPy и любая другая реализация могут/не иметь такого же поведения.
Операция изменяет размер в обходной последовательности, чтобы амортизировать добавление к списку, начиная со списка, предварительно выделенного компилятором.