[Перевод] Оптимизации, используемые в Python: список и кортеж

В Python, есть два похожих типа — список (list) и кортеж (tuple). Самая известная разница между ними состоит в том, что кортежи неизменяемы.

Вы не можете изменить объекты в tuple:

>>> a = (1,2,3)
>>> a[0] = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Но вы можете модифицировать изменяемые объекты внутри кортежа:

>>> b = (1,[1,2,3],3)
>>> b[1]
[1, 2, 3]
>>> b[1].append(4)
>>> b
(1, [1, 2, 3, 4], 3)

Внутри CPython (стандартного интерпретатора), список и кортеж реализованы как лист из указателей (ссылок) на Python объекты, т.е. физически они не хранят объекты рядом с друг другом. Когда вы удаляете объект из списка происходит удаление ссылки на этот объект. Если на объект ещё кто-то ссылается, то он продолжит находиться в памяти.

Кортежи

Несмотря на тот факт, что кортежи намного реже встречаются в коде и не так популярны, это очень фундаментальный тип, который Python постоянно использует для внутренних целей.

Вы можете не замечать, но вы используйте кортежи когда:

• работайте с аргументами или параметрами (они хранятся как кортежи)
• возвращайте две или более переменных из функции
• итерируйте ключи-значения в словаре
• используйте форматирование строк

Как правило, самый просто скрипт использует тысячи кортежей:

>>> import gc
>>> def type_stats(type_obj):
...     count = 0
...     for obj in gc.get_objects():
...         if type(obj) == type_obj:
...             count += 1
...     return count
...
>>> type_stats(tuple)
3136
>>> type_stats(list)
659
>>> import pandas
>>> type_stats(tuple)
6953
>>> type_stats(list)
2455

Пустые списки vs пустые кортежи

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

>>> a = ()
>>> b = ()
>>> a is b
True
>>> id(a)
4409020488
>>> id(b)
4409020488
>>> # В CPython, функция id возвращает адрес в памяти.

Но это не работает со списками, ведь они могут быть изменены:

>>> a = []
>>> b = []
>>> a is b
False
>>> id(a)
4465566920
>>> id(b)
4465370632

Оптимизация выделения памяти для кортежей

Для того, чтобы снизить фрагментацию памяти и ускорить создание кортежей, Python переиспользует старые кортежи, которые были удалены. Если кортеж состоит из менее чем 20 элементов и больше не используется, то вместо удаления Python помещает его в специальный список, в котором хранятся свободные для повторного использования кортежи.

Этот список разделен на 20 групп, где каждая группа представляет из себя список кортежей размера n, где n от 0 до 20. Каждая группа может хранить до 2 000 свободных кортежей. Первая группа хранит только один элемент и представляет из себя пустой кортежей.

>>> a = (1,2,3)
>>> id(a)
4427578104
>>> del a
>>> b = (1,2,4)
>>> id(b)
4427578104

В примере выше, мы можем видеть, что a и b имеют одинаковый адрес в памяти. Это происходит из-за того, что мы мгновенно заняли свободный кортеж такого же размера.

Оптимизация выделения памяти для списков

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

>>> a = []
>>> id(a)
4465566792
>>> del a
>>> b = []
>>> id(b)
4465566792

Изменение размера списка

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

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

Паттерн роста размера списка выглядит примерно так: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…

Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.

Формула выбора размера написанная на Python:

>>> def get_new_size(n_items):
...     new_size = n_items + (n_items // 2 ** 3)
...     if n_items < 9:
...             new_size += 3
...     else:
...             new_size += 6
...
...     return new_size
...
>>> get_new_size(9)
16

Скорость

Если сравнивать эти два типа по скорости, то в среднем по больнице, кортежи слегка быстрее списков. У Raymond Hettinger есть отличное объяснение разницы в скорости на stackoverflow.

P.S.: Я являюсь автором этой статьи, можете задавать любые вопросы.

Let's block ads! (Why?)