Список против кортежа: 16 байт, которые получаются только при одном сравнении из трёх, и две операции, в которых разницы нет

Что здесь на самом деле спрашивают

Расхожий ответ на этот вопрос сводится к двум придаточным: кортеж неизменяемый, поэтому легче и быстрее.

Оба следствия неточны, и неточны по-разному. «Легче» — верно, но величина зависит от того, какой список вы взяли для сравнения, и разброс там четырёхкратный. «Быстрее» — верно для одной операции из пяти, и по причине, которая к неизменяемости отношения не имеет.

Разбираем по одному — но сначала о том, из-за чего эти два типа вообще разные.

База: список меняется, кортеж — нет

Различие между ними начинается не с байтов, а с одного слова.

Список — изменяемая последовательность. В него можно добавить элемент, убрать, заменить один на другой — и объект при этом останется тем же самым.

Кортеж — неизменяемая. После создания состав его элементов менять нельзя: ни добавить, ни удалить, ни присвоить по индексу. t[0] = ... даёт TypeError: 'tuple' object does not support item assignment.

Всё, чего обычно ждут в ответе, следует из этого одного различия.

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

Второе: выбор типа — это сообщение читателю кода. Кортеж говорит «это одна запись фиксированной формы, у каждого места свой смысл»; список — «это сколько угодно однородных штук, и их число заранее не известно». Интерпретатор такого различия не требует, но именно оно и есть причина, по которой тип выбирают осознанно.

Третье: это же видно и в интерфейсе. Функция, вернувшая список, отдала наружу то, что вызывающий волен изменить, — и по этой причине list(l) обязан делать копию. В кортеже, который вернула функция, менять снаружи нечего, и копировать его незачем: tuple(t) is t — тот же объект.

Этого уже достаточно, чтобы ответить на базовый вопрос собеседования: что выбрать и почему. Всё дальнейшее — про приписку, которой этот ответ обычно заканчивают: «и поэтому кортеж легче и быстрее». Насколько легче, при каком сравнении — и в какой именно операции быстрее.

Механизм 1: ошибка, которая не падает

Как обычно, интересна не та ошибка, что роняет программу.

Правило про запятую в учебнике сформулировано прямо: a tuple with one item is constructed by following a value with a comma (it is not sufficient to enclose a single value in parentheses) (кортеж из одного элемента строится постановкой запятой после значения (заключить одно значение в скобки недостаточно)). В справочнике то же нормативно: it is actually the comma which makes a tuple, not the parentheses (кортеж на самом деле образует запятая, а не скобки).

Забыть запятую легко, а последствия зависят от того, что внутри:

ALLOWED = ("admin")      # ← запятой нет: это строка 'admin'
 
def allowed(role):
    return role in ALLOWED

Проверка «есть ли роль среди разрешённых» превратилась в проверку вхождения подстроки. Замер на шести именах — admin, adm, min, administrator, guest, a:

Трое лишних из шести, ни одного исключения. Программа не упала, тесты на allowed("admin") прошли, а allowed("a") вернуло True.

Второй способ получить неверный ответ молча — умножение:

grid = [[]] * 3          # три ссылки на ОДИН список
for i, row in enumerate(grid):
    row.append(i)
grid                     # [[0, 1, 2], [0, 1, 2], [0, 1, 2]]
[sum(r) for r in grid]   # [3, 3, 3] — одна строка, посчитанная трижды

Правильная форма — включение, которое создаёт новый объект на каждом шаге:

grid = [[] for _ in range(3)]   # [[0], [1], [2]]

С кортежем ровно то же самое: ([],) * 3 даёт три ссылки на один список. Неизменяемость кортежа здесь ни при чём — и это подводит к следующему разделу.

Механизм 2: неизменяемость неглубокая

Кортеж хранит ссылки, и запрет касается замены ссылок, а не объектов, на которые они указывают:

t = ([], [])
t[0].append("а меня можно")   # работает
t[0] = ["а меня нельзя"]      # TypeError: 'tuple' object does not
                              # support item assignment

Отсюда и оговорка к тому, что в «Базе» сказано про ключи словаря: «кортеж можно класть в словарь» — не всегда.

hash((1, "a", (2, 3)))   # ок
hash((1, [2, 3]))        # TypeError: unhashable type: 'list'

Кортеж хешируется, только если хешируется каждый его элемент. Один список внутри — и ключом такой кортеж уже не будет, причём узнаете вы об этом в момент вставки в словарь, а не в момент создания кортежа.

Есть и обратная сторона той же медали, полезная на практике: раз кортеж неизменяем, копировать его незачем.

t = (1, 2, 3);  tuple(t) is t   # True  — тот же объект
l = [1, 2, 3];  list(l)  is l   # False — копия

list(l) обязан копировать: вернув тот же объект, конструктор отдал бы наружу изменяемую ссылку на чужие данные. tuple(t) копировать не обязан — менять там нечего.

Механизм 3: 16 байт — откуда они берутся

Теперь к той самой приписке — «и поэтому легче». Начинается она с числа, которое проверяется одной строкой:

import sys
sys.getsizeof([None] * 10)     # 136
sys.getsizeof((None,) * 10)    # 120

Разница — 16 байт. И она не меняется с длиной, если брать список, построенный литералом (эта оговорка окажется решающей, но пока о ней можно не думать):

Постоянная разница означает постоянное поле, а не накладные расходы на элемент. Так и есть, и видно это в объявлениях структур.

У обоих объектов есть PyObject_VAR_HEAD — счётчик ссылок, указатель на тип и длина, всего 24 байта. Дальше они расходятся:

• у кортежа массив элементов лежит прямо в объекте, сразу за заголовком;
• у списка в объекте лежит только указатель на отдельный массив (8 байт) и поле allocated (ещё 8) — сколько места под этот массив выделено.

8 + 8 = 16. Поле allocated — это и есть то, чего у кортежа нет и быть не может: кортежу незачем помнить запас, потому что он не растёт.

Механизм 4: 16 байт — только против одного списка из трёх

Теперь та самая оговорка. Разница в 16 байт получена на списке, построенном литералом, а у такого списка запаса нет. Возьмите другой список той же длины:

sys.getsizeof((None,) * 17)     # 176 — кортеж, ровно 17 слотов
sys.getsizeof([None] * 17)      # 192 — список повторением: тоже ровно 17
sys.getsizeof([0, 1, 2, ..., 16])  # 200 — список литералом: 18 слотов
sys.getsizeof(list(range(17)))  # 200 — конструктор: тоже 18
grown = []
for i in range(17): grown.append(i)
sys.getsizeof(grown)            # 248 — вырос через append: 24 слота

Одна длина, четыре списка, три разных числа — и запаса нет только у того, что получен повторением. Литерал, вопреки ожиданию, тоже перевыделяет: список из одних констант компилятор собирает не поэлементно, а как BUILD_LIST 0 плюс LIST_EXTEND из готового кортежа, а list_extend идёт тем же путём, что и append. Против последнего кортеж легче не на 16 байт, а на 72. «Кортеж легче на 16 байт» верно ровно для одного сравнения из трёх — и это, а не какое-то скрытое поле, главная неточность расхожего ответа.

Обратите внимание, что́ здесь происходит: getsizeof показывает запас честно. 248 = 56 + 24 × 8, где 24 — сколько слотов выделено. Массив, на который список ссылается, входит в это число целиком.

Тогда что getsizeof действительно не считает

Документация формулирует ограничение прямо: Only the memory consumption directly attributed to the object is accounted for, not the memory consumption of objects it refers to (Учитывается только память, непосредственно занятая объектом, а не память объектов, на которые он ссылается). Речь про элементы, а не про массив указателей.

Проверить это можно, сведя два инструмента. tracemalloc на батче из 10 000 объектов, за вычетом самого списка, который держит батч (он стоит 8,51 байта на объект):

Они сходятся. Для этих объектов getsizeof не занижает ничего — и более строгий способ, мерить tracemalloc на батче объектов вместо sys.getsizeof поштучно, здесь ничего бы не изменил.

Почему сходятся — видно, если посмотреть на элементы. Это малые целые числа, то есть синглтоны: списку и кортежу принадлежат не они, а только указатели на них. Считать нечего.

Замените элементы на строки, которые создаются заново каждый раз, — и расхождение появляется сразу:

Вот здесь getsizeof и занижает — на 470 байт, то есть втрое. И занижает он именно то, о чём предупреждает документация: сами строки.

Практический вывод из этих двух таблиц один, и он не про списки: getsizeof надёжен ровно настолько, насколько элементы контейнера принадлежат кому-то ещё. Для контейнера общих объектов он точен; для контейнера собственных — показывает верхушку.

Возвращаемся к запасу — теперь понятно, что он не прячется, а просто зависит от способа построения.

Механизм 5: запас — цена того, что список умеет расти

Список, выросший через append, держит больше места, чем в нём элементов. Шаблон роста записан в комментарии над list_resize в Objects/listobject.c:

Проверено запуском — те же числа:

Список из 17 элементов держит место под 24. Кортеж из 17 держит 17.

По какому правилу он растёт

Лестница выше — это вывод правила, а не само правило. Само правило записано в list_resize одной строкой:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

То есть: новая длина плюс её восьмая часть плюс шесть, округлённое вниз до кратного четырём.

Здесь легко прочесть неверно, поэтому по шагам. Формула считает запас от длины, а не от прошлого запаса. Она отвечает на вопрос «в списке стало n элементов — сколько места под них выделить», и старое значение в неё не входит вовсе.

Формула проверяется на замере, а не принимается на слово, — первые двенадцать ступеней совпадают до единицы:

Почему «восьмая часть», а по таблице удвоение

В формуле два слагаемых, и на разной длине правит разное.

На коротком списке правит + 6. Для длины 1 восьмая часть — это ноль, и весь запас даёт шестёрка: 1 + 0 + 6 = 7, вниз до четырёх. Поэтому первые ступени и выглядят удвоением: 4 → 8 → 16.

На длинном правит len / 8. Шестёрка на фоне тысяч уже ничего не решает, и отношение соседних запасов сходится к 1,125. Это видно только на замере:

Вот что такое 1,125: предел, к которому отношение сходится на длинных списках, а не множитель на каждом шаге. Расхожее «список удваивается» верно ровно для первых двух ступеней и неверно дальше.

Чем это отличается от удвоения на практике

Удвоение — это vector в C++ и срез в Go до 256 элементов. Разница видна на счёте, если дорастить список до трёхсот тысяч элементов:

Вот и весь размен. Вчетверо больше перевыделений — ради того, чтобы готовый список не держал лишнего почти на три четверти своей длины. Для языка, где списки живут долго и их много, это разумная сторона размена; для языка, где важнее скорость роста, — другая.

Мотив в том же комментарии назван прямо, и это не экономия памяти: enough to give linear-time amortized behavior over a long sequence of appends() in the presence of a poorly-performing system realloc() (достаточно, чтобы дать амортизированно линейное время на длинной череде append() даже при неудачной системной реализации realloc()). Запас существует для того, чтобы тысяча append подряд стоила линейно, а не квадратично.

Два случая, где запас ведёт себя иначе

Большой скачок за один раз запаса не получает. В list_resize рядом с формулой стоит отдельная ветка: Do not overallocate if the new size is closer to overallocated size than to the old size (Не выделять с запасом, если новый размер ближе к размеру с запасом, чем к старому). Разница видна на одной тысяче элементов:

a = []; a.extend(range(1000))          # выделено под 1000
b = []
for i in range(1000): b.append(i)      # выделено под 1100

Ровно тысяча против тысячи ста. Это и есть измеренная цена совета «стройте одним выражением, а не циклом append».

Обратно память возвращается не сразу. Условие в начале list_resize пропускает realloc вовсе, пока длина держится в верхней половине запаса:

if (allocated >= newsize && newsize >= (allocated >> 1))

Поэтому список из тысячи элементов после четырёхсот pop всё ещё держит место под тысячу. Сжатие срабатывает на длине 499 — первой, что оказалась меньше половины, — и даёт ровно то, что предсказывает формула: 499 + 62 + 6 = 567, округлённое вниз до 564.

Практически это значит, что список, который однажды вырос до миллиона и потом опустел наполовину, память не отдаст.

Так объясняются три разных числа из раздела выше: 192, 200 и 248 при одной и той же длине. Повторение ([None] * 17) знает длину точно и запаса не берёт; литерал и list(range(17)) тоже знают её, но идут через list_extend и округляют до 18; выросший через append прошёл всю лестницу и остановился на 24.

Практическое следствие узкое, но полезное: если длина известна заранее, стройте одним выражением, а не циклом append. Не ради 56 байт на список, а ради того, что тогда размер предсказуем — пусть и с точностью до одного лишнего слота.

Механизм 6: «кортеж быстрее» — одна операция из пяти

Теперь второе следствие расхожего ответа. Замер (3.13.7, лучшее из семи прогонов по 2 000 000 повторов):

Смысл здесь имеет последняя колонка: кратность получена из двух чисел одного запуска и потому не зависит от того, чем машина была занята в момент замера. Наносекунды в первых двух — иллюстрация конкретного прогона, переносить их на свою машину не стоит.

Про каждую кратность прогон сам говорит, различима ли она прибором, — и для этого повторяет весь замер пятью отдельными процессами. Отдельными намеренно: внутри одного процесса пять повторов держатся своего значения, а между процессами строка «создать из переменных» уезжает с 1,29 на 1,79 — разброс живёт между запусками, а не внутри них, и замер, повторённый внутри процесса, показал бы ложно узкий размах.

  Различима ли каждая кратность прибором (размах по 5 процессам):
    создать литерал           4.08 ..  4.24   размах 0.16   различима да
    создать из переменной     1.29 ..  1.29   размах 0.01   различима да
    прочитать по индексу      1.08 ..  1.11   размах 0.02   различима да
    распаковать               0.99 ..  1.00   размах 0.01   различима нет
    обойти 1000 элементов     1.03 ..  1.03   размах 0.00   различима да

Две средние строки — чтение и распаковка, то, ради чего контейнер обычно и заводят. Распаковка разницы не даёт вовсе: размах лежит по обе стороны от единицы. А чтение по индексу — даёт: 1,08, устойчиво во всех пяти процессах.

И вот тут начинается самое интересное, потому что на 3.14.7 та же строка выходит ×0,92 — быстрее оказывается список, и тоже устойчиво, размах 0,03. Та же перемена знака на распаковке (×0,96) и на обходе (×0,83). Каждое из двух чисел верно внутри своего прогона; вместе они говорят одно: на четырёх строках из пяти знак принадлежит сборке, а не типу. Переносить с собой стоит не кратность, а первую строку — ту единственную, у которой есть объяснение в байт-коде, а не в замере.

А вот первая строка требует объяснения, потому что пятикратная разница на пустом месте не берётся.

Механизм 7: почему литерал — объяснение в байт-коде

Разница на первой строке видна дизассемблером и никакого секундомера не требует (дизассемблер 3.13.7):

x = (1, 2, 3)   ->  LOAD_CONST  STORE_NAME
                    co_consts: ((1, 2, 3), None)

x = [1, 2, 3]   ->  BUILD_LIST  LOAD_CONST  LIST_EXTEND  STORE_NAME
                    co_consts: ((1, 2, 3), None)

Константный кортеж во время исполнения не строится вовсе. Он собран на этапе компиляции и целиком лежит в co_consts; на месте выражения стоит одна инструкция — взять готовое. Списку так нельзя: он изменяем, и вернуть один и тот же объект на каждом проходе цикла означало бы отдать наружу общее состояние. Поэтому список собирается заново каждый раз — и, что любопытно, из той же самой константы: LIST_EXTEND разворачивает в него тот же кортеж (1, 2, 3), который лежит в co_consts у обоих.

Отсюда и граница действия этого преимущества. Стоит внутри появиться хоть одному неконстантному выражению:

x = (a, 2, 3)   ->  LOAD_NAME  LOAD_CONST  LOAD_CONST  BUILD_TUPLE  STORE_NAME
x = [a, 2, 3]   ->  LOAD_NAME  LOAD_CONST  LOAD_CONST  BUILD_LIST   STORE_NAME

Одна и та же форма, разная последняя инструкция — и разница падает впятеро с лишним до полутора раз.

На 3.14 те же строки выглядят чуть иначе: мелкие целые константы грузятся отдельной инструкцией LOAD_SMALL_INT. На вывод это не влияет — константный кортеж по-прежнему целиком лежит в co_consts, а список по-прежнему собирается.

Практический вывод: «кортеж быстрее» — это про константы, а не про типы. Если ваш кортеж собирается из переменных, вы получаете полтора раза на создании объекта, которое в горячем цикле обычно не главное.

Что с этим делать

Не выбирайте кортеж ради скорости. На чтении и распаковке разницы нет, на создании из переменных — полтора раза. Выигрыш в пять раз бывает только у константного литерала, и он не про типы, а про co_consts.

Выбирайте кортеж ради смысла. Учебник формулирует это как разницу намерений: кортеж usually contain a heterogeneous sequence of elements (обычно содержат разнородную последовательность элементов), список — their elements are usually homogeneous (их элементы обычно однородны). Кортеж говорит читателю кода «это одна запись фиксированной формы», список — «это сколько угодно однородных штук».

Ставьте запятую и проверяйте типом. ("admin") — строка. Если значение приходит извне или собирается условно, assert isinstance(x, tuple) дешевле разбирательства с тем, почему пользователь a оказался администратором.

Не считайте разницу в памяти одним сравнением. 16 байт (8 на 3.14) получаются только против списка, построенного литералом; против выросшего через append та же разница — 72 байта. И помните границу самого getsizeof: массив списка он считает целиком, а элементы — нет. Для контейнера общих объектов он точен, для контейнера собственных показывает верхушку.

Помните, что неизменяемость неглубокая. Кортеж с изменяемым элементом внутри не защищает ни от изменения, ни от TypeError при попытке сделать его ключом.

Глубже: что изменилось в 3.14

За четыре версии раскладка менялась ровно один раз, и знать об этом стоит: от версии зависит то самое число, которое вы увидите у себя в консоли.

sys.getsizeof(())    # 40 на 3.11, 3.12, 3.13
                     # 48 на 3.14

Прибавка постоянная — 8 байт при любой длине, — то есть в объект добавили одно поле. Это ob_hash, кеш хеша:

// Include/cpython/tupleobject.h, тег v3.14.0
typedef struct {
    PyObject_VAR_HEAD
    Py_hash_t ob_hash;      /* Cached hash. Initially set to -1 */
    PyObject *ob_item[1];
} PyTupleObject;

Разрыв между списком и кортежем стал вдвое меньше: 8 байт вместо 16.

Здесь есть соблазн, и его стоит назвать: увидеть, что на 3.14 повторный hash идёт быстрее, и написать «хеш стал вчетверо быстрее». Сравнивать время двух версий нельзя ни с числом, ни без него — сборки, на которых сняты эти числа, различаются не только версией языка, и такое сравнение ничего не доказывает.

Доказать наличие кеша можно внутри одного запуска, и это законно на любой версии: если кеша нет, повторный хеш того же объекта стоит столько же, сколько первый; если есть — заметно дешевле.

Три версии подряд говорят «кеша нет», четвёртая — «есть», и ровно там же кортеж прибавил 8 байт. Каждая строка — сравнение двух чисел одного прогона; между строками сравнивать нечего, и не нужно.

Заявленный эффект в самой задаче назван честно и узко: the mdp benchmark increased by 86% (тест mdp ускорился на 86 %), и тут же — no measurable improvement on any other benchmark, but it also seems to have no downside, including for memory usage (ни на одном другом тесте заметного улучшения нет, но и вреда, включая расход памяти, тоже не видно). Последнее относится к max_rss на наборе тестов, а не к размеру одного объекта: каждый кортеж стал на 8 байт больше, и getsizeof это показывает. Оба утверждения верны одновременно, и это ровно тот случай, ради которого стоит различать «память процесса» и «размер объекта».

История версий

Как отвечать на собеседовании

Короткий ответ: список — изменяемая последовательность, кортеж — неизменяемая, и выбирают между ними по этому, а не по байтам. Кортеж годится в ключи словаря, когда годится каждый его элемент, и говорит читателю «это одна запись фиксированной формы»; список говорит «это сколько угодно однородных штук». Разница в памяти есть, но она не то, ради чего тип меняют.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

Про память: список хранит указатель на отдельный массив плюс запас, кортеж — элементы в себе, отсюда и разница в getsizeof. Но она равна 16 байтам только при одном сравнении: кортеж против списка, построенного литералом. У выросшего через append есть запас, и на семнадцати элементах разница уже 72 байта.

Что отличает хороший ответ: не соглашаться с «кортеж быстрее» вообще, а назвать, где именно. Из пяти операций преимущество есть у одной — создания из литерала, — и не потому, что это кортеж: константный кортеж во время исполнения не строится вовсе, он лежит в co_consts. Поставьте внутрь переменную, и преимущество падает до полутора раз. На чтении по индексу и на распаковке разницы нет вовсе. И отдельно: кортеж неизменяем неглубоко — t = ([],), и t[0].append(1) работает.

Дальше спросят

Частые заблуждения

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ взят из прогона скрипта, а не назначен.

import sys

literal = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
grown = []
for n in range(17):
  grown.append(n)

print(literal == grown)
print(sys.getsizeof(literal) == sys.getsizeof(grown))
print(sys.getsizeof(literal), sys.getsizeof(grown))

True
False
200 248

True
True
200 200

True
False
248 200

False
False
200 248

Проверка знаний