Язык Python. Дополнительные типы коллекций

СЕРГЕЙ СУПРУНОВ, инженер электросвязи «широкого ИТ-профиля». В свободное время изучает FreeBSD и Python и пытается осмыслить свою нелюбовь к KDE

Язык Python
Дополнительные типы коллекций

Возможность разрабатывать свои собственные типы данных делает его гибким и мощным. Но прежде чем писать что-то своё, загляните в стандартную библиотеку.

Коллекциями в языке Python принято называть типы данных, в том или ином виде хранящие ссылки на ряд других объектов (не обязательно однотипных). Коллекции делятся на последовательности, множества и отображения. Среди встроенных типов данных к первым относятся списки (тип данных list) и кортежи (tuple), ко вторым – обычные (изменяемые) и фиксированные множества (set и frozenset), и, наконец, к третьим – словари (dict).

Для большинства решаемых задач этих типов коллекций более чем достаточно, но иногда всё же возникает потребность в нестандартных типах. И по мере развития языка всё реже приходится прибегать к собственным реализациям, поскольку с каждым новым релизом стандартная библиотека Python предлагает всё больше дополнительных типов данных.

В данной статье мы рассмотрим типы коллекций, которые доступны в модуле collections стандартной библиотеки Python 3.1.

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

Класс collections.namedtuple позволяет создать тип данных, ведущий себя как кортеж, с тем дополнением, что каждому элементу («полю») присваивается имя, по которому можно в дальнейшем получать доступ к нему как к атрибуту:

>>> import collections

>>> User = collections.namedtuple('User', 'name phone login speed')

>>> vasya = User('Петров В. И.', 22343, 'vasya', 128)

>>> for field in vasya:

... print(field) # поведение аналогично кортежу

Петров В. И. 22343 vasya 128

>>> print(vasya[3]) # работает как обычный кортеж

128

>>> print(vasya.login, vasya.speed)

vasya 128

>>> tvasya = tuple(vasya) # если нужен простой кортеж

>>> tvasya

('Петров В. И.', 22343, 'vasya', 128)

Первым параметром функции namedtuple() передаётся имя создаваемого типа данных, которое будет возвращаться функцией type() и фигурировать, например, в сообщениях об ошибках. Второй параметр – разделённый пробелами список «полей» в том порядке, как они будут следовать в кортеже. С помощью дополнительного аргумента rename=True (появился в Python 3.1) можно включить автоматическое переименование тех полей, для которых задано недопустимое с точки зрения Python имя (например, не соответствующее правилам именования идентификаторов или одно из зарезервированных слов) – такие поля автоматически получат имена вида _0, _1 и т.д., число соответствует порядковому номеру поля:

>>> Bool = collections.namedtuple('Bool', 'False True', rename=True)

>>> test = Bool('2 > 3', '7 < 8')

>>> test

Bool(_0='2 > 3', _1='7 < 8')

Данный пример, конечно, искусственный. Реальная потребность в переименовании может понадобиться, если имена полей берутся из «внешних источников», например формируются на основании заголовка CSV-файла. Использование этого типа данных позволяет повысить удобочитаемость кода, поскольку не нужно постоянно вспоминать, какой смысл несёт значение под тем или иным индексом.

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

NAME, PHONE, LOGIN, SPEED = (0, 1, 2, 3) # или range(4)

vasya = ('Петров В. И.', 22343, 'vasya', 128)

print(vasya[LOGIN])

Теперь всё доступно в стандартной библиотеке, и вам нет необходимости прикладывать лишние усилия.

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

Рассмотрим небольшой пример:

>>> counter = {}

>>> sample = [1,2,1,4,2,3,4]

>>> for dig in sample:

... counter[dig] += 1

...

 

Traceback (most recent call last):   File "<stdin>", line 2, in <module> KeyError: 1

 

Знакомая ситуация? Да, мы хотели в словаре counter посчитать число вхождений каждого элемента в списке sample. Но на первой же итерации возникла ошибка, так как словарь пуст и элемента с ключом 1 ещё нет – прибавлять единицу не к чему. В обычных словарях эта проблема решается либо предварительной проверкой на вхождение, либо с помощью методов словаря get() или setdefault(), либо обработкой соответствующего исключения:

# Первый способ

if dig in counter:

   counter[dig] += 1

else:

   counter[dig] = 1

# Второй способ

counter[dig] = counter.get(dig, 0) + 1

# Третий способ

counter[dig] = counter.setdefault(dig, 0) + 1

# Четвёртый способ

try:

   counter[dig] += 1

except KeyError:

   counter[dig] = 1

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

counter = collections.defaultdict(int)

for dig in sample:

counter[dig] += 1

Эта конструкция уже не вызовет никаких ошибок – если элемент с нужным ключом в словаре отсутствует, он будет создан автоматически, а значением по умолчанию будет результат выполнения «фабричной функции», переданной в качестве параметра при инициализации словаря. В качестве «фабричной» можно использовать любую функцию, возвращающую какое-либо значение. В нашем примере мы используем встроенную функцию int(), которая, будучи вызвана без аргумента, возвращает 0. Именно это значение и будет присвоено вновь создаваемому элементу.

Аналогично вы можете использовать собственную функцию (она должна уметь выполняться без аргументов) или lambda-функцию: collections.defaultdict(lambda: 'default') создаст словарь, в котором автоматически создаваемые элементы будут получать в качестве значения строку default. Учтите, что конструктору defaultdict() должна передаваться именно ссылка на функцию (то есть её имя), а не возвращаемое значение. Поэтому имя нужно указывать без скобок.

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

«Двусторонние очереди»

Тип deque позволяет очень просто имитировать такие последовательности, как очереди и стеки.

Например:

>>> fifo = collections.deque()

>>> stack = collections.deque()

>>> fifo.appendleft(1)

>>> fifo.appendleft(2)

>>> fifo.appendleft(3)

>>> fifo.pop()

1

>>> fifo.pop()

2

>>> stack.append(1)

>>> stack.append(2)

>>> stack.append(3)

>>> stack.pop()

3

>>> stack.pop()

2

В объект fifo мы добавляем элементы слева, а извлекаем справа, реализуя тем самым очередь типа FIFO (First In – First Out, «первый пришёл – первый вышел»). Объект stack ведёт себя по принципу LIFO (Last In – First Out, «последний пришёл – первый вышел»). Хотя в принципе ничто не мешает добавлять и извлекать элементы с любой из сторон. Соблюдение соглашений здесь целиком и полностью ложится на программиста.

Объекты класса deque, как и другие коллекции, являются итерируемыми – при желании вы всегда можете выполнить их обход в цикле. Можно обращаться к элементам и по индексу.

По большому счёту, продемонстрированное выше поведение неплохо обеспечивается и обычным списком: методы append() и pop() ведут себя точно так же, а работу с началом списка можно реализовать методами pop(0) и insert(0), то есть передавая в качестве аргумента индекс извлекаемого элемента (кстати, метод pop() объектов deque «умеет» извлекать только последний элемент, а метода insert() нет вообще).

Хотя методы appendleft() и popleft() класса deque, на мой взгляд, более очевидны. Также скорость их выполнения не зависит от количества элементов в очереди (в терминах оценки времени исполнения алгоритмов O(), вставка и извлечение элементов как сначала очереди, так и с конца, имеет производительность O(1)) – например, при большом числе элементов метод appendleft() выполняется в разы быстрее, чем метод insert() для списков.

Но зато тип deque предоставляет метод rotate(N), переносящий N последних элементов в начало очереди (для отрицательного значения N – с начала в конец; по умолчанию N=1). Так, последовательно применяя этот метод к очереди deque([1, 2, 3, 4, 5]) , мы будем получать deque([5, 1, 2, 3, 4]) , deque([4, 5, 1, 2, 3]) и так далее. Как пример использования, можно привести реализацию «русской рулетки»:

!/usr/local/bin/python3.1

import collections, random

baraban = collections.deque((1,0,0,0,0,0))

baraban.rotate(random.randint(5,99))

for shot in range(len(baraban)):

   input('Чья очередь - нажмите Enter... ')

   if baraban[shot]:

      print('БА-БАХ!!!')

      break

   else:

      print('клац')

print('Финита ля комедия, господа!')

Упорядоченные словари

Класс OrderedDict появился в Python 3.1 и позволяет создавать словари с фиксированным порядком элементов. В стандартных словарях, как известно, порядок элементов не определён – они хранятся на основании хэш-функции, и любое изменение словаря может изменить и порядок, в котором элементы будут доступны при переборе (например, в цикле for ... in).

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

>>> od = c.OrderedDict()

>>> od['w'] = 123

>>> od['a'] = 34

>>> od.keys()

KeysView(OrderedDict([('w', 123), ('a', 34)]))

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

Счётчики

Ещё один тип данных, появившийся в модуле collections в Python 3.1, – Counter. Чуть выше, когда мы обсуждали словари со значением по умолчанию, мы в качестве примера решали задачу подсчёта количества одинаковых элементов в некотором списке. Благодаря классу Counter (и разработчикам языка Python) это теперь можно сделать одной строчкой:

>>> sample = [1,2,1,4,2,3,4]

>>> cnt = collections.Counter(sample)

>>> cnt

Counter({1: 2, 2: 2, 4: 2, 3: 1})

>>> cnt[4]

2

Столь же просто можно выполнить подсчёт любых элементов в любой последовательности, например посчитать частоту появления различных символов в файле (строка текста не вполне вписывается в понятие коллекции, поскольку является одним объектом, а не набором ссылок на другие, но везде, где подразумевается итерируемый объект, строка рассматривается как последовательность отдельных символов):

>>> text = open('/home/amsand/reconf.py').read()

>>> cnt = c.Counter(text)

>>> cnt.most_common(3)

[(' ', 1162), ('e', 397), ('s', 284)]

Метод most_common() возвращает указанное число наиболее часто встречающихся элементов, упакованных в кортежи (ключ, значение). Здесь «золото» взял пробел.

***

Как видите, в модуль collections добавлено уже довольно много типов «нестандартных» коллекций (а ведь ещё в версии 2.5 там были представлены только defaultdict и deque), которые могут в ряде случаев заметно упростить вашу программу и сделать её более понятной. Помимо рассмотренных «готовых к употреблению» типов данных, модуль collections предоставляет и ряд абстрактных классов и «классов-заготовок», на базе которых вы можете создавать свои собственные типы коллекций.

Подробную документацию к модулю collections вы найдёте по следующей ссылке: http://docs.python.org/3.1/library/collections.html. Также обратите внимание на модули array, queue и heapq – в ряде случаев они могут предоставить более соответствующие вашим задачам специализированные типы данных.

Приложение

Встроенные типы коллекций

Кратко напомню основные особенности встроенных коллекций:

Список (list) – тип данных, хранящий упорядоченный список ссылок на другие объекты (элементы списка). Обычно создается с использованием квадратных скобок: [1, 'два', 3]. (Замечание: помимо приведённого здесь и далее синтаксиса, объект любого типа данных в Python может быть создан вызовом соответствующей (одноимённой имени типа) функцией. Например, int(5) создаст целое число со значением 5, list() создаст пустой список, и т.д.)

Кортеж (tuple) – неизменяемый набор элементов. Создается с использованием круглых скобок: (1, 'два', 3). В отличие от списка, кортеж представляет из себя единый объект, состоящий из нескольких элементов, и соответственно элементы нельзя изменять, удалять, добавлять иначе, как путём создания нового объекта. Благодаря неизменяемости операции с кортежем выполняются несколько быстрее, чем со списком, и его можно использовать там, где требуется «хэшируемый» объект, например, ключ словаря (см. далее).

Множество (set) – неупорядоченный список уникальных элементов. Создается с использованием фигурных скобок: {1, 'два', 3}; пустое множество можно создать только вызовом функции set(). Все дублирующиеся элементы удаляются. Элементами могут быть только хэшируемые (неизменяемые) объекты – числа, строки, кортежи, фиксированные множества (frozenset). Благодаря использованию хэш-функции множества поддерживают очень быструю проверку на вхождение элемента оператором in (в списках и кортежах оператор in работает методом прямого перебора). Множества (как «обычные», так и фиксированные, о которых речь идёт в следующем абзаце) по своему поведению аналогичны математическим множествам и поддерживают методы, реализующие основные операции над ними – объединение, пересечение, разность, проверка на включение и т.д.

Фиксированное множество (frozenset) – неизменяемое множество (создаётся только вызовом функции frozenset()). Благодаря неизменяемости операции с ними выполняются ещё быстрее, и их можно использовать там, где требуется хэшируемый тип данных (как элементы множеств или ключи словарей).

Словарь (dict) – тип данных, хранящий пары «ключ – значение». Создается с использованием фигурных скобок: {'one':1, 'two': 2, 'three': 3}. Ключами могут быть только хэшируемые объекты, значениями – объекты любых типов. Порядок следования элементов не определён.

Копирование коллекций

Затронем и один «тонкий» вопрос реализации языка Python – копирование объектов. С «бытовой» точки зрения присваивание «b = a» должно бы породить объект b, являющийся копией a. Но на практике мы видим совсем другое:

>>> a = [1,2,3]

>>> b = a

>>> b[2] = 5

>>> a

[1, 2, 5]

>>> b

[1, 2, 5]

>>> a is b

True

Почему так происходит? Дело в том, что имя переменной содержит ссылку на объект (можно сказать, его адрес). Записывая «b = a», мы копируем в переменную b этот адрес, но все обращения по нему ведут к тому же объекту (обратите внимание, что выражение «a is b» возвращает True).

С неизменяемыми объектами – числами, строками, кортежами - этого не происходит, поскольку при любом «изменении» такого объекта фактически создаётся новый, и переменная b начинает указывать на него, в то время как a продолжает ссылаться на первоначальный объект.

Так как же создать копию изменяемой коллекции? Есть три основных способа: использование «полного» среза (b = a[:]), явное создание нового объекта на базе существующего (b = list(a)) и использование функции copy модуля copy (b = copy.copy(a)).

Всё это относится к так называемому «поверхностному» копированию – например, если копируемый список содержит вторым элементом словарь (точнее, ссылку на словарь), то список-копия будет ссылаться на тот же самый словарь. В итоге изменения в списках a и b не будут влиять друг на друга, а вот изменения в словаре a[1] будут видны и по ссылке b[1]. Чтобы создать абсолютно независимые копии, применяется «глубокое копирование», выполняемое функцией copy.deepcopy().