Не изобретать велосипед, или Обзор модуля collections (Python)

Разберем модуль collections, существенно дополняющий функциональность встроенных типов данных Python.

Статья исходно подготовлена для издания Библиотека программиста. На Яндекс.Дзене не очень удобная вёрстка для исходного кода, так что часть материалов осталась в оригинальном тексте.

Типы данных Python не ограничиваются стандартными. Модуль collections содержит специализированные классы контейнеров, альтернативных традиционным dict, list и tuple.

Это доступный «из коробки» родной модуль Python – те самые батарейки, что идут в комплекте. Уверенное владение инструментарием collections, itertools и других модулей стандартной библиотеки – одна из черт, отличающих продвинутых питонистов от новичков.

Рассмотрим на примерах самые популярные составляющие модуля collections для Python 3 (проверено на 3.6). Для начала импортируйте библиотеку:

import collections

Счётчик (Counter)

Одна из распространённых задач, для которой начинающие питонисты придумывают собственные решения, – подсчёт элементов последовательности: списка, строки символов и т. д.

Если нужно что-то посчитать, определить количество вхождений или наиболее (наименее) часто встречающихся элементов, используйте объекты класса Counter. Создаются они с помощью конструктора collections.Counter().

Функция принимает итерируемый аргумент и возвращает словарь, в котором ключами служат индивидуальные элементы, а значениями – количества повторений элемента в переданной последовательности. Посчитаем, сколько раз встречается каждая буква в слове «абракадабра»:

>>> list_of_letters = list('абракадабра')
>>> letter_cnt = collections.Counter(list_of_letters)
>>> letter_cnt
Counter({'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1})

Обращение к ключам происходит аналогично обычному словарю:

>>> letter_cnt['а']
5

Если элемент отсутствовал в последовательности, при обращении по ключу счётчик не вызовет исключение, а вернет нулевое значение:

>>> letter_cnt['ю']
0

Присвоение нуля ключу не удаляет это значение, а создаёт соответствующую пару:

>>> letter_cnt['в'] = 0
>>> letter_cnt
Counter({'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1, 'в': 0})

Чтобы удалить пару key-value, используем del:

>>> del letter_cnt['в']
>>> letter_cnt
Counter({'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1})

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

>>> emotion_cnt = collections.Counter({'like':2, 'dislike':3})
>>> emotion_cnt
Counter({'like': 2, 'dislike': 3})

Метод elements() преобразует результаты подсчета в итератор:

>>> list(emotion_cnt.elements())
['like', 'like', 'dislike', 'dislike', 'dislike']

Метод most_common(n) ищет n самых повторяющихся элементов. Найдём для примера три наиболее частых символа:

# без передачи аргумента выводятся все элементы
# в порядке от наиболее частых к наиболее редким

>>> letter_cnt.most_common(3)
[('а', 5), ('б', 2), ('р', 2)]

Метод возвращает список кортежей вида (ключ, число повторений).

Нередко интерес представляют не самые частотные, а уникальные значения, самые редкие элементы. Их можно найти срезом с шагом -1:

>>> letter_cnt.most_common()[:-3:-1]
[('д', 1), ('к', 1)]

Счётчики складываются и вычитаются друг из друга:

>>> letter_cnt + emotion_cnt
[('д', 1), ('к', 1)]
>>> emotion_cnt - collections.Counter(like=1, dislike=3)
Counter({'like': 1})

Операнд & даст минимальные значения для одних и тех же подсчитываемых элементов, операнд | – максимальные:

>>> c = collections.Counter(a=4, b=2, c=0, d=-2)
>>> d = collections.Counter(a=1, b=2, c=3, d=4)
>>> c & d
Counter({'b': 2, 'a': 1})
>>> c | d
Counter({'a': 4, 'd': 4, 'c': 3, 'b': 2})

Как видно из примера, счётчику можно передавать отрицательные значения. Однако для перечисленных операций хранятся только положительные подсчеты. Нулевые или отрицательные значения обычно приходится хранить при вычитании, что реализовано в методе subtract():

>>> c.subtract(d)
>>> c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

Обратите внимание, что метод subtract() обновляет сам счётчик, а не создает новый.

Распространненные шаблоны применения Counter:

>>> sum(letter_cnt.values()) # число всех посчитанных элементов
11
>>> list(letter_cnt) # список уникальных элементов исходной последовательности
['а', 'б', 'р', 'к', 'д']
>>> set(letter_cnt)
{'а', 'б', 'д', 'к', 'р'}
>>> dict(letter_cnt) # счетчик это подкласс словаря, можно преобразовать в обычный dict
{'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1}

Унарные операции оставляют только положительные или отрицательные подcчёты:

>>> +c # способ вывести положительные подсчеты
Counter({'a': 3})
>>> -c # способ вывести отрицательные подсчеты
Counter({'c': 3, 'd': 6})
>>> c.clear() # Очищаем счетчик
>>> c
Counter()

Счетчик в сочетании с регулярными выражениями используется для частотного анализа текста. Давайте узнаем, какие десять слов чаще прочих встречаются в тексте «Евгения Онегина»:

>>> import re
>>> words = re.findall(r'\w+', open('onegin.txt').read().lower())
>>> collections.Counter(words).most_common(10)
[('и', 1011),
('в', 606),
('не', 387),
('он', 294),
('на', 260),
('с', 240),
('я', 238),
('как', 192),
('но', 190),
('что', 167)]

Словарь со значением по умолчанию (defaultdict)

Что будет, если обратиться к словарю по ключу, которого в нем ещё нет?

Верно, исключение KeyError:

>>> d = dict()
>>> d['name'] = 'James'
>>> d['surname'] = 'Bond'
>>> d['patronymic']
KeyError Traceback (most recent call last) <...>

Если нет нужды отлавливать исключение, достаточно использовать альтернативный вариант словаря – collections.defaultdict.

Соответствующему конструктору в качестве аргумента передается тип элемента по умолчанию:

>>> d = collections.defaultdict(str)
>>> d['name'] = 'James'
>>> d['surname'] = 'Bond'
>>> d['patronymic']
''
>>> d
defaultdict(str, {'name': 'James', 'surname': 'Bond', 'patronymic': ''})

Таким образом, для ключей, к которым происходит обращение, конструктор поставит в соответствие дефолтный элемент данного типа. В случае str – пустая строка, для целых чисел – 0 и т. д.

Обычные словари имеют метод setdefault(), который позволяет добиться того же результата, но его использование делает программный код менее наглядным и замедляет исполнение.

Словарь с памятью порядка добавления элементов (OrderedDict)

Ощутимость пользы OrderedDict так повлияла на обычный dict, что в новых версиях Python различий между ними становится всё меньше. В былые времена OrderedDict кардинально отличался от обычного словаря тем, что умел запоминать порядок вставки. Но с версии Python 3.6 на это способен и обычный словарь. Однако некоторые различия между ними все равно остаются:

1. Обычный dict был разработан, чтобы быть лучшим в операциях, связанных с мапированием. Отслеживание порядка вставки для него – дело вторичное. И наоборот, OrderedDict хорош в операциях переупорядочения, а эффективность, скорость итераций и производительность не главное.
2. Алгоритмически OrderedDict может обрабатывать частые операции переупорядочения лучше, чем dict.

Так как OrderedDict это упорядоченная последовательность, объекты содержат соответствующие методы, реорганизующие структуру:

1. popitem(last=True) – удаляет последний элемент если last=True, и первый, если last=False
2. move_to_end(key, last=True) – переносит ключ key в конец, если last=True, и в начало, если last=False

>>> d = collections.OrderedDict.fromkeys('abcde')
>>> d.move_to_end('b')
>>> ''.join(d.keys())
'acdeb'
>>> d.move_to_end('b', last=False)
>>> ''.join(d.keys())
'bacde'

Контейнер словарей (ChainMap)

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

>>> letters = {'a':1, 'b':2}
>>> vowels = {'a':1, 'b':0, 'c':0, 'd': 0, 'e':1}
>>> chain = collections.ChainMap(letters, vowels)
>>> chain
ChainMap({'a': 1, 'b': 2}, {'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1})

При обращении к ChainMap по ключу одного из словарей, происходит поиск значения среди всех словарей, при этом нет необходимости указывать конкретный словарь:

>>> chain['e']
1

При поиске ChainMap выводит первое найденное значение (проходя словари по очереди добавления). В том числе если в словарях несколько одинаковых ключей:

>>> chain['b']
2

Изменение содержания словаря изменяет и ChainMap. Нет необходимости перезаписывать надструктуру:

>>> letters['c'] = 3
>>> chain
ChainMap({'a': 1, 'b': 2, 'c': 3}, {'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1})

Так как ChainMap это комбинация словарей, логично, что у неё есть методы keys() и values():

>>> list(chain.keys())
['c', 'd', 'a', 'e', 'b']
>>> list(chain.values())
[3, 0, 1, 1, 2]

Значения values соответствуют списку keys, как это было описано выше. То есть в случае несколько совпадающих ключей, выводится значение для первого из словарей, где встречается этот ключ.

При необходимости расширить составленный ранее ChainMap можно методом new_child():

>>> consons = {'a':0, 'b':1, 'c':1}
>>> chain.new_child(consons)
ChainMap({'a': 0, 'b': 1, 'c': 1}, {'a': 1, 'b': 2, 'c': 3}, {'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1})

Обратите внимание, что метод не обновляет старую структуру, а создаёт новую.

Двусторонняя очередь (deque)

Объект типа deque (читается как «дэк», двусторонняя или двусвязная очередь) является усовершенствованным вариантом списка с оптимизированной вставкой/удалением элементов с обоих концов. Реализация deque оптимизирована так, что операции слева и справа имеют примерно одинаковую производительность O(1). Добавление новых элементов в конец происходит не сильно медленнее, чем во встроенных списках, но добавление в начало выполняется существенно быстрее.

>>> seq = list("bcd")
>>> deq = collections.deque(seq)
>>> deq
deque(['b', 'c', 'd'])
>>> deq.append('e') # добавление в конец
>>> deq.appendleft('a') # добавление в начало (левый конец)
>>> deq
deque(['a', 'b', 'c', 'd', 'e'])

Чтобы добавлять не одиночный элемент, а группу итерируемого объекта iterable используйте соответственно extend(iterable) и extendleft(iterable).

Аналогично методу append() метод pop() для deque работает с обоих концов:

>>> deq.pop()
>>> deq.popleft()
>>> deq
deque(['b', 'c', 'd'])

Если нужно посчитать число вхождений элемента в последовательность, применяем метод count():

>>> deq.count('b'), deq.count('a')
(1, 0)

Кроме перечисленных, доступны следующие методы:

1. remove(value) – удаление первого вхождения value
2. reverse() – разворачивает очередь)
3. rotate(n=1) – последовательно переносит n элементов из начала в конец (если n отрицательно, то с конца в начало). В этом поведение deque напоминает кольцевой связный список

Очередь deque имеет аргумент maxlen, позволяющий ограничить ее размер. При заполнении ограниченной очереди добавление n новых объектов «слева» вызовет удаление n элементов справа.

Именованный кортеж и функция namedtuple()

namedtuple() – функция-фабрика для создания именованных кортежей. Этот тип данных похож на struct в других языках программирования:

>>> cols = ['fname', 'pname', 'lname', 'age']
>>> User = collections.namedtuple('User', cols)
>>> user1 = User('Петр', 'Иванович', 'Сидоров', 30)
>>> user1
User(fname='Петр', pname='Иванович', lname='Сидоров', age=30)
>>> user1.lname
Сидоров
>>> Point = collections.namedtuple('Point', ['x', 'y'])
>>> p = Point(3, 4)
>>> p.x**2 + p.y**2
25

Именованные кортежи делают код яснее – вместо индексирования составляющие объекта вызываются по явным именам. Остаётся доступной и численная индексация:

>>> p[0]**2 + p[1]**2
25

Структура namedtuple похожа на словарь. Посредством метода _asdict можно представить те же данные в виде OrderedDict:

>>> p._asdict()
OrderedDict([('x', 3), ('y', 4)])

Чтобы вызвать значение через строковый ключ, необязательно преобразовывать namedtuple – подходит стандартная функция getattr():

>>> getattr(p, 'x')
3

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

>>> d = {'x': 0, 'y': 1}
>>> Point(**d)
Point(x=0, y=1)

Имена полей namedtuple перечислены в _fields:

>>> user1._fields, p._fields
(('fname', 'pname', 'lname', 'age'), ('x', 'y'))

С версии 3.7 можно присвоить полям значения по умолчанию.

Если вам пришлась по душе компактность namedtuple в сравнении с обычными классами и ваш проект может работать с версиями Python не меньше 3.7, присмотритесь к модулю dataclasses. Эта встроенная библиотека предоставляет декоратор и функции для автоматического добавления в пользовательские классы сгенерированных специальных методов, таких как __init__() и __repr__().

Резюме

Подведём итог нашему рассказу об основных составляющих модуля collections:

1. Counter – инструмент подсчёта неизменяемых объектов. Используйте, если нужно определить количество вхождений или число наиболее (наименее) часто встречающихся элементов.
2. defaultdict – словарь, умеющий при вызове отсутствующего ключа вместо вызова исключения KeyError записывать значение по умолчанию (работает быстрее, чем метод setdefault()).
3. OrderedDict – словарь с памятью порядка добавления элементов, умеющий переупорядочивать элементы лучше, чем dict.
4. ChainMap – контейнер комбинаций словарей с поиском, обобщением ключей и элементов.
5. namedtuple() – функция-фабрика для создания именованного кортежа. Это один из простейших способов сделать код более ясным: использовать вместо индексов имена.
6. deque – двусторонняя очередь – список, оптимизированный для вставки и удаления элементов с обоих концов с методом подсчёта вхождений
7. UserDict, UserList, UserString – не заслуживающие развёрнутого описания обертки над стандартными объектами словарей, списков и строк для беспроблемного наследования (прямое наследование встроенным типам dict, list, str чревато ошибками, связанными с игнорированием переопределения методов).

А вы уже используете collections в своих проектах?