Оптимизации, используемые в Python: список и кортеж
В Python, есть два похожих типа — список (list) и кортеж (tuple). Самая известная разница между ними состоит в том, что кортежи неизменяемы.
Вы не можете изменить объекты в tuple:
Но вы можете модифицировать изменяемые объекты внутри кортежа:
Внутри CPython (стандартного интерпретатора), список и кортеж реализованы как лист из указателей (ссылок) на Python объекты, т.е. физически они не хранят объекты рядом с друг другом. Когда вы удаляете объект из списка происходит удаление ссылки на этот объект. Если на объект ещё кто-то ссылается, то он продолжит находиться в памяти.
Кортежи
Несмотря на тот факт, что кортежи намного реже встречаются в коде и не так популярны, это очень фундаментальный тип, который Python постоянно использует для внутренних целей.
Вы можете не замечать, но вы используете кортежи когда:
- работаете с аргументами или параметрами (они хранятся как кортежи)
- возвращаете две или более переменных из функции
- итерируете ключи-значения в словаре
- используете форматирование строк
Пустые списки vs пустые кортежи
Пустой кортеж работает как синглтон, т.е. в памяти запущенного Python скрипта всегда находится только один пустой кортеж. Все пустые кортежи просто ссылаются на один и тот же объект, это возможно благодаря тому, что кортежи неизменяемы. Такой подход сохраняет много памяти и ускоряет процесс работы с пустыми кортежами.
Но это не работает со списками, ведь они могут быть изменены:
Оптимизация выделения памяти для кортежей
Для того, чтобы снизить фрагментацию памяти и ускорить создание кортежей, Python переиспользует старые кортежи, которые были удалены. Если кортеж состоит из менее чем 20 элементов и больше не используется, то вместо удаления Python помещает его в специальный список, в котором хранятся свободные для повторного использования кортежи.
Этот список разделен на 20 групп, где каждая группа представляет из себя список кортежей размера n, где n от 0 до 20. Каждая группа может хранить до 2 000 свободных кортежей. Первая группа хранит только один элемент и представляет из себя список из одного пустого кортежа.
В примере выше, мы можем видеть, что a и b имеют одинаковый адрес в памяти. Это происходит из-за того, что мы мгновенно заняли свободный кортеж такого же размера.
Оптимизация выделения памяти для списков
Так как списки могут изменяться, такую же оптимизацию как в случае с кортежами провернуть уже не получится. Несмотря на это, для списков используется похожая оптимизация нацеленная на пустые списки. Если пустой список удаляется, то он так же может быть переиспользован в дальнейшем.
Изменение размера списка
Чтобы избежать накладные расходы на постоянное изменение размера списков, Python не изменяет его размер каждый раз, как только это требуется. Вместо этого, в каждом списке есть набор дополнительных ячеек, которые скрыты для пользователя, но в дальнейшем могут быть использованы для новых элементов. Как только скрытые ячейки заканчиваются, Python добавляет дополнительное место под новые элементы. Причём делает это с хорошим запасом, количество скрытых ячеек выбирается на основе текущего размера списка — чем он больше, тем больше дополнительных скрытых слотов под новые элементы.
Эта оптимизация особенно выручает, когда вы пытайтесь добавлять множество элементов в цикле.
Паттерн роста размера списка выглядит примерно так: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…
Для примера, если вы хотите добавить новый элемент в список с 8 элементами, то свободных ячеек в нём уже не будет и Python сразу расширит его размер до 16 ячеек, где 9 из них будут заняты и видны пользователю.
Формула выбора размера написанная на Python:
Скорость
Если сравнивать эти два типа по скорости, то в среднем по больнице, кортежи слегка быстрее списков. У Raymond Hettinger есть отличное объяснение разницы в скорости на stackoverflow.
Python для начинающих: какая разница между tuple, list и set?
Язык программирования Python предоставляет четыре встроенных типа данных для хранения коллекций из объектов. Все они наделены различными свойствами и характеристиками: list (список), tuple (кортеж), set (множество) и dictionary (словарь).
В статье обсудим различия между списками, кортежами, множествами и словарями, а также поразмышляем, когда лучше использовать каждый из встроенных типов последовательностей Python.
Примечание: поскольку словарь связывает соответствующие значения с ключами, а это совсем другой сценарий использования по сравнению со списками, множествами и кортежами (которые просто содержат значения), словарь не участвует в обсуждении.
Встроенные типы данных Python для хранения коллекций объектов
Зачем вообще выбирать?
По большей части любая из последовательностей Python применяется на практике без особых проблем, в любом приложении. Однако представьте, что перед вами поставлена легендарная задача найти иголку в стоге сена: какой тип данных Python эффективнее всего справится с такой задачей с точки зрения скорости и памяти?
Может стог сена — это список? Как насчет кортежа? Почему бы не использовать множества всегда? На какие предостережения следует обратить внимание?
Отличия между списком, кортежем и множеством
- Отличие 1: дубликаты.
Говоря проще, List и Tuple в Python как двойняшки разного пола, а тип данных Set для них как двоюродный брат. В отличие от списков или кортежей, множество не содержит дубликатов. Другими словами, элементы множества всегда уникальны. Получается, что множество удобно удаляет дубликаты, словно создано именно для этого.
- Отличие 2: упорядоченность.
Наверняка вы слышали утверждение “множества и словари в Python не упорядочены”, но на сегодняшний день — это лишь половина правды в зависимости от того, какой версией Python вы пользуетесь. До Python версии 3.6 словари и множества действительно не сохраняли порядок элементов, но начиная с Python 3.7, dictionary и set официально упорядочены по времени добавления элементов. А вот list и tuple — это всегда упорядоченные последовательности объектов.
- Отличие 3: индексация.
Что списки, что кортежи — оба поддерживают индексацию и срезы, а вот множества — нет.
Когда выбирать список, а когда — кортеж?
Как упоминалось в руководстве ранее, кортеж — неизменяемый тип данных, тогда как список — изменяемый. Кроме того, размер кортежа фиксированный, а вот размер списка — динамический.
- Список подходит, если:
- Последовательность планируется изменять.
- Планируется постепенно добавлять новые элементы в последовательность или удалять старые.
- Кортеж подходит, если:
- Последовательность НЕ планируется изменять.
- Все, что нужно от последовательности — это возможность поочередно перебирать постоянный набор элементов.
- Нужна последовательность элементов для ее назначения в качестве ключа словаря. Поскольку списки — это изменяемый тип данных, их нельзя применять в качестве ключей словаря.
- Важна скорость выполнения операций с последовательностью: из-за отсутствия возможности изменения, кортежи работают куда быстрее списков.
Когда выбирать множества?
Базовая структура типа данных “множество” — это хеш-таблица (Hash Table). Поэтому множества очень быстро справляются с проверкой элементов на вхождение, например содержится ли объект x в последовательности a_set .
Идея заключается в том, что поиск элемента в хэш-таблице — это операция O(1), то есть операция с постоянным временем выполнения.
Получается, всегда надо использовать множество?
По сути, если не нужно хранить дубликаты, то множество будет лучшим выбором, чем список.
Выводы
“Преждевременная оптимизация — корень всех зол”.
Итак, самое главное, что вам стоит запомнить по поводу списков, кортежей и множеств.
- Если необходимо хранить дубликаты, то выбирайте список или кортеж.
- Если НЕ планируется изменять последовательность после ее создания, то выбирайте кортеж, а не список.
- Если НЕ нужно хранить дубликаты, то воспользуйтесь множеством, так как они значительно быстрее определяют наличие объекта в последовательности.
В конечном итоге, по большей части не стоит слишком сильно задумываться о том, какого же типа данных последовательностью воспользоваться.
Главное — помнить о похожих чертах и особенностях встроенных типов данных Python.
Почему кортеж быстрее, чем список в Python?
Я только что прочитал в «Погружение в Python», что «кортежи быстрее списков».
Кортеж неизменен, а список изменчив, но я не совсем понимаю, почему кортеж быстрее.
Кто-нибудь делал тест производительности на этом?
8 ответов
Сообщаемое соотношение «скорость построения» сохраняется только для констант кортежей (те, чьи элементы выражены литералами). Внимательно наблюдайте (и повторите на своем компьютере — вам просто нужно набирать команды в командной оболочке / окне команд!) .
Я не проводил измерения на 3.0, потому что, конечно, у меня его нет — он полностью устарел, и нет абсолютно никаких причин его хранить, так как 3.1 превосходит его во всех отношениях (Python 2.7, если вы может обновиться до него, то есть почти на 20% быстрее, чем 2,6 в каждой задаче — и 2,6, как вы видите, быстрее, чем 3,1 — так что, если вы серьезно относитесь к производительности, Python 2.7 действительно единственный выпуск, который вам следует идти за!).
В любом случае, ключевым моментом здесь является то, что в каждом выпуске Python построение списка из константных литералов примерно одинаково или чуть медленнее, чем построение его из значений, на которые ссылаются переменные; но кортежи ведут себя по-разному — построение кортежа из константных литералов обычно в три раза быстрее, чем построение его из значений, на которые ссылаются переменные! Вы можете задаться вопросом, как это может быть, верно? -)
Ответ: кортеж, составленный из константных литералов, может быть легко идентифицирован компилятором Python как один, сам неизменяемый константный литерал: так что он по сути создается только один раз, когда компилятор превращает источник в байт-коды, и спрятан в «таблице констант». «соответствующей функции или модуля. Когда эти байт-коды выполняются, им просто нужно восстановить предварительно созданный постоянный кортеж — эй presto! -)
Эту простую оптимизацию нельзя применить к спискам, поскольку список является изменяемым объектом, поэтому очень важно, чтобы одно и то же выражение, например [1, 2, 3] , выполнялось дважды (в цикле — модуль timeit делает цикл от вашего имени ;-), каждый раз заново создается новый новый объект списка — и эта конструкция (например, конструкция кортежа, когда компилятор не может тривиально идентифицировать его как константу времени компиляции и неизменный объект) действительно требует немного времени
Тем не менее, конструкция кортежа (когда обе конструкции на самом деле должны происходит примерно вдвое быстрее, чем создание списка — и это несоответствие можно объяснить простой простотой кортежа, о которой неоднократно упоминались другие ответы. Но эта простота не учитывает ускорение в шесть и более раз, как вы заметите, если сравнить только списки и кортежи с простыми константными литералами в качестве их элементов! _)
Кортежи идентифицируются компилятором Python как одна неизменяемая константа, поэтому компилятор создал только одну запись в хеш-таблице и никогда не менялся
Списки являются изменяемыми объектами. Поэтому компилятор обновляет запись, когда мы обновляем список, поэтому он немного медленнее по сравнению с кортежем
Одна область, где список заметно быстрее, — это построение из генератора, и, в частности, понимание списка намного быстрее, чем ближайший эквивалент кортежа, tuple() с аргументом генератора:
В частности, обратите внимание, что tuple(generator) кажется чуть-чуть быстрее, чем list(generator) , но [elem for elem in generator] намного быстрее, чем оба.
С помощью модуля timeit вы часто можете самостоятельно решать вопросы, связанные с производительностью:
Это показывает, что кортеж ничтожно быстрее, чем список для итерации. Я получаю аналогичные результаты для индексации, но для построения кортеж уничтожает список:
Так что, если скорость итерации или индексирования являются единственными факторами, разницы практически нет, но для построения выигрывают кортежи.
Алекс дал отличный ответ, но я попытаюсь остановиться на нескольких вещах, которые, я думаю, стоит упомянуть. Любые различия в производительности, как правило, невелики и зависят от конкретной реализации, поэтому не стоит ставить на них ферму.
В CPython кортежи хранятся в одном блоке памяти, поэтому для создания нового кортежа в худшем случае требуется один вызов для выделения памяти. Списки размещаются в двух блоках: фиксированный со всей информацией об объектах Python и блок переменного размера для данных. Это одна из причин того, почему создание кортежа происходит быстрее, но, вероятно, это также объясняет небольшую разницу в скорости индексации, так как указатель должен следовать меньше.
В CPython также есть оптимизации для сокращения выделения памяти: нераспределенные объекты списка сохраняются в свободном списке, поэтому их можно использовать повторно, но выделение непустого списка все еще требует выделения памяти для данных. Кортежи сохраняются в 20 свободных списках для кортежей разного размера, поэтому выделение небольшого кортежа часто вообще не требует каких-либо вызовов выделения памяти.
Подобные оптимизации полезны на практике, но они также могут поставить под угрозу слишком сильную зависимость от результатов timeit, и, конечно, они будут совершенно другими, если вы перейдете к чему-то вроде IronPython, где распределение памяти работает совсем по-другому.
В питоне у нас есть два типа объектов. 1 . Изменчивый , 2. Неизменное .
В python списки попадают под изменяемые объекты, а кортежи — под неизменяемые объекты.
Кортежи хранятся в одном блоке памяти. Кортежи неизменны Таким образом, он не требует дополнительного места для хранения новых объектов.
Списки расположены в двух блоках: фиксированный со всеми Python информация об объекте и блок переменного размера для данных.
По этой причине создание кортежа происходит быстрее, чем List.
Это также объясняет небольшую разницу в скорости индексации быстрее чем списки, потому что в кортежах для индексации следует меньше указателей.
Преимущества использования кортежей:
Кортежи состоят в том, что они используют меньше памяти, тогда как списки используют больше памяти.
Мы можем использовать кортежи в словаре в качестве ключа, но это невозможно с списки.
Мы можем получить доступ к элементам с индексом в кортежах и списках.
Недостатки кортежей:
Мы не можем добавить элемент в кортеж, но мы можем добавить элемент в список.
Мы не можем отсортировать кортеж, но в списке мы можем отсортировать, вызвав list.sort() метод.
Мы не можем удалить элемент в кортеже, но в списке, мы можем удалить элемент.
Мы не можем заменить элемент в кортеже, но вы можете в списке.
По сути, потому что неизменность кортежа означает, что интерпретатор может использовать для него более гибкую и быструю структуру данных по сравнению со списком.
Управляющее резюме
Кортежи имеют тенденцию работать лучше, чем списки почти в каждой категории:
2) Кортежи можно использовать повторно вместо копирования.
3) Кортежи компактны и не перераспределяют.
4) Кортежи напрямую ссылаются на свои элементы.
Кортежи могут быть постоянно сложены
Кортежи констант могут быть предварительно вычислены оптимизатором глазков Python или AST-оптимизатором. Списки, с другой стороны, создаются с нуля:
Кортежи не нужно копировать
Запуск tuple(some_tuple) сразу же возвращает себя. Поскольку кортежи являются неизменяемыми, их не нужно копировать:
Напротив, list(some_list) требует, чтобы все данные были скопированы в новый список:
Кортежи не перераспределяют
Поскольку размер кортежа фиксирован, он может храниться более компактно, чем списки, которые необходимо перераспределить, чтобы сделать операции append () эффективными.
Это дает кортежам хорошее космическое преимущество:
Вот комментарий от Objects / listobject.c , который объясняет, что делают списки:
Кортежи ссылаются непосредственно на свои элементы
Ссылки на объекты включаются непосредственно в объект кортежа. Напротив, списки имеют дополнительный уровень косвенности к внешнему массиву указателей.
Это дает кортежам небольшое преимущество в скорости для индексированных поисков и распаковки:
Здесь как хранится кортеж (10, 20) :
Здесь как хранится список [10, 20] :
Обратите внимание, что объект кортежа включает два указателя данных напрямую, в то время как объект списка имеет дополнительный уровень косвенности к внешнему массиву, содержащему два указателя данных.