Не изобретать велосипед, или Обзор модуля 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
Counter({'а': 5, 'dislike': 3, 'б': 2, 'р': 2, 'like': 2, 'к': 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(), который позволяет добиться того же результата, но его использование делает программный код менее наглядным и замедляет исполнение.

Помимо str и int, defaultdict часто используют в связке с пустым списком, чтобы начинать добавление элементов без лишнего кода:

>>> dict_of_lists = collections.defaultdict(list)
>>> for i in range(5):
...     dict_of_lists[i].append(i)
... 
>>> dict_of_lists
defaultdict(<class 'list'>, {0: [0], 1: [1], 2: [2], 3: [3], 4: [4]})

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

Словарь с памятью порядка добавления элементов (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 элементов справа.

Ограниченные очереди обеспечивают функциональность, похожую на tail-фильтр в Unix:

def tail(filename, n=10):
    """Возвращает n последних строк файла'"""
    with open(filename) as f:
        return collections.deque(f, n)

Другой шаблон применения deque – хранение последних добавленных элементов с выбрасыванием более старых. Пример компактной и быстрой реализации функции скользящего среднего:

import itertools

def moving_average(iterable, n=3):
    # moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0
    it = iter(iterable)
    d = collections.deque(itertools.islice(it, n-1))
    d.appendleft(0)
    s = sum(d)
    for elem in it:
        s += elem - d.popleft()
        d.append(elem)
        yield s / n

Алгоритм распределения нагрузки Round-robin можно реализовать с помощью итераторов, хранящихся в deque. Значения выводятся из активного итератора в нулевой позиции. Если этот итератор исчерпан, его можно удалить методом popleft (); в противном случае его можно циклически «провернуть» до конца методом rotate():

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    iterators = collections.deque(map(iter, iterables))
    while iterators:
        try:
            while True:
                yield next(iterators[0])
                iterators.rotate(-1)
        except StopIteration:
            # Удалить "закончившийся" итератор
            iterators.popleft()

Именованный кортеж и функция 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

Именованные кортежи часто используются для назначения имён полей кортежам, возвращаемым модулями csv или sqlite3:

EmployeeRecord = collections.namedtuple('EmployeeRecord', 'name, age, title, department, paygrade')

import csv
for emp in map(EmployeeRecord._make, csv.reader(open("employees.csv", "rb"))):
    print(emp.name, emp.title)

import sqlite3
conn = sqlite3.connect('/companydata')
cursor = conn.cursor()
cursor.execute('SELECT name, age, title, department, paygrade FROM employees')
for emp in map(EmployeeRecord._make, cursor.fetchall()):
    print(emp.name, emp.title)

Структура 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 можно присвоить полям значения по умолчанию.

Поскольку именованный кортеж является обычным классом Python, в него легко привнести новую функциональность или изменить старую. Например, добавим к Point расчёт гипотенузы и формат вывода данных:

class Point(collections.namedtuple('Point', ['x', 'y'])):
    __slots__ = ()  # предотвращает создание словарей экземпляров
    @property
    def hypot(self):
        return (self.x**2 + self.y**2) ** 0.5
    def __str__(self):
        return 'Point: x=%6.3f  y=%6.3f  hypot=%6.3f' % (self.x, self.y, self.hypot)

for p in Point(3, 4), Point(14, 5/7):
    print(p)

Point: x= 3.000  y= 4.000  hypot= 5.000
Point: x=14.000  y= 0.714  hypot=14.018

Если вам пришлась по душе компактность 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 имеется наследованный модуль коллекции абстрактных базовых классов сollections.abc. Но это тема отдельного разговора.

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