Главная » Хабрахабр » [Перевод] Оптимизации, используемые в Python: список и кортеж

[Перевод] Оптимизации, используемые в 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 помещает его в специальный список, в котором хранятся свободные для повторного использования кортежи.

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

>>> 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.

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

OWASP Proactive Controls: cписок обязательных требований для разработчиков ПО

Данная статья содержит список техник по обеспечению безопасности, обязательных для реализации при разработке каждого нового проекта.Недостаточно защищенное ПО подрывает безопасность объектов критической инфраструктуры, относящихся, например, к здравоохранению, обороне, энергетике или финансам. Предлагаем вашему вниманию Top 10 Proactive Controls for Software ...

— А вы там в нефтехимии бензин делаете, да?

Привет, Хабр! Понятно, по пути будем упрощать, чтобы не превращать рассказ в занудную лекцию с перечислением всей таблицы Менделеева (кстати, 2019 год – официально год периодического закона, в честь 150-летия его открытия). Продолжая серию наших публикаций, мы решили, что для ...