Динамический массив

Программа на Python миллион раз делает lst.append(x) и ни разу не говорит, сколько всего будет элементов. А память компьютер выдаёт блоками заранее известной длины, и блок нельзя просто удлинить, если сразу за ним лежит что-то чужое. Список выкручивается так: держит запас, а когда запас кончается, просит новый блок побольше и переносит в него всё, что накопил. Ниже — настоящие замеры из песочницы этого сайта: как растут список Python и срез Go на миллионе добавлений, и для сравнения три правила роста по формуле.

Ступенчатая линия — ёмкость: сколько ячеек выделено. Пунктир — сколько занято. Каждый столбик — переезд, и его высота равна числу перенесённых элементов: при переезде переносят всё. У списка Python часть столбиков серые: там блок удлинился на месте, об этом ниже. Столбики дорожают, но редеют, и на нижнем графике средняя цена одного append у всех правил выходит на ровную линию — у всех, кроме «+1000». Там ёмкость растёт не в разы, а на постоянную добавку, и средняя цена ползёт вверх без конца: к миллиону это пятьсот копирований на каждый append.

Идея

Храним элементы в обычном массиве с запасом: размер — сколько занято, ёмкость — сколько выделено. Пока есть место, append пишет в следующую ячейку. Когда места нет, заводим массив в r раз больше и копируем туда всё. Раз ёмкость растёт в геометрической прогрессии, переезды так редки, что их суммарная цена — не больше константы на каждый добавленный элемент.

Всё остальное достаётся от обычного массива даром. Элементы лежат в памяти подряд, и адрес i-го — начало плюс i, умноженное на размер элемента, поэтому доступ по индексу стоит одно действие, как бы ни был велик массив. Соседние элементы лежат рядом, и процессор читает их целыми строками кэша: перебирать массив быстрее, чем почти любую другую структуру. Как устроен массив в памяти и почему список Python хранит не числа, а ссылки на них, подробно разобрано в главе курса о массивах и списках.

Почему в среднем O(1)

Один append, на который пришёлся переезд, стоит O(n): нужно перенести n элементов. Обещание «O(1)» относится к среднему по любой последовательности операций — это амортизированная стоимость (подробнее — в статье об амортизационном анализе). Она не про удачу и не про случайные данные: оценка верна для любой последовательности append, без всякой вероятности.

Тот же вывод можно рассказать бухгалтерски. Пусть каждый append при удвоении платит три монеты: одну за запись себя, две откладывает. К моменту, когда ёмкость C исчерпана, с прошлого переезда добавились C/2 элементов и отложили C монет — ровно столько, сколько стоит перенести все C элементов. Счёт никогда не уходит в минус, значит, три монеты на операцию хватает всегда.

А теперь «+1000». Переезды случаются на 1000, 2000, 3000 элементах, и к n элементам их набирается около n/1000, а перенесено 1000 + 2000 + … ≈ n²/2000. Это O(n²) на n операций, O(n) на каждую в среднем. Неважно, тысяча в добавке или миллион: постоянная добавка лишь откладывает квадрат, но не отменяет. На сцене при миллионе append правило «+1000» перенесло 499 500 000 элементов, а удвоение — 1 048 575.

Какой множитель выбрать

Из доказательства видно, что множитель — торг. Большой r — меньше копирований (в среднем от 1/(r − 1) до r/(r − 1) на append), но больше пустующей памяти: сразу после переезда занята только доля 1/r ёмкости. Настоящие языки решают этот торг по-разному:

Числа для Python и Go измерены, для Java и ×2 — посчитаны по их правилам; все они есть в первой сцене. Python выглядит расточительным: восемь с лишним копирований на элемент. Но копирует он восьмибайтные ссылки одним сплошным куском, а главное, часто не копирует вовсе. Он просит у системы удлинить блок функцией realloc, и если сразу за блоком свободно, блок растёт на месте. В нашем замере из 85 переездов списка на миллионе append буфер на самом деле сменил адрес 42 раза, в другом запуске — 35. Комментарий в исходниках CPython так и говорит: запас скромный, но даже при плохом realloc его хватает на линейное время в сумме. Go свою память так не удлиняет: каждый переезд среза — новый блок и копирование (35 из 35).

Есть и довод против множителя 2, про повторное использование памяти. При удвоении каждый новый блок больше всех прежних вместе взятых: 1 + 2 + … + 2^k < 2^k+1. Освобождённые позади куски никогда не вместят следующий блок, и массив ползёт по адресам вперёд. При меньшем множителе через несколько переездов освободившиеся куски складываются в достаточно большую дыру, и блок возвращается в начало. Строго говоря, если старый блок освобождается только после копирования, нужно r меньше золотого сечения φ ≈ 1,618: условие 1 + r + … + r^k−1 ≥ r^k+1 при больших k сводится к r² − r − 1 < 0. На этот довод опираются авторы fbvector из библиотеки Folly, где выбран множитель 1,5.

Модель здесь идеальная: распределитель кладёт блок в первое подходящее свободное место и сливает соседние дыры. Настоящие распределители раскладывают блоки разных размеров по разным областям, так что выигрыш от 1,5 на практике меньше, чем на картинке. Но направление верное.

Ловушка: сжатие

Если массив умеет расти, хочется, чтобы он умел и сжиматься: удалили 90 % элементов — верните память. Самое очевидное правило — «сжиматься вдвое, когда занята половина» — ломает всю амортизацию. Возьмите полный массив на 8 элементов и делайте по очереди push и pop:

push переполняет массив, и он переезжает в 16 ячеек. pop оставляет 8 из 16 — ровно половину, и массив переезжает обратно в 8. Каждая операция переносит все элементы, и цена у неё уже не O(1), а O(n). Лечится это зазором между порогами: расти, когда полон, а сжиматься вдвое, когда занята четверть. После любого переезда массив заполнен примерно наполовину, и до следующего переезда в любую сторону нужно не меньше n/4 дешёвых операций — их отложенных монет хватит на перенос. Так сжимается таблица в учебнике Кормена и соавторов, так делает и листинг ниже.

Python сжимает список, когда занято меньше половины, но новый размер берёт по той же формуле роста, с запасом в восьмую часть: зазор есть, и качели его не раскачивают. Срез Go не сжимается никогда. s = s[:0] оставляет ёмкость прежней, и это удобно: буфер можно переиспользовать. Но здесь же сидит частая утечка: маленький срез, вырезанный из огромного, держит в памяти весь огромный массив. Если от гигабайтного буфера нужно десять элементов, скопируйте их: slices.Clone(big[:10]).

Код

Динамический массив, собранный вручную. Под капотом — блок постоянной длины: в Python это список, созданный сразу нужного размера, в Go — срез, который никогда не растёт сам. Переезд — явный цикл копирования, и программа считает, сколько элементов перенесла:

Последние строки вывода — та же теорема в числах:

n =   1000: 10 moves,   1023 copied, 1.02 per append,    24 cells spare
n =  10000: 14 moves,  16383 copied, 1.64 per append,  6384 cells spare
n = 100000: 17 moves, 131071 copied, 1.31 per append, 31072 cells spare

Копирований на append всегда меньше двух, а запас гуляет от 2 до 39 % ёмкости: он зависит от того, далеко ли до следующего переезда. А вот как растут настоящие список и срез. Программа миллион раз добавляет элемент и печатает каждый переезд: новую ёмкость, во сколько раз она выросла и сменил ли буфер адрес. В Python адрес буфера достаётся через ctypes — так делают только ради такого опыта. Запустите несколько раз: ёмкости всегда одни и те же, а «переехал» или «вырос на месте» меняется от запуска к запуску.

Сколько это стоит

Память — O(n) с запасом до (r − 1)/r ёмкости: при удвоении в худший момент половина ячеек пустует. Плюс, в Python, сами объекты: список хранит восьмибайтные ссылки, а каждое число — отдельный объект в памяти.

Амортизация — обещание о сумме, а не о каждой операции. Массив на сто миллионов восьмибайтных элементов при переезде копирует 800 мегабайт, и именно этот append может прийтись на момент, когда программа должна ответить пользователю. Если размер известен заранее, место резервируют сразу: make([]T, 0, n) в Go, reserve в C++, new ArrayList<>(n) в Java. Замер ниже — цена одного append при росте с нуля и при заранее выделенном месте:

Обе линии в целом горизонтальные — это и есть O(1) амортизированно, видимое глазом. В Go рост с нуля обходится в несколько раз дороже заранее выделенного места: на каждый элемент приходятся переносы и выделения памяти. В Python разницы почти нет: запись по индексу в готовый список то чуть быстрее, то чуть медленнее append. Интерпретатор тратит на каждую строку цикла больше, чем стоят все переезды вместе.

Где работает

Почти везде, где в программе написано «список». list в Python, срезы в Go, ArrayList в Java, std::vector в C++, Vec в Rust, массивы в JavaScript — динамические массивы с разными множителями. На них же стоят другие структуры: стек — это динамический массив, у которого трогают только конец; двоичная куча лежит в массиве, а хеш-таблица растёт ровно по тому же закону и с тем же доказательством.

Слабое место — вставка в начало и в середину: чтобы освободить ячейку, нужно сдвинуть весь хвост. Для очереди это значит, что list.pop(0) в Python стоит O(n), и для неё берут collections.deque, которая умеет быстро работать с обоими концами. Для текстового редактора, который вставляет символы посреди мегабайтного файла, придумали верёвку и буфер с разрывом. А связный список вставляет в середину за O(1), но проигрывает массиву на переборе из-за кэша.

История

Растущие таблицы с удвоением в программах встречались давно, но слово для их цены появилось позже. В 1985 году Роберт Тарьян в обзоре «Amortized Computational Complexity» описал, как оценивать не каждую операцию по отдельности, а их сумму по всей последовательности, и показал два способа такого счёта: банковский, с отложенными монетами, и через потенциал. Правило «расти при заполнении, сжимайся при четверти» стало классическим примером такого анализа — его разбирают, например, в учебнике Кормена, Лейзерсона, Ривеста и Штайна.

Задачи

В первой задаче нужно предсказать рост настоящего списка Python на любом числе append, вплоть до 10¹⁸, — перебором по одному не успеть. Во второй склад то арендует зал побольше, то съезжает в поменьше, и нужно посчитать, сколько коробок перевезут при двух правилах переезда.