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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ощутимость пользы 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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