Python: Встроенные типы данных (list, set, dict, etc)

Знающий людей благоразумен. Знающий себя просвещен.

Дао дэ Цзин

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

И для Python число библиотек, доступных каждому разработчику, уже перевалило за 215 тысяч, а число разрботчиков этих библиотек приближается к 400 тысячам.

Однако, перед тем как рассматривать библиотеки на все случаи жизни (можете найти их на pypi.org), стоит обратить внимание на встроенные типы данных в Python. Даже они экономят сотни часов на реализацию часто используемых структур данных и алгоритмов работы с ними.

Документация объектов, получение информации о содержимом объекта

Одна из замечательных особенностей языка Python – возможность получить документацию практически по каждому объекту. К слову, эту возможность мы получили также за счёт того, что "всё есть объект", а у объекта есть документация.

К примеру, получим документацию функцией help по встроенному типу данных int, ведь тип – это тоже объект:

>>> help(int)

Help on class int in module builtins:

class int(object)
 |  int([x]) -> integer
 |  int(x, base=10) -> integer
 |  
 |  Convert a number or string to an integer, or return 0 if no arguments
 |  are given.  If x is a number, return x.__int__().  For floating point
 |  numbers, this truncates towards zero.
 ...
 |  Methods defined here:
 |  
 |  __abs__(self, /)
 |      abs(self)
 ...

Если же вам нужна не целая документация по всему, что есть в объекте, а лишь список содержимого – используйте функцию dir. Например, чтобы вспомнить название какого-то метода типа:

>>> dir(int)
['__abs__', '__add__', '__and__', '__bool__', '__ceil__',
...
'from_bytes', 'imag', 'numerator', 'real', 'to_bytes']

list – список объектов

В предыдущей главе мы уже встретились со списком. Создать список мы можем одним из следующих способов:

list_of_anything = [1, 'hello', help, None, [True]]

-- мы создали объект списка, содержащего объекты типа int, str, function, NoneType и list (в котором bool). Также можно воспользоваться конструктором list, если мы хотим создать объект списка из итерируемого объекта (условно, похожего на список), например:

another_list = list(list_of_anything)

Элементы в списке упорядочены, к ним можно обращаться по индексам, начиная с нулевого:

list_of_anything[2](list_of_anything[4][0])

-- взяли элемент списка по сдвигу 2 (help), вызвали его с параметром 0-го элемента 4-го элемента нашего списка (True). В итоге – получили документацию по True.

Часто list используется для итеративной обработки элементов в цикле. Поэтому настоятельно рекомендую: храните в списке однотипные объекты. К примеру, мы можем попытаться получить квадраты значений списка:

>>> for element in list_of_anything:
...     print(element ** element)
...
1
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
TypeError: unsupported operand type(s) for ** or pow(): 'str' and 'str'

Подумайте, какие операции можно провести на нашем списке.

Чуть выше мы создали из списка list_of_anything другой список – another_list. Убедимся, что это действительно другой список:

>>> another_list[0] = 0  # 1
>>> another_list[1] = 'bye'  # 'hello'
>>> another_list[2] = dir  # help
>>> another_list[3] = 42  # None
>>> another_list[4][0] = False  # True
>>> print(list_of_anything)
[1, 'hello', Type help() for interactive help, None, [False]]

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

>>> another_list[4] is list_of_anything[4]
True
>>> another_list[4][0] is list_of_anything[4][0]
True
>>> import sys
>>> sys.getrefcount(another_list[4])
3

Как можно увидеть, ни для списка, ни для его содержимого не были созданы новые объекты, лишь увелиился счётчик ссылок. Можно посчитать это недостатком конструктора list. Однако, это типичное поведение при работе со ссылочными типами данных. Так функция copy из модуля copy также не копирует "вложенные" объекты – такое копирование называется "поверхностным" (или "shallow"). Если каждый раз бездумно копировать данные, то памяти на долго не хватит.

Если же вам нужно "глубокое" копирование – воспользуйтесь функцией deepcopy всё того же модуля copy:

>>> from copy import deepcopy
>>> another_list = deepcopy(list_of_anything)
>>> another_list[4] is list_of_anything[4]
False

Ах, опять встроенные функции не по snake_case.

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

>>> original = [0, 1, 2, 3, 4, 5]
>>> slice = original[1:4]
>>> print(slice)
[1, 2, 3]

Можно как в функции range указать ещё и третий параметр – шаг копирования:

>>> slice = original[3:0:-1]
>>> print(slice)
[3, 2, 1]

И это далеко не всё, на что способен list! Давайте оглядимся:

>>> dir(list)
['append', 'clear', 'copy', 'count', 'extend', 'index',
'insert', 'pop', 'remove', 'reverse', 'sort']

Опустив "магические методы" (те, что обрамлены __ – двойным символом подчёркивания), остаётся ещё 11 методов. Советую ознакомиться с ними, используя help(list.имя_метода). Если же коротко:

Реализуем пару известных структур данных на базе list. Для начала сделаем очередь (берём из начала, добавляем в конец):

>>> queue = []
>>> queue.append(0)
>>> queue.append(1)
>>> queue.append(2)
>>> queue.pop(0)
0
>>> queue.pop(0)
1
>>> queue.pop(0)
2

Теперь – стек (добавляем наверх, берём сверху) а ля стопка книг:

>>> stack = []
>>> stack.insert(0, 0)
>>> stack.insert(0, 1)
>>> stack.insert(0, 2)
>>> stack.pop(0)
2
>>> stack.pop(0)
1
>>> stack.pop(0)
0

И "в подарок" – дзенская сортировка:

some_list.copy().sort()

-- глядим на список. Если список упорядочен, значит не о чём беспокоиться. Если нет – а может он не должен быть упорядочен? Также не о чём беспокоиться.

Синтаксический сахар для списков

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

Для начала – сложение списков. Работает оно подобно методу extend, но не изменяет список, а возвращает результат:

>>> first_list = ['a']
>>> second_list = ['b']
>>> first_list += second_list
>>> print(first_list)
['a', 'b']
>>> first_list.extend(second_list)
>>> print(first_list)
['a', 'b', 'b']

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

Ещё один частый случай использования "сахара" – поиск элемента в списке. Для этого применим ключевое слово in:

>>> 2 in [1, 1, 2, 3, 5, 8]
True
>>> 4 in [1, 1, 2, 3, 5, 8]
False

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

>>> 2 * [1, 1, 2, 3, 5, 8]
[1, 1, 2, 3, 5, 8, 1, 1, 2, 3, 5, 8]

Если последний оператор я вижу не так часто, то первые 2 – довольно частые гости в коде на Python.

Мутабельность / иммутабельность и "брат" list-а – tuple

Есть данные, которые должны изменяться во время исполнения программы. А есть те, что изменять не стоит. К примеру, конфигурация программы, константы, прочие стабильные значения. Для первых придумали мутабельность (изменемость), а для вторых – иммутабельность (неизменяемость). Вообще, можно жить и с полной иммутабельностью, что доказывают языки функционального программирования. Однако, скорость их исполнения может падать в различных алгоритмах, созданных в эпоху Машины Тьюринга – абсолютно мутабельной сущности.

Однако, оставим споры за и против на другие курсы. Сейчас мы в рамках Python. И он нам предлагает иммутабельную замену почти на каждую встроенную сущность.

Для нашего list есть tuple, который эквивиалентен во всём, кроме операции присвоения по индексу.

Так, например:

>>> some_tuple = (0, 1, 2, 3)
>>> some_tuple[2] = 2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Создать из элементов кортеж можно через круглые скобки, подобно списку (на забудьте запятую, в случае кортежа из одного элемента). Аналогично с помощью конструктора tuple можно порождать иммутабельные объекты из итерабельных, например, list.

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

*Подумайте, какие из следующих значений стоит хранить списком, а какие кортежем:

• Набор возможных состояний персонажа в игре.
• Заблокированные IP-адреса при работе сетевого фильтра.
• Множество пройденных вершин при обходе графа.
• E-mail-ы для рекламной рассылки.*

set, frozenset и хешируемость

В Python есть специальный тип для работы с множествами – наборами значений без повторения элементов. И он довольно быстр! Ну о скорости мы поговорим дальше, а сейчас реальный пример, чтобы не только математики заинтересовались данным типом данных. На блогах, магазинах, приложениях для горизонтальной навигации часто используются теги (метки).

Представим, что у нас есть текущее состояние заметки – с тегами "Python", "курс", "книга", а нам нужно его поменять на "курс", "мат-мех", "Python3". Для того, чтобы поменять в некоторой абстрактной базе данных состояние, нам полезно сформировать 2 списка: того, что нужно удалить, и того, что нужно создать. В нашем случае удалить (как минимум, связь) нужно будет ["Python", "книга"], а создать ["мат-мех", "Python3"].

Напишите код, позволяющий найти эти 2 списка из произвольных исходных, используя list.

С помощью множеств – это очевидная и простая задача:

>>> old_tags = {"Python", "курс", "книга"}
>>> new_tags = {"курс", "мат-мех", "Python3"}
>>> delete_tags = old_tags - new_tags
>>> create_tags = new_tags - old_tags
>>> print("Delete: ", delete_tags, "; ", "Create: ", create_tags)
Delete:  {'книга', 'Python'} ;  Create:  {'Python3', 'мат-мех'}

Для поиска меток к удалению – из списка старых меток убираем все, которые имеются в новых. Асимметрично делаем для меток к созданию.

Как вы заметили, создать множество из элементов можно с помощью фигурных скобок. Но непустое! Попытайтесь создать пустое множество.

Если же вам нужно пустое множество, либо множество из какого-то списка или итерабельного объекта – воспользуйтесь конструктором set().

Подобно list, используйте функции dir и help для ознакомления с методами типа set. Часть из них я также кратко опишу:

Ну и несколько действительно важных:

• x.add(a) – Добавляет элемент в множество.
• x.remove(a) – Удаляет элемент из множества. KeyError если элемента не существует.
• x.discard(a) – Удаляет элемент, если он есть в множестве.
• x.pop() – Удаляет первый элемент из множества. До версии Python 3.6 множества были неупорядочены -- удалялся "случайный".

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

frozenset

Ни чем не отличается от set, кроме того, что иммутабелен и хешируем.

Хешируемость

Так, для начала определим, что такое "хеш", и почему он так важен.

Если коротко, то хеш или функция свёртки — функция, осуществляющая преобразование набора входных данных произвольной длины в битовую строку установленной длины, выполняемое указанным алгоритмом.

В чём польза? Представим такой алгоритм, которой способен из каких-то байтов производить числа. Самый примитивный -- взятие длины байтовой последовательности.

Возьмём 3 слова "hello", "python", "from 900913". Теперь выделим массив длинной в 8 элементов. Станем класть значения в ячейки выделенного массива, получая остаток от деления длины на размер массива. И также извлекать. То есть для "hello" получим 5 и положим в 4-ый индекс, для "python" - 6, положим в 5-ый индекс, для "from 900913" - 3, положим во 2-ой индекс.

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

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

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

Довольно очевидный факт, который тем не менее требует упоминания: вычисление хешей от мутабельных типов не имеет особого смысла, ведь объект может измениться. Другое дело -- иммутабельные типы -- по ним хеш меняться не будет, их можно использовать в качестве хешируемых значений.

Тип словаря -- dict

Один из самых часто используемых встроенных типов -- dict, также известный как "словарь", "ассоциативный массив" или "хеш" (называемый так за способ адресации).

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

>>> heroes = {
...     'Капитан америка': 'Стивен Роджерс',
...     'Железный человек': 'Энтони Эдвард «Тони» Старк',
...     'Чёрная вдова': 'Наташа Романофф',
... }
>>> print(heroes['Чёрная вдова'])
Наташа Романофф

Или с помощью конструктора dict:

heroes_short = dict(
    Кэп='Стивен Роджерс',
    Сокол='Сэм Уилсон',
)

Для объединения двух словарей можно воспользоваться методом update:

heroes.update(heroes_short)

Или же самим написать поэлементное добавление элементов одного словаря в другой (само собой, встроенный update будет эффективнее):

for key in heroes_short:
    heroes[key] = heroes_short[key]

Кстати, что будет, если ключи словарей совпадут? А если обратимся к несуществующему элементу?

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

for short_name, long_name in heroes_short.items():
    heroes[short_name] = long_name

На самом деле, метод items возвращает итерируемый объект, из которого мы получаем в виде tuple пары ключ, значение. Это ещё один замечательный пример использования tuple. И напротив -- мы можем из списка кортежей получить словарь:

>>> dict([(1, 2), (3, 4)])
{1: 2, 3: 4}

Вот ещё несколько методов, которые могут пригодиться:

• dict.get(key, default) -- получить значение по ключу key. Если же его нет -- вернуть default, где параметр default -- опциональный и равный None по умолчанию. В упражнение ниже вам, возможно, поможет dict.get(key, 0)
• dict.keys() вернёт список ключей списка.
• dict.values() -- список значений.
• dict.pop(key, default) вытолкнет значение по ключу key. Если же его нет и default не определён -- KeyError. А если default определён при отсутствующем ключе, вернётся значение default.

Чтобы узнать прочие методы dict, обратитесь к dir и help.

Упражнение

Чтобы ощутить, что dict -- это не просто сопоставление одних слов другим, предлагаю дописать следующую программу:

import re
file_handler = open('story.txt')
file_content = file_handler.read()
words = re.split('\W+', file_content)
file_handler.close()

-- теперь в words у вас есть список всех слов файла "story.txt", который было нужно подготовить заранее в текущей директории. Осталось дописать эту программу, чтобы получить таблицу частотности слов исходного текста. У меня по незаконченному тексту этой главы получилось нечто следующее:

...
Тип: 1
словаря: 2
dict: 6
типов: 2
известный: 1
словарь: 2
ассоциативный: 1
массив: 2
хеш: 4
...

А после этого, придумав, как сделать удобный список, и вспомнив описание метода list.sort, и вовсе получить топ-5 слов:

[(41, 'в'), (34, 'Python'), (28, '1'), (27, 'из'), (27, '2')]

Пример полиномиального хеша с основанием 37

Добавить пример полиномиального хеша с основанием 37

Модуль collections

В стандартной поставке Python идёт модуль collections. Он содержит ещё несколько типов данных (классов), реализующих алгоритмы работы с реализованной внутри структурой данных.

Кортежи с именованными полями

namedtuple позволяет создавать типы данных, подобные tuple, однако, с фиксированным набором полей. Более того, у каждого поля есть имя, по которому к нему можно обратиться. Если вы имели удовольствие программировать на Си, возможно, увидите сходство со struct.

>>> from collections import namedtuple
>>>
>>> Point = namedtuple("Point", ["x", "y", "z"])
>>> p = Point(x=1, y=2, z=3)
>>> print("Point: (", p.x, ';', p.y, ';', p.z, ')')
Point: ( 1 ; 2 ; 3 )
>>> p.some = 'more'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Point' object has no attribute 'something'

Создавать новые поля (не перечисленные при создании типа) нельзя.

Двунаправленная очередь

Сперва может показаться, что deque ("double-ended queue") – тот же list, только "в профиль". Однако, deque имеет иное внутреннее устройство, в частности, заботится о потокобезопасности. А некоторые операции имеют куда более приятную оценку вычислительной сложности (времени исполнения).

Так например, если вам нужно убирать или вставлять элементы в начало списка – лучше воспользоваться deque, ведь он вне зависимости от размера списка будет делать это за одно и то же время. При этом в list эти операции будут линейно замедляться с ростом числа элементов в списке.

С другой стороны, из-за задач и внутреннего устройства deque операция взятия элемента по индексу не предусмотрена – она как раз будет медленной по сравнению с list. А с учётом наличия метода rotate ещё и смысл теряется.

Обычно deque используется в реализациях математических алгоритмов, использующих "очередь" (FIFO – first in, firt out). Также можно встретить deque, когда нам нужны кольцевые буфферы, или обработку данных по принципу "по кругу" (round-robin).

Подобно примеру из параграфа про list напишем эффективную очередь, точнее воспользуемся возможностями deque:

>>> from collections import deque
>>>
>>> queue = deque()
>>> queue.appendleft(1)
>>> queue.appendleft(2)
>>> print(queue.pop())
1

>>> queue.appendleft(3)
>>> queue.appendleft(4)
>>> print(queue.pop())
2

>>> print(queue)
deque([4, 3])

Словари на любой вкус

Быстрый поиск ключа в нескольких словарях можно делать с помощью ChainMap. Опять же воспользуемся примером из параграфа про dict:

>>> from collections import ChainMap
>>>
>>> heroes = {
...     'Капитан америка': 'Стивен Роджерс',
...     'Железный человек': 'Энтони Эдвард «Тони» Старк',
...     'Чёрная вдова': 'Наташа Романофф',
... }
>>>
>>> heroes_short = dict(
...     Кэп='Стивен Роджерс',
...     Сокол='Сэм Уилсон',
... )
>>>
>>> chain_map = ChainMap(heroes, heroes_short)
>>> print(chain_map['Кэп'])
Стивен Роджерс

В dict мы бы использовали метод update, который бы отработал за линейное время (время исполнения растёт со скоростью роста количетсва элементов словарей). ChainMap же сработает всегда за одно и то же время. С другой стороны, время доступа по ключу будет медленнее. Однако, для разового поиска в итоге будет быстрее ChainMap.

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

>>> import builtins
>>> from collections import ChainMap
>>>
>>> name_lookup = ChainMap(locals(), globals(), vars(builtins))
>>> name_lookup['heroes']
{'Капитан америка': 'Стивен Роджерс', 'Железный человек': 'Энтони Эдвард «Тони» Старк', 'Чёрная вдова': 'Наташа Романофф'}

Обратимся к другому примеру из параграфа dict – подсчёту повторов слов в тексте. Для подобных задач отлично подойдёт Counter. При чём решает он её с ходу:

>>> from collections import Counter
>>>
>>> word_stat = Counter(words)
>>> word_stat.most_common(10)
[('в', 41), ('Python', 34), ('1', 28), ('из', 27), ('2', 27), ('не', 26), ('и', 25), ('x', 24), ('0', 24), ('на', 20)]

Можно посчитать совокупную статистику по нескольким "тестам":

>>> another_stat = Counter(Python=5, не=10)
>>> sum_stat = word_stat + another_stat
>>> sum_stat['Python']
39
>>> sum_stat.most_common(6)
[('в', 41), ('Python', 39), ('не', 36), ('1', 28), ('из', 27), ('2', 27)]

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

До Python версии 3.6 словари не гарантировали порядок ключей – он мог отличаться от порядка добавления, а при добавлении нового ключа старые могли поменять порядок также. Тогда особо полезно было знать об OrderedDict – словарь, который поддерживает порядок ключей. Также он позволяет программисту менять порядок:

>>> from collections import OrderedDict
>>>
>>> ordered = OrderedDict([('first', 1337), ('second', 1984), ('third', 100500)])
>>> ordered.keys()
odict_keys(['first', 'second', 'third'])
>>> ordered.move_to_end('first')
>>> ordered
OrderedDict([('second', 1984), ('third', 100500), ('first', 1337)])
>>> ordered.move_to_end('third', last=False)
>>> ordered
OrderedDict([('third', 100500), ('second', 1984), ('first', 1337)])

Таким образом, на базе OrderedDict вы можете построить работу со словарём как с очередью.

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

Опять же обратимся к примеру с подсчётом статистики. На обычных словарях сбор статистики будет выглядеть так:

stat = dict()
for word in words:
    if word not in stat:
        stat[word] = 0
    stat[word] += 1

Для defaultdict:

from collections import defaultdict

stat = defaultdict(int)
for word in words:
    stat[word] += 1

Что мы сделали? Вспомним конструктор целых чисел в Python: если его вызвать без агрументов, то он создаст число 0. Так и в примере мы сказали использовать функцию-конструктор int для создания значения, если ключ отсутствует – получаем желанный 0, к которому прибавляем 1 при первом нахождении слова. Код получается более простой, элегантный.