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

Помимо 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 в своих проектах?