Как растёт список Python
Список в CPython хранит ссылки на элементы в массиве с запасом. Пока запас есть, append просто пишет в следующую ячейку. Когда список полон и в него добавляют ещё один элемент, CPython выделяет новый массив. Если в списке станет s элементов (то есть s — размер вместе с добавляемым), новая ёмкость равна числу s + ⌊s/8⌋ + 6, округлённому вниз до кратного четырём:
В коде это одна строка: (s + (s >> 3) + 6) & ~3. У пустого списка ёмкость 0, поэтому первый же append выделяет 4 ячейки, дальше ёмкости идут так: 8, 16, 24, 32, 40, 52, 64, 76…
Будем считать, что при каждом выделении все элементы, которые уже были в списке, копируются в новый массив. Для каждого n ответьте: какой будет ёмкость после n вызовов append к пустому списку, сколько раз за это время выделялась память (первое выделение тоже считается) и сколько всего элементов было скопировано.
Это настоящее правило Python 3.13: генератор тестов сверяет его с sys.getsizeof на списках до ста тысяч элементов.
Вход
В первой строке число запросов q (1 ≤ q ≤ 100 000). Во второй — q чисел n (1 ≤ n ≤ 10¹⁸).
Выход
Для каждого запроса — строку из трёх чисел: ёмкость, число выделений памяти, число скопированных элементов. Все ответы помещаются в 64-битное целое со знаком.
Примеры
Пример 1
5 1 4 5 9 17
4 1 0 4 1 0 8 2 4 16 3 12 24 4 28
Пример 2
3 1000 1000000 1000000000000000000
1100 28 7556 1056084 86 8445096 1108046317219334708 321 8864370537754664216
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Прямая симуляция — по одному append до n — при n = 10¹⁸ не закончится никогда. Но между выделениями памяти ничего интересного не происходит: размер просто растёт на единицу. Можно ли прыгать от одного выделения сразу к следующему?
2Подсказка 2
Ёмкость растёт примерно в 1,125 раза. Сколько выделений нужно, чтобы дорасти до 10¹⁸? И зависит ли последовательность ёмкостей от n в запросе?
3Идея
Последовательность ёмкостей одна на все запросы: 0, 4, 8, 16, 24, 32… Каждая следующая получается из предыдущей c подстановкой s = c + 1 в формулу: выделение случается ровно тогда, когда в полный список добавляют ещё один элемент. Растёт она геометрически, и до 10¹⁸ в ней всего 322 члена. Посчитаем их один раз вместе с накопленным числом копирований, а на каждый запрос найдём двоичным поиском первую ёмкость, которая вмещает n.
4Разбор
Массив caps: caps[0] = 0, caps[k+1] = (s + (s >> 3) + 6) & ~3 при s = caps[k] + 1. Массив copies: copies[k+1] = copies[k] + caps[k] — при k+1-м выделении список был полон и переносил все свои caps[k] элементов (при первом выделении — ноль). Для запроса n индекс k первой ёмкости, не меньшей n, — это и число выделений, а ответ — caps[k] k copies[k].
Проверка на смысл: на миллионе append — 86 выделений и 8 445 096 копирований, примерно 8,4 на элемент. Это предсказывает теорема из статьи: при множителе r копирований на элемент меньше r/(r − 1), а у Python r ≈ 1,125 и предел — 9.
Почему не умножить на 1,125 в числах с плавающей точкой: формула с >> 3 целочисленная, а double хранит только 53 бита мантиссы. Пока ёмкость меньше 2⁵³ ≈ 9·10¹⁵, s * 1.125 + 6 вычисляется точно, а дальше младшие цифры теряются и ёмкости расходятся с настоящими. Второй пример это ловит.
4+Решение
5Сложность
Предподсчёт — O(log1,125 N), около 322 шагов. Каждый запрос — двоичный поиск по ним: O(q · log 322).
6Типичные ошибки
- Симуляция по одному append. Верно, но 10¹⁸ шагов — это годы.
- Множитель 1,125 в плавающей точке. Верно до 2⁵³ и неверно после.
- Забыть округление до кратного 4 или добавку 6. Последовательность уходит в сторону с первых шагов: без округления вместо 4, 8, 16, 24 получится 7, 15, 24, 34.
- Не считать первое выделение. Переход от пустого списка к четырём ячейкам — тоже выделение памяти, хотя копировать ещё нечего.