list: массив ссылок с запасом в одну восьмую

Если ты знаешь, как растёт ёмкость списка в CPython, почему рост на 1/8 не ломает амортизацию и сколько памяти занимает список чисел, листай до «Теперь сам».

Как думаешь, сколько раз переедет массив

В разделе про амортизацию динамический массив удваивался: заполнился - выделили вдвое больше, скопировали. На миллион вставок это 19-20 переездов. Теперь настоящий list из CPython: в список по одному дописывают миллион элементов. Сколько раз массив переедет на новое место, и сколько ссылок за всё время придётся скопировать?

Ответь себе до чтения. Если твой ответ «около двадцати, как у удвоения», - разбор покажет 86 переездов и восемь копий на каждый элемент. И при этом вставка остаётся дешёвой.

На что это похоже

Представь гардероб в театре. На вешалках висят не пальто зрителей, а номерки: само пальто лежит где-то на складе, номерок говорит, где его взять. Вешалка - это list, номерки - ссылки, пальто - объекты. Чтобы повесить номерок в конец, достаточно свободного крючка. Когда крючки кончились, вешалку меняют на чуть более длинную и перевешивают номерки - пальто при этом никто не трогает.

А вот повесить номерок первым - значит сдвинуть на крючок вправо все остальные. На вешалке из ста тысяч номерков это сто тысяч сдвигов.

Механизм: длина, ёмкость и массив ссылок

Объект списка хранит три вещи: длину (ob_size), ёмкость (allocated) и указатель на массив ссылок (ob_item). len(a) читает готовую длину - это O(1). a[i] - это адрес начала массива плюс 8 · i, тоже O(1). Сами объекты лежат в других местах памяти.

append кладёт ссылку в первое свободное место. Если свободных нет, вызывается пересчёт ёмкости (list_resize в Objects/listobject.c):

новая_ёмкость = (нужно + нужно // 8 + 6), округлённое вниз до кратного 4

Для одного append «нужно» - это старая длина плюс один. Сдвиг вправо на 3 бита - то же деление на 8 нацело, а & ~3 обнуляет два младших бита и округляет вниз до кратного четырём. Отсюда ряд ёмкостей 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108: сначала рост почти вдвое (там решает «плюс 6»), потом всё ближе к 9/8. Обратно список сжимается, только когда длина падает ниже половины ёмкости.

Правило

list - массив ссылок с запасом. Ёмкость растёт до n + n // 8 + 6 (кратно 4), то есть в 9/8 раза на больших длинах. Любой постоянный множитель роста r > 1 даёт амортизированный append за O(1): всего копий меньше n · r / (r − 1). Чтение по индексу, len, append и pop() с конца - O(1); insert(0, x), pop(0) и del a[0] сдвигают все ссылки - O(n).

Разбор: 86 переездов на миллион, и почему это всё ещё O(1)

Посчитаем переезды без миллиона шагов: переезд случается, только когда массив полон, поэтому достаточно прыгать от ёмкости к ёмкости. На каждом переезде копируется вся старая ёмкость.

def novaya_emkost(nuzhno, bylo_dliny):
    # формула CPython: запас в одну восьмую плюс 6, кратно четырём
    e = (nuzhno + (nuzhno >> 3) + 6) & ~3
    if nuzhno - bylo_dliny > e - nuzhno:
        e = (nuzhno + 3) & ~3
    return e

def append_podryad(n, rost):
    # считаем только переезды: массив полон, дописываем ещё один
    emkost = 0
    pereezdov = 0
    skopirovano = 0
    while emkost < n:
        skopirovano = skopirovano + emkost
        pereezdov = pereezdov + 1
        if rost == "cpython":
            emkost = novaya_emkost(emkost + 1, emkost)
        else:
            emkost = max(4, 2 * emkost)
    return [pereezdov, skopirovano]

for n in [1000, 1000000]:
    for rost in ["cpython", "удвоение"]:
        r = append_podryad(n, rost)
        print(n, rost, "переездов", r[0], "скопировано", r[1],
              "на элемент", round(r[1] / n, 2))

1000 cpython переездов 28 скопировано 7556 на элемент 7.56
1000 удвоение переездов 9 скопировано 1020 на элемент 1.02
1000000 cpython переездов 86 скопировано 8445096 на элемент 8.45
1000000 удвоение переездов 19 скопировано 1048572 на элемент 1.05

86 расширений (программа зовёт их переездами, считая и первое выделение) и 8,45 копии на элемент - в восемь раз больше, чем при удвоении, но число копий на элемент не растёт с n: оно колеблется между расширениями и всегда меньше девяти. Откуда граница: при каждом переезде копируется вся заполненная ёмкость, а ёмкости растут геометрически с множителем r. Пусть последний переезд скопировал ёмкость C, она меньше n; до неё были C/r, C/r²… Их сумма - геометрическая прогрессия: C · (1 + 1/r + 1/r² + …), а сумма в скобках меньше 1 / (1 − 1/r) - так суммируется бесконечная убывающая прогрессия. Итого меньше C · r / (r − 1) < n · r / (r − 1). При r = 2 это 2n, при r = 9/8 - 9n. Множитель влияет на константу, а не на асимптотику.

Почему CPython платит восьмикратную константу? Ради памяти: у удвоения сразу после переезда пустует половина массива, а здесь на больших длинах не больше одной девятой (у маленьких списков «плюс 6» оставляет больше: после первого append пустуют 3 места из 4). Вдобавок переезд делает realloc - системная функция «расширь этот блок памяти»: если за блоком свободно, она растит его на месте, а у больших блоков переставляет страницы, не копируя байты, - и тогда «скопировано» в разборе - это верхняя граница.

Проверим ряд ёмкостей на настоящем Python 3.12 - том, что стоит на этом сайте. sys.getsizeof возвращает размер объекта списка в байтах: 56 байт заголовка плюс по 8 на каждое место.

import sys

a = []
pusto = sys.getsizeof(a)
vmestimost = 0
for i in range(100):
    a.append(i)
    v = (sys.getsizeof(a) - pusto) // 8
    if v != vmestimost:
        print("длина", len(a), "- мест", v)
        vmestimost = v

длина 1 - мест 4
длина 5 - мест 8
длина 9 - мест 16
длина 17 - мест 24
длина 25 - мест 32
длина 33 - мест 40
длина 41 - мест 52
длина 53 - мест 64
длина 65 - мест 76
длина 77 - мест 92
длина 93 - мест 108

Ряд совпал с формулой. Переезд - на длине 1, 5, 9, 17: ровно когда все места заняты.

Разбор: сколько памяти у списка чисел

Ссылка - 8 байт, но число - отдельный объект. Миллион дробных чисел в списке и в array, где числа лежат прямо в массиве, без объектов:

import sys
from array import array

n = 1_000_000
spisok = [float(i) for i in range(n)]
ssylki = sys.getsizeof(spisok)
obekty = sum(sys.getsizeof(x) for x in spisok)
print("list: ссылки", ssylki // 1024, "КБ, объекты",
      obekty // 1024, "КБ")
print("float занимает", sys.getsizeof(1.5), "байта, ссылка на него - 8")
massiv = array("d", spisok)
print("array('d'):", sys.getsizeof(massiv) // 1024, "КБ")

list: ссылки 8250 КБ, объекты 23437 КБ
float занимает 24 байта, ссылка на него - 8
array('d'): 7812 КБ

Список занял около 31 МБ: 8 МБ ссылок (с запасом - ёмкость чуть больше миллиона) и 23 МБ самих объектов, по 24 байта на число. Тот же миллион в array('d') - 7,8 МБ, вчетверо меньше (буква 'd' - тип элемента, дробное число в 8 байт; 'q' - целое в 8 байт, 'i' - целое в 4). Граница правила: «список стоит 8 байт на элемент» верно только для ссылок; память под объекты считается отдельно.

Что ломается без этого

Очередь на list. queue.pop(0) сдвигает все ссылки. Замер на этом сайте, вставка в начало против вставки в конец:

import time
from collections import deque


def zamer(dejstvie, n):
    # лучшее из трёх: так меньше случайных помех
    luchshee = None
    for popytka in range(3):
        t = time.perf_counter()
        dejstvie(n)
        dt = time.perf_counter() - t
        if luchshee is None or dt < luchshee:
            luchshee = dt
    return luchshee


def s_konca(n):
    a = []
    for i in range(n):
        a.append(i)


def v_nachalo(n):
    a = []
    for i in range(n):
        a.insert(0, i)


def deka(n):
    d = deque()
    for i in range(n):
        d.appendleft(i)


for n in [10_000, 100_000]:
    print(n, end="")
    for imya, f in [("append", s_konca), ("insert(0)", v_nachalo),
                    ("appendleft", deka)]:
        print(f"  {imya} {zamer(f, n) * 1000:.1f} мс", end="")
    print()

10000  append 0.5 мс  insert(0) 17.4 мс  appendleft 0.5 мс
100000  append 5.7 мс  insert(0) 2020.7 мс  appendleft 6.4 мс

Вдесятеро больше элементов - в 116 раз дольше: квадрат. deque из collections вставляет с обоих концов за O(1), о нём урок 4.

Таблица из одной строки. Повтор списка копирует ссылки, а не строки:

a = [[0] * 3] * 3
a[0][0] = 7
print(a)
b = []
for i in range(3):
    b.append([0] * 3)
b[0][0] = 7
print(b)

[[7, 0, 0], [7, 0, 0], [7, 0, 0]]
[[7, 0, 0], [0, 0, 0], [0, 0, 0]]

В a три ссылки на один и тот же список - запись в «первую строку» видна во всех. В b три разных списка.

Зачем это в работе

Сервис копит события в списке и раз в секунду отдаёт самое старое через pop(0). Пока событий сотни, всё летает; в час пик их сто тысяч, и обработчик тратит секунды на сдвиг ссылок. Профилировщик (например, python -m cProfile -s cumtime сервис.py печатает время по функциям) покажет list.pop, и без знания устройства легко решить, что «Python медленный». Лечение - deque или индекс начала. Второй частый случай - память: таблица на десять миллионов чисел в списках занимает вчетверо больше, чем в array или NumPy, и это решает, влезет ли задача в память контейнера.

Теперь сам

1. Список пуст, в него по одному дописывают 20 элементов. Сколько раз массив переедет и какая будет ёмкость в конце?
2. Почему при множителе роста r = 9/8 всего копий может быть почти 9n, а не меньше 2n, как при удвоении?
3. Сколько примерно памяти займёт список из 1000 разных дробных чисел, если ёмкость равна 1000?