Список в Python — массив указателей, а не массив значений. Из этой одной фразы выводится закон роста, разница между append и insert(0) в тысячу раз, и то, почему миллион чисел весит тридцать шесть мегабайт вместо восьми.
import sys
l = []
for i in range(10):
print(len(l), sys.getsizeof(l))
l.append(i)len: 0 1 2 3 4 5 6 7 8 9
байт: 56 88 88 88 88 120 120 120 120 184import timeit
print(timeit.timeit("l.append(1)", "l=[]", number=100_000))
print(timeit.timeit("l.insert(0,1)", "l=[]", number=100_000))0.0013
1.5814import sys
print(sys.getsizeof((1, 2, 3)))
print(sys.getsizeof([1, 2, 3]))64
88big = list(range(200_000))
bigs = set(big)
# сколько времени займёт 200 проверок "последний элемент внутри?"в списке 0.204 c
в множестве 0.000012 cin.Из урока 01: имя — ссылка на объект. Контейнер — это объект, который держит такие же ссылки. Отсюда всё дальнейшее.
Список — это непрерывный массив указателей плюс два числа: сколько элементов занято и сколько места выделено. Сами объекты лежат где угодно в куче, список знает только их адреса.
Массив выделяется с запасом. Иначе каждый append требовал бы перевыделения и копирования.
Когда занятых мест становится столько же, сколько выделенных, список просит новый блок по формуле новый = размер + размер/8 + константа — примерно ×1.125, а не ×2, как в std::vector.
Фрагмент A показывает это напрямую: 56 байт у пустого списка (только заголовок), 88 после первого append — выделено место под четыре указателя, потом скачок на пятом элементе, потом на девятом. Скачки становятся всё реже, но всё крупнее.
Отсюда амортизированная O(1) для append: перевыделение случается редко, и стоимость копирования размазывается. И отсюда же — коэффициент 1.125 выбран как размен: меньше памяти впустую, чаще копирования. C++ выбрал другую точку на том же компромиссе.
Массив непрерывен, значит вставить элемент в начало — это сдвинуть все существующие указатели на одну позицию вправо. Для списка из N элементов это N операций, для цикла из N вставок — N².
Фрагмент B: 0.0013 секунды против 1.58. Разница не в «медленном методе», а в том, что append пишет в свободный хвост, а insert(0, …) двигает весь массив. Та же логика у pop(0) и у del l[0].
Если нужны обе стороны — существует collections.deque: двусвязный список блоков, у которого добавление и удаление с любого конца стоит O(1). Ценой того, что доступ по индексу в середину становится O(n).
Фрагмент C. Кортеж неизменяем, значит ему не нужно поле «сколько выделено» — размер известен навсегда, и указатели лежат прямо в теле объекта, а не в отдельном блоке. Одна аллокация вместо двух, на 24 байта меньше.
Из неизменяемости следует и второе: кортеж может быть ключом словаря, а список — нет. И третье, менее известное: CPython держит списки свободных кортежей малых размеров и переиспользует их, потому что кортежи создаются и умирают массово — на каждой распаковке, на каждом возврате нескольких значений.
in по списку — это переборСписок не знает ничего о своих элементах, кроме адресов. Значит проверка «есть ли здесь x» может быть только линейным перебором со сравнением каждого элемента. Никакой структуры для поиска в списке нет и быть не может.
Множество и словарь устроены иначе: они считают хеш и идут сразу в нужную корзину. Отсюда фрагмент D и семнадцать тысяч раз разницы. Оператор in один, а стоящие за ним механизмы принципиально разные — и выбор структуры данных здесь не микрооптимизация, а выбор класса сложности.
Как устроено множество изнутри — в уроке 05. Здесь достаточно вывода: если по коллекции ищут, она не должна быть списком.
Раз список хранит указатели, его собственный размер — 8 байт на элемент. Но сами объекты живут отдельно, и вместе с ними считать надо и их. Из урока 02 известно, что целое весит 28 байт:
| миллион целых | память |
|---|---|
| массив указателей в списке | 8 МБ |
миллион объектов int | 28 МБ |
| итого | ~36 МБ |
numpy.arange с int64 | 8 МБ |
то же с int32 | 4 МБ |
Вот и весь numpy одной строкой: он не ускоряет модель, он выносит однородные данные за её пределы. Ни объектов, ни указателей — один непрерывный буфер, с которым работает скомпилированный код. Разница в девять раз по памяти и на порядки по скорости берётся отсюда, а не из того, что «C быстрее».
sys.getsizeof при этом честно врёт: он показывает только сам список, без содержимого. Для полной картины нужен обход или tracemalloc.
Сжатие есть, но не всегда. Список действительно уменьшает выделенный блок — но только когда занятых мест становится меньше половины выделенных, и не до фактического размера, а по той же формуле с запасом. Удаление одного элемента из тысячи не вернёт ничего; удаление девятисот вернёт почти всё. Проверить это на своей версии стоит замером, а не доверием к тексту 🔧.
Срез копирует. l[:] и l[10:20] создают новый список с новыми указателями — из урока 01 известно, что копия при этом поверхностная. Взгляда на данные без копирования у списка нет; он есть у memoryview и у numpy, но только для буферов, а не для объектов.
Числа роста — деталь реализации 🔧. Формула менялась и может меняться дальше; гарантируется только амортизированная сложность операций, записанная в документации, а не конкретный размер выделенного блока.
Тот же корень R1: значение — объект, контейнер хранит ссылки. Альтернативы у Python не было — раз элементы могут быть чем угодно и разного размера, хранить их по значению в непрерывном массиве нельзя физически.
Отсюда честная формулировка компромисса. Список Python — универсальная структура: гетерогенная, растущая, принимающая любые объекты. За универсальность заплачено косвенностью на каждом обращении и раздельной памятью. Специализированные структуры в стандартной библиотеке — array.array для однородных чисел, bytes и bytearray для байт, deque для очередей — существуют ровно как точечные отказы от этой универсальности там, где она не нужна.
Список объектов против массива numpy — это ровно та же развилка, что разреженное представление против плотного. Список хранит адреса и позволяет элементам быть чем угодно и лежать где угодно; плотный массив фиксирует тип и раскладку и получает за это последовательный доступ и работу в кэше.
И следствие переносится: как в разреженных матрицах поэлементный доступ дороже, чем в плотных, так и обход списка объектов дороже обхода буфера, даже если операция та же. Причина одинаковая — указатель, по которому надо сходить.
Вопросы, которые возникают сами, если читать внимательно. Ответ — под вопросом.
Нельзя, пока список обязан принимать что угодно. Массив значений требует, чтобы все элементы были одного размера; список Python обязан хранить рядом число, строку и функцию.
Это прямое следствие R1. Раз значение — объект в куче, единственное, что помещается в ячейку фиксированного размера, — адрес. Отсюда всё поведение: обход списка это прыжки по куче, а не последовательное чтение, поэтому кеш процессора работает плохо и миллион чисел стоит 36 МБ вместо 8.
Иначе — можно, и в стандартной библиотеке это есть:
import array, sys
a = array.array("q", range(1_000_000)) # знаковые 8-байтовые
print(sys.getsizeof(a) / 1e6, "МБ") # → около 8
print(sys.getsizeof(list(range(1_000_000))) / 1e6, "МБ") # → около 8 плюс сами объектыarray хранит значения, а не ссылки, — и платит за это тем, что тип фиксирован при создании. numpy делает то же самое, добавляя размерность и векторные операции. Выбор не между «правильно» и «неправильно», а между однородностью и универсальностью, и Python сделал универсальность умолчанием.
list.pop(0) медленный, а deque.popleft() — нет?Потому что это разные структуры данных, а не разная реализация одной.
Список — непрерывный массив указателей. Удаление с начала обязано сдвинуть все остальные элементы на одну позицию влево: N операций memmove. deque — двусвязный список блоков по 64 указателя, и удаление с любого конца это сдвиг индекса внутри блока.
import timeit
print(timeit.timeit("while l: l.pop(0)", "l=list(range(100_000))", number=1))
print(timeit.timeit("while d: d.popleft()",
"import collections; d=collections.deque(range(100_000))", number=1))
# → 0.738
# → 0.0035 в 213 раз213 раз на ста тысячах элементов, и разрыв растёт линейно с длиной — это разница между O(n) и O(1) на каждой операции, то есть между O(n²) и O(n) на цикле.
Цена deque: доступ по индексу в середину — O(n), потому что придётся идти по блокам. Правило выбора простое: обращаешься по индексу — список; добавляешь и снимаешь с концов — deque. Очередь, буфер последних N событий, обход в ширину — всё это deque.
На создании — да, ощутимо. На обходе — нет вообще. И знать, где именно разница, полезнее, чем общее «кортежи быстрее».
import timeit
print(timeit.timeit("(1,2,3,4,5)", number=3_000_000))
print(timeit.timeit("[1,2,3,4,5]", number=3_000_000))
# → 0.022
# → 0.131 в 5.9 раза
s = "t=tuple(range(1000)); l=list(range(1000))"
print(timeit.timeit("sum(t)", s, number=20_000))
print(timeit.timeit("sum(l)", s, number=20_000))
# → 0.127
# → 0.135 разницы нетОткуда шестикратная разница на создании. Не из «кортеж легче»: кортеж из литералов целиком складывается компилятором в константу (урок 22, фаза 5), и создание — это просто загрузка готового объекта. Список константой быть не может, его собирают инструкциями при каждом проходе.
Отсюда правильный вывод: выигрыш не в типе, а в том, что неизменяемое можно вычислить заранее. Кортеж из вычисляемых значений собирается почти так же, как список.
Выбирать между ними надо по смыслу — «фиксированная запись из разнородных полей» против «однородная последовательность переменной длины», — а из этого выбора уже следуют и хешируемость, и 64 байта против 88, и возможность стать ключом словаря.
Потому что удвоение — плохой компромисс на маленьких списках, а их подавляющее большинство.
CPython наращивает буфер примерно на 12.5% сверх нужного, с округлением и с особыми правилами для первых нескольких элементов. Последовательность видна прямо:
import sys
l = []
prev = -1
for i in range(70):
if sys.getsizeof(l) != prev:
prev = sys.getsizeof(l)
print(len(l), prev)
l.append(i)Почему не 2×. Удвоение даёт в среднем 50% перерасхода памяти; при 12.5% амортизированная сложность append остаётся O(1), а перерасход в четыре раза меньше. Для языка, где списков в программе десятки тысяч и почти все короткие, это выгоднее.
И обратная операция существует, вопреки распространённому «список никогда не уменьшается»:
l = list(range(1000))
print(sys.getsizeof(l)) # → 8056
del l[100:]
print(sys.getsizeof(l)) # → 984 буфер сжалсяКонкретные числа — 🔧 целиком: формула менялась и может меняться. Гарантируется только амортизированная сложность, записанная в документации. Тест, сверяющий getsizeof списка с константой, сломается на следующем релизе.
append и линейная стоимость insert(0), дающая в замере разницу в тысячу двести раз. Кортеж дешевле на 24 байта, потому что неизменяем и не нуждается в поле запаса. Проверка in по списку — перебор, потому что список не знает о своих элементах ничего, кроме адресов; та же операция по множеству быстрее на четыре порядка, и это выбор класса сложности, а не микрооптимизация. И память списка объектов складывается из двух сумм — указателей и самих объектов, — из-за чего миллион целых занимает тридцать шесть мегабайт вместо восьми. Именно эта арифметика делает numpy не ускорителем, а выходом за пределы объектной модели.
C++ std::vector<int> хранит значения непосредственно: миллион чисел это восемь мегабайт одним куском, и обход не выходит за пределы кэша процессора. Цена — вектор однороден по типу, и это известно на этапе компиляции.
Java ArrayList<Integer> болеет тем же, чем Python: это массив ссылок на объекты-обёртки, с той же двойной памятью и той же косвенностью. Именно поэтому в Java для чисел держат int[], а не ArrayList, — то самое «два набора правил», о котором шла речь в уроке 02.
Go хранит значения в слайсе непосредственно, но len и cap вынесены наружу и видны программисту: рост управляется вручную через make с запасом. Python прячет то же самое внутрь и решает за тебя.
Дедупликация с сохранением порядка. Читается идеально, работает квадратично.
result = []
for item in items:
if item not in result: # ← вот здесь
result.append(item)Код очевиден и правилен: пройти по элементам, добавить те, которых ещё нет. Ревьюер видит понятное намерение и одобряет. Но item not in result — это перебор всего накопленного списка на каждой итерации, то есть следствие 4 в цикле: сложность N².
| 9000 элементов, три прогона | время |
|---|---|
| проверка по списку | 0.058 с |
| проверка по множеству | 0.0004 с |
В полтораста раз, и на десяти тысячах элементов. На ста тысячах разница станет стократной от этой. Коварство в том, что на тестовых данных из полусотни записей код работает мгновенно, и проблема появляется только на реальном объёме — то есть после релиза.
seen = set()
result = []
for item in items:
if item not in seen:
seen.add(item)
result.append(item)Правило, выводимое из механизма, а не из опыта: если внутри цикла стоит in по списку, это цикл в цикле. Искать надо по множеству или словарю, а список оставить для порядка. Та же ошибка в другом обличье — list.remove и del l[0] в цикле: обе операции линейные.
Миллион чисел в списке против миллиона чисел в буфере. Разница не в скорости языка.
| миллион целых | память |
|---|---|
list(range(...)) | ~36 МБ |
array("q", ...) из стандартной библиотеки | 8 МБ |
numpy.arange(..., dtype=int32) | 4 МБ |
Тридцать шесть мегабайт складываются из восьми на массив указателей и двадцати восьми на сами объекты — прямо по следствию 5. Оба альтернативных варианта убирают и то, и другое: числа лежат по значению, без заголовков и без указателей.
Что выбрать. Если нужна только компактность и стандартная библиотека — array.array, он есть везде и не требует зависимостей. Если нужны ещё и векторные операции — numpy. Если данные разнородные или объекты сложные — оставаться со списком, потому что альтернативы к ним неприменимы.
Где это реально решает. Не там, где чисел тысяча, — там разница незаметна. А там, где коллекция живёт в памяти сервиса постоянно: справочник координат, буфер метрик, индекс идентификаторов. Тридцать шесть мегабайт на воркер против четырёх при двадцати воркерах — это уже разница между «влезаем» и «не влезаем».
Прогони четыре фрагмента, сверяясь с предсказанием. Затем:
l = list(range(1000))
sys.getsizeof(l)
del l[100:]
sys.getsizeof(l)
# Вернулась ли память? А если пересоздать список?
a = [1, 2, 3]
b = a * 3
sys.getsizeof(b)
# Во сколько раз больше и почему не ровно в три?
import array
arr = array.array("q", range(1_000_000))
sys.getsizeof(arr), sys.getsizeof(list(range(1_000_000)))
# Почему для array getsizeof честен, а для списка нет?
# Без кода: почему tuple может быть ключом словаря,
# а tuple со списком внутри — нет?Третий вопрос — самый важный: он про то, что getsizeof измеряет объект, а не достижимый из него граф, и это ловушка при любых замерах памяти.
Lib/heapq.py — сто пятьдесят строк чистого Python, где обычный список используется как двоичная куча. Индексы детей вычисляются арифметикой: у элемента i дети 2i+1 и 2i+2.
Заметь, почему это работает: доступ по индексу к списку — константный, потому что это массив. На связном списке та же куча была бы бессмысленна. Вся структура данных существует за счёт свойства из следствия 1, и это хороший пример того, как раскладка в памяти определяет, какие алгоритмы вообще возможны.
Второе место — Lib/collections/__init__.py. Посмотри, ради чего заведён deque и как в документации к нему прямо написано про O(1) с обоих концов против O(n) у списка. Стандартная библиотека здесь не скрывает компромисс, а называет его.
Из L1 ты знаешь, что список — массив указателей с запасом. Здесь — точная структура и во что обходится лишний переход по адресу.
Объект списка состоит из заголовка переменной длины (24 байта: счётчик ссылок, тип, длина), указателя на массив элементов и поля allocated. Итого 56 байт у пустого списка. Сам массив указателей выделяется отдельно — это вторая аллокация, и она же объясняет, почему getsizeof пустого списка не ноль, а размер после первого append прыгает сразу на 32 байта: выделено место под четыре указателя.
Полная таблица скачков для первых семидесяти элементов:
len: 0 1 5 9 17 25 33 41 53 65
байт: 56 88 120 184 248 312 376 472 568 664Видно, что запас растёт пропорционально размеру — это и есть множитель 1.125 из следствия 1.
Цена косвенности. Обход списка объектов — это для каждого элемента: прочитать указатель из массива, сходить по нему в кучу, прочитать заголовок объекта, достать значение. Четыре обращения к памяти вместо одного, причём объекты разбросаны по куче и почти наверняка лежат в разных строках кэша. Обход numpy-массива — последовательное чтение подряд лежащих байт, которое процессор предсказывает и загружает заранее.
Отсюда практический ориентир: разрыв между списком и буфером тем больше, чем больше данных и чем проще операция. На сложной поэлементной логике разница сглаживается, потому что доминирует сама логика; на простом суммировании она максимальна.
Тег v3.11.15.
Objects/listobject.c, функция list_resize — там буквально написана формула роста: new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3. Одна строка, из которой выведено следствие 1.Objects/listobject.c, ins1 — вставка со сдвигом через memmove. Следствие 2 в виде кода.Objects/tupleobject.c — раскладка кортежа и списки свободных объектов для малых размеров.Modules/_collectionsmodule.c — deque как двусвязный список блоков фиксированного размера; интересно, что блок держит несколько элементов сразу, чтобы не платить за узел на каждый.in константнымstd::vector<int> и Go-слайсы: значения по месту против указателейdeque против списка: O(1) с обоих концов ценой доступа по индексуlist, deque, set. Ровно те гарантии сложности, на которые можно опираться, в отличие от размеров блоков.array — хватит разбора выше; идти туда за кодами типов, когда понадобится.Objects/listobject.c, функция list_resize — тридцать строк, читаются целиком и лучше любого объяснения роста, включая это.