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

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

Списки и кортежи

Списки и кортежи — это типы массивов в Python. Могут быть различные способы реализации массивов, такие как статические и динамические. Кортежи — это статические массивы, а списки — это динамические массивы. Когда мы объявляем массивы, мы выделяем блок памяти для этого массива. Это делается путем запроса использования N последовательных сегментов данных. Эти сегменты памяти содержат целочисленные адреса фактических данных.

Так что в случае, если мы хотим найти что-то в этом массиве, нам придется просмотреть эти корзины и проверить данные по адресу, указанному в корзине. И если данные, которые мы ищем, отсутствуют, может потребоваться время O (n) для массива размера «n», если мы выполним линейный поиск, который проверит все элементы массива. Итак, как нам улучшить эту временную сложность?

Как улучшить поиск

Преобразуйте массив в другую структуру данных, например словарь, а затем выполните поиск. Но одним недостатком этого подхода является ограничение словарей наличием уникальных ключей, а время, необходимое для преобразования списка в словарь, также составляет O (n). Однако после завершения преобразования время поиска будет O (1) для каждого поиска.
Мы можем хранить элементы в списке в отсортированном порядке сортировка в python выполняется Tim sort с помощью функции list.sort(), которая в лучшем случае имеет временную сложность O(n) и O (nlogn) в худшем случае. После этого каждый поиск может быть выполнен с помощью двоичного поиска, который имеет сложность O (logn), поэтому мы в конечном итоге читаем небольшую часть массива.
Использование модуля bisect в python. Модуль bisect — это модуль, который упрощает добавление элементов при сохранении порядка массива. Поскольку он использует сильно оптимизированный бинарный поиск, временная сложность составляет O (logn).

import random
import bisect
original_numbers=[]
for i in range(10):
   new_number=random.randint(0,1000) 
   bisect.insort(original_numbers, new_number)

Обратите внимание, что операция insort занимает время O(n) для каждой вставки.

Списки

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

Если мы знаем индекс элемента, который хотим изменить, мы можем внести изменения за время O(1).
Мы также можем добавить к списку, так как динамический массив поддерживает операцию изменения размера, которая увеличивает емкость массива. Когда элемент добавляется к списку размера N, выделяется новая память размера M (вместо N+1), где M>N, так что дополнительные элементы также могут быть добавлены позже. Затем следует копирование всех данных из старого списка в новый список и уничтожение старого списка. По мере добавления данных мы увеличиваем эффективный размер списка N до тех пор, пока N==M. После этого создается новый список. В этом сценарии мы теряем время на копирование списка и дополнительный запас памяти, так как память M-N только что выделена, но не используется.

Кортежи

Кортежи неизменяемы, поэтому их нельзя изменить или изменить их размер. Вот чем кортежи отличаются от списков.

Конкатенация двух кортежей может быть выполнена для получения нового кортежа, мы не используем никакой дополнительной памяти, в отличие от операции изменения размера списков. Но эта операция занимает время сложности O(n) вместо O(1) для добавления в списки (пока у нас не закончится дополнительное пространство), поскольку каждый раз нам приходится копировать старые кортежи в новые. кортеж1=(1,2,3) кортеж2=(4,5,6)
кортеж3=кортеж1+кортеж2
Кортежи предпочтительнее, когда данные являются статическими, поскольку кортежи не требуют дополнительного запаса. Список размером 100 000 000, созданный с помощью append, фактически будет использовать память размером 112 500 007, с другой стороны, кортеж размером 100 000 000 будет использовать только 100 000 000 памяти, что делает кортежи легкими.
Списки, созданные без добавления, по-прежнему будут занимать больше памяти, чем кортежи того же размера. Это связано с тем, что списки отслеживают больше данных, чем кортежи, для изменения размера, что может привести к значительному увеличению числа, если мы используем много списков.
Еще одно преимущество кортежей заключается в том, что python использует кэширование ресурсов. В python, когда мы не используем переменную, память освобождается обратно в ОС. Но для кортежей размером 1–20 этот размер сохраняется для будущего использования, когда нам понадобится новый кортеж этого размера, вместо того, чтобы обмениваться данными с ОС, мы можем напрямую использовать эту память, экономя наше время. Таким образом, кортежи могут быть легко и быстро созданы

Заключение

Списки — это динамические массивы, а кортежи — это статические массивы. Если мы хотим хранить неизменяемые данные, кортежи являются лучшим вариантом, с другой стороны, если мы хотим хранить разрозненные списки объектов, это будет лучшим выбором. Таким образом, кортежи можно использовать для хранения таких объектов, как части телефонного номера, коэффициент многочлена, первые 20 простых чисел, день рождения человека и место рождения. В то время как списки можно использовать для хранения таких объектов, как названия языков программирования (по мере того, как они продолжают расти), возраст, вес и рост человека (поскольку их необходимо будет обновлять), результаты продолжающейся серии игр в бильярд.

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

Использованная литература:

Высокопроизводительный Python (https://www.oreilly.com/library/view/high-performance-python/9781449361747/)
https://docs.python.org/3/library/bisect.html