Коллекции

Коллекции составляют основу хранения и обработки данных в Python. В настоящей главе рассматриваются конкретные типы, встроенные в язык, и их устройство, тогда как сами структуры данных, дек и хеш-таблица в их общем виде, разбираются в части «Алгоритмы и структуры данных»; стоимость конкретных операций над списком, множеством и словарём оценивается в следующей главе. Выбор между ними определяет, будет программа выполняться секунды или часы.

Слайды к главе. Материал главы изложен также в пятой части лекции «Python. Начало» с демонстрациями в интерактивной оболочке; слайды лекции доступны на сайте книги и в PDF.

Понятие коллекции

Коллекцией в Python стандартная библиотека называет объект с тремя свойствами. Он является контейнером (Container), то есть отвечает на оператор in; он итерируемый (Iterable), и его элементы можно перебрать в цикле; он ограниченной длины (Sized), а значит знает, сколько в нём элементов, и отвечает на len().

Принадлежность к коллекциям проверяется через isinstance с абстрактным классом из стандартной библиотеки.

from collections.abc import Collection

# Проверим, является ли список коллекцией
print(isinstance([1, 2, 3], Collection))  # True

Любопытные исключения

  • Числовой интервал служит контейнером: про любое число можно сказать, лежит оно внутри или нет. Однако перебрать все его точки нельзя, и длины, измеряемой в элементах, у него нет.
  • Генератор итерируем, но заранее не знает, сколько элементов выдаст, и не способен отвечать на in, не израсходовав себя.

Синтаксис @dataclass и магические методы, за которыми стоят операторы наподобие in, разбираются в главе «Классы»; здесь описывается собственный тип, отвечающий на in.

# Пример: Интервал как контейнер
from dataclasses import dataclass

@dataclass
class Interval:
    a: float
    b: float

    def __contains__(self, x):
        return self.a < x < self.b

interval = Interval(0, 1)
print(0.5 in interval)  # True — оператор in работает

# а вот длины у интервала нет и быть не может:
# len(interval) -> TypeError: object of type 'Interval' has no len()

Иерархия коллекций

Стандартная библиотека Python определяет абстрактные базовые классы (ABC), по которым коллекции и классифицируются:

   Container      Iterable       Sized          три независимых свойства
       |             |             |
       +-------------+-------------+
                     |
                 Collection        объект, обладающий всеми тремя
                     |
        +------------+------------+
        |            |            |
    Sequence        Set        Mapping

Container, Iterable и Sized представляют собой три независимых свойства, и объект может обладать любым их сочетанием. Генератор итерируем, но не знает своей длины; рассмотренный выше Interval, не позволяющий перебирать точки, остаётся контейнером. Collection объединяет все три свойства, потому и наследуется от всех трёх.

Ниже располагаются три семейства:

  • Sequence (последовательности), где элементы упорядочены и доступны по индексу. Сюда относятся списки, кортежи и строки.
  • Set (множества), где элементы уникальны, а порядка, связывающего их, нет. Это set и frozenset.
  • Mapping (отображения), хранящие пары «ключ, значение». Это словари.

Списки (list): универсальные и изменяемые

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

Неочевидные особенности инициализации

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

# Кажется, что это создаст матрицу 2x1
chunks = [[0]] * 2
chunks[0][0] = 42
print(chunks)  # [[42], [42]] Оба элемента ссылаются на один и тот же список!

# Правильный способ: включение создаёт новый список на каждой итерации
correct_chunks = [[0] for _ in range(2)]
correct_chunks[0][0] = 42
print(correct_chunks)  # [[42], [0]] — а вот теперь как надо

Тело включения выполняется на каждой итерации заново, и [0] создаёт новый список каждый раз.

Эффективные операции

Внутренне список устроен как динамический массив, и стоимость операций следует из этого устройства. append(item) и pop(), работающие с последним элементом, имеют амортизированную сложность O(1). insert(0, item) и pop(0) сдвигают все элементы и имеют сложность O(n). extend(iterable) выгоднее серии append(), поскольку один раз оценивает требуемый размер вместо наращивания списка по одному элементу.

Совет: При необходимости частых операций с обоих концов целесообразно использовать collections.deque (устройство дека и сравнительные измерения со списком приведены в главе «Основные структуры данных»).

Кортежи (tuple): неизменяемые и хешируемые

Неизменяемость даёт кортежу свойство, отсутствующее у списка: кортеж хешируем, а значит, подходит для ключей словаря и элементов множества. Пара координат, связка «прибор, канал», дата, записанная тремя числами, помещаются в кортеж и становятся ключом.

Распаковка кортежей

Распаковка разбирает кортеж на переменные одним присваиванием. Звёздочка слева от знака равенства собирает остаток в список, подчёркивание по соглашению помечает ненужное значение, а звёздочка в вызове функции работает в обратную сторону и раскладывает кортеж по аргументам.

# Распаковка с упаковкой «лишних» элементов в переменную
first, second, *rest = range(10)
print(first, second, rest)  # 0 1 [2, 3, 4, 5, 6, 7, 8, 9]

# Игнорирование ненужных значений
x, _, z = (1, 2, 3)

# Распаковка в аргументы функции
def greet(name, greeting):
    return f"{greeting}, {name}!"

person = ("Alice", "Hello")
print(greet(*person))  # "Hello, Alice!"

Именованные кортежи (namedtuple)

Через месяц смысл, вложенный в point[1], оказывается забытым. collections.namedtuple является фабрикой классов, создающей подтип кортежа с именованными полями. Полученный объект остаётся кортежем со всеми его свойствами, но к элементам можно обращаться по имени.

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(10, y=20)
print(p.x, p.y)  # 10 20
print(p._asdict()) # {'x': 10, 'y': 20}

Метод _asdict() преобразует такой кортеж в словарь, что удобно для вывода и сериализации. Имена полей задаются пользователем, поэтому служебные методы помечаются подчёркиванием, чтобы они не столкнулись с полем, названным asdict.

Множества (set): уникальность и скорость

Множества реализованы как хеш-таблицы, рассматриваемые в главе «Хеш-функции», поэтому проверка вхождения (in) имеет среднюю сложность O(1), и время не зависит от размера множества.

Неочевидные применения множеств

Множество применяется не только ради уникальности, но и ради быстрой проверки принадлежности.

  1. Удаление дубликатов из списка.

    unique_list = list(set(duplicated_list))

  2. Подсчёт элементов, встречающихся сразу в двух коллекциях.

    common = set(list1) & set(list2)

  3. Фильтрация «мусора» при разборе данных.

    valid_tags = {'python', 'tutorial', 'advanced'}
tags = ['python', 'beginner', 'advanced']
filtered_tags = [tag for tag in tags if tag in valid_tags]
# ['python', 'advanced']

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

frozenset: неизменяемое множество

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

# Множество множеств? Нет.
# {set([1,2]), set([3,4])}  # TypeError: unhashable type: 'set'

# А так — можно.
fs1 = frozenset([1, 2])
fs2 = frozenset([3, 4])
meta_set = {fs1, fs2}  # Valid

Словари (dict): сердце Python

Словарь является наиболее нагруженной структурой в языке. На нём построены пространства имён модулей, атрибуты объектов и передача именованных аргументов. Начиная с Python 3.7 словарь гарантированно сохраняет порядок добавления элементов; ранее это было деталью реализации CPython 3.6, не оговорённой в языке.

Малоизвестные возможности словарей

  1. Метод setdefault() возвращает значение по ключу, а при отсутствующем ключе сначала помещает в словарь указанное значение, за один поиск по хеш-таблице вместо двух.

    data = {}
# Классический, но неэффективный способ
if 'key' not in data:
    data['key'] = []
data['key'].append(1)

# Эффективный способ с setdefault
data.setdefault('key', []).append(1)

  2. Метод popitem() удаляет и возвращает пару (ключ, значение) в порядке LIFO (последним пришёл, первым ушёл). Полезен для обработки данных в обратном порядке.

  3. Словарные включения (Dict Comprehensions).

    squares = {x: x*x for x in range(5)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

Коллекции из модуля collections

Для частых сценариев в стандартной библиотеке предусмотрены готовые надстройки над четырьмя базовыми типами. Counter, defaultdict и OrderedDict являются подклассами словаря, а deque поддерживает интерфейс последовательности, поэтому большая часть кода работает с ними без изменений. Исключения всё же есть: у дека нет срезов, а defaultdict создаёт ключ уже при чтении d[k].

  • defaultdict, словарь с фабричной функцией, отвечающей за недостающие ключи.

    from collections import defaultdict
graph = defaultdict(list)
graph['a'].append('b')  # Не нужно проверять, есть ли ключ 'a'

  • Counter, подкласс словаря, подсчитывающий хешируемые объекты.

    from collections import Counter
words = ['apple', 'banana', 'apple', 'orange']
word_count = Counter(words)
print(word_count.most_common(1))  # [('apple', 2)]

  • deque, двусторонняя очередь, пополняемая с обоих концов. Подходит для очередей (FIFO) и стеков (LIFO).

    from collections import deque
queue = deque([1, 2, 3])
queue.append(4)    # O(1)
queue.popleft()    # O(1) — в отличие от списка!

  • OrderedDict, словарь, сохраняющий порядок. В Python 3.7+ обычный dict также упорядочен, но у OrderedDict есть дополнительные методы (move_to_end, popitem(last=True/False)).

Заключение

Выбор коллекции определяет эффективность и корректность программы. Это решение принимается в начале, когда переписывание ещё обходится дёшево.

  • Список применяется, когда важен порядок и данные изменяются.
  • Кортеж подходит, когда данные фиксированы или требуется хешируемый объект.
  • Множество выбирается ради уникальности и быстрой проверки вхождения.
  • Словарь уместен, когда у данных есть естественный ключ.
  • Специализированные коллекции из модуля collections необходимы тогда, когда стандартная четвёрка обрастает обвязкой из проверок и заглушек.

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

Задание. Собрать словарь цепочек и сгенерировать по нему текст: «Генерация текста на основе данных».