Объем памяти списка python

Question

Я что-то экспериментировал со списками и наткнулся на списки, ссылающиеся на себя. Я поискал через SO и получил ответы на некоторые из моих c основных вопросов. Но когда я попытался получить размер памяти саморегулирующихся списков разной длины, я обнаружил интересный образец

Код для воспроизведения:

import sys

memory_size = {}

for length in range(50):
    lst = []
    for length_loop in range(length):
        lst.append(lst)
    memory_size[length] = sys.getsizeof(lst)

Значение memory_size:

{0: 64, 1: 96, 2: 96, 3: 96, 4: 96, 5: 128, 6: 128, 7: 128, 8: 128, 9: 192, 10: 192, 11: 192, 12: 192, 13: 192, 14: 192, 15: 192, 16: 192, 17: 264, 18: 264, 19: 264, 20: 264, 21: 264, 22: 264, 23: 264, 24: 264, 25: 264, 26: 344, 27: 344, 28: 344, 29: 344, 30: 344, 31: 344, 32: 344, 33: 344, 34: 344, 35: 344, 36: 432, 37: 432, 38: 432, 39: 432, 40: 432, 41: 432, 42: 432, 43: 432, 44: 432, 45: 432, 46: 432, 47: 528, 48: 528, 49: 528}

При построении вышеуказанных точек данных

введите описание изображения здесь

Python 3.7.3 (default, Mar 27 2019, 16:54:48)
Type 'copyright', 'credits' or 'license' for more information
IPython 7.5.0 -- An enhanced Interactive Python. Type '?' for help.

Почему размер памяти самореференционного списка остается постоянным для определенного диапазона длин и увеличивается после определенного диапазона?

А также увеличение размера памяти другое

Answer 1

Списки всегда отображают этот шаблон, если они увеличены с добавлением.

Ключевой момент для понимания, sys.getsizeof не учитывает объекты, указанные в списке , только размер самого объекта списка. Теперь объекты Python list реализованы в виде списков массивов под капотом, поэтому по существу есть заголовок PyObject (например, 16-байтовые накладные расходы или что-то подобное), затем примитивный массив указателей PyObject (что составляет почему они могут быть разнородными и ссылаться на себя).

Этот базовый массив имеет превышение доступности , и его размер изменен таким образом, чтобы гарантировать амортизированные операции с постоянным временем .append . Другими словами, объекты Python list имеют амортизированное постоянное время .append, поэтому выполнение чего-то вроде for x in range(N): my_list.append(0) является операцией с линейным временем , потому что базовый буфер не перераспределяется для каждого итерация.

Смотрите, вы видите один и тот же паттерн с любым объектом, например None:

In [24]: import sys
    ...:
    ...: memory_size = {}
    ...:
    ...: for length in range(50):
    ...:     lst = []
    ...:     for length_loop in range(length):
    ...:         lst.append(None)
    ...:     memory_size[length] = sys.getsizeof(lst)
    ...:

In [25]: memory_size
Out[25]:
{0: 72,
 1: 104,
 2: 104,
 3: 104,
 4: 104,
 5: 136,
 6: 136,
 7: 136,
 8: 136,
 9: 200,
 10: 200,
 11: 200,
 12: 200,
 13: 200,
 14: 200,
 15: 200,
 16: 200,
 17: 272,
 18: 272,
 19: 272,
 20: 272,
 21: 272,
 22: 272,
 23: 272,
 24: 272,
 25: 272,
 26: 352,
 27: 352,
 28: 352,
 29: 352,
 30: 352,
 31: 352,
 32: 352,
 33: 352,
 34: 352,
 35: 352,
 36: 440,
 37: 440,
 38: 440,
 39: 440,
 40: 440,
 41: 440,
 42: 440,
 43: 440,
 44: 440,
 45: 440,
 46: 440,
 47: 536,
 48: 536,
 49: 536}

И, чтобы вас убедить, вот ваш самореференционный список:

In [26]: import sys
    ...:
    ...: memory_size = {}
    ...:
    ...: for length in range(50):
    ...:     lst = []
    ...:     for length_loop in range(length):
    ...:         lst.append(lst)
    ...:     memory_size[length] = sys.getsizeof(lst)
    ...:

In [27]: memory_size
Out[27]:
{0: 72,
 1: 104,
 2: 104,
 3: 104,
 4: 104,
 5: 136,
 6: 136,
 7: 136,
 8: 136,
 9: 200,
 10: 200,
 11: 200,
 12: 200,
 13: 200,
 14: 200,
 15: 200,
 16: 200,
 17: 272,
 18: 272,
 19: 272,
 20: 272,
 21: 272,
 22: 272,
 23: 272,
 24: 272,
 25: 272,
 26: 352,
 27: 352,
 28: 352,
 29: 352,
 30: 352,
 31: 352,
 32: 352,
 33: 352,
 34: 352,
 35: 352,
 36: 440,
 37: 440,
 38: 440,
 39: 440,
 40: 440,
 41: 440,
 42: 440,
 43: 440,
 44: 440,
 45: 440,
 46: 440,
 47: 536,
 48: 536,
 49: 536}

Расхождения в индивидуальных размерах сводятся к таким вещам, как Python версия и системная архитектура (например, в 32-битной системе указатели имеют 4 байта вместо 8, а разные версии Python - свободно изменять детали реализации, такие как размер пустого списка). Обратите внимание, что приведенное выше было запущено на Python 3.7, если я использую другое окружение:

(base) juanarrivillaga@173-11-109-137-SFBA ~ % python -c "import sys; print(f'{sys.version}\nEmpty List Size: {sys.getsizeof([])}')"
3.8.1 (default, Jan  8 2020, 16:15:59)
[Clang 4.0.1 (tags/RELEASE_401/final)]
Empty List Size: 56

Answer 2

Ответ может быть где-то в этом. Хотя очевидно, что различия в размере будут зависеть от архитектуры вашей системы и установки python, размер увеличения можно объяснить реализацией списков в Python.

https://github.com/python/cpython/blob/master/Objects/listobject.c