5. Структуры данных

Данная глава описывает некоторые вещи, которые вы уже изучили, более детально, и добавляет кое-что новое.

5.1. Подробнее о списках

Тип данных list имеет ещё несколько методов. Здесь перечислены все методы списков:

list.append(value, /)

Добавить элемент в конец списка. Аналогично a[len(a):] = [x].

list.extend(iterable, /)

Расширить список, добавив все элементы из итерируемого объекта. Аналогично a[len(a):] = iterable.

list.insert(index, value, /)

Вставить элемент на определенную позицию. Первый аргумент — это индекс элемента, перед которым происходит вставка, таким образом a.insert(0, x) поместит элемент в начало списка, а a.insert(len(a), x) эквивалентно a.append(x).

list.remove(value, /)

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

list.pop(index=-1, /)

Удалить элемент в заданной позиции списка и вернуть его. Если индекс не указан, a.pop() удаляет и возвращает последний элемент списка. Возбуждает IndexError, если список пуст или индекс находится за пределами допустимого диапазона.

list.clear()

Удалить все элементы из списка. Аналогично del a[:].

list.index(value[, start[, stop]])

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

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

list.count(value, /)

Возвращает количество вхождений value в списке.

list.sort(*, key=None, reverse=False)

Отсортировать элементы списка на месте (аргументы можно использовать для настройки сортировки, смотри sorted() для их пояснения).

list.reverse()

Развернуть элементы списка на месте.

list.copy()

Вернуть неглубокую копию списка. Аналогично a[:].

Пример, который использует большинство методов списка:

>>> fruits = ['апельсин', 'яблоко', 'груша', 'банан', 'киви', 'яблоко', 'банан']
>>> fruits.count('яблоко')
2
>>> fruits.count('мандарин')
0
>>> fruits.index('банан')
3
>>> fruits.index('банан', 4)  # Найти следующий 'банан', начиная с позиции 4
6
>>> fruits.reverse()
>>> fruits
['банан', 'яблоко', 'киви', 'банан', 'груша', 'яблоко', 'апельсин']
>>> fruits.append('виноград')
>>> fruits
['банан', 'яблоко', 'киви', 'банан', 'груша', 'яблоко', 'апельсин', 'виноград']
>>> fruits.sort()
>>> fruits
['апельсин', 'банан', 'банан', 'виноград', 'груша', 'киви', 'яблоко', 'яблоко']
>>> fruits.pop()
'яблоко'

Вы могли заметить, что методы вроде insert, remove или sort, которые изменяют список, не выводят возвращаемого значения — они возвращают значение по умолчанию None. [1] Такой принцип использовался при проектировании всех изменяемых структур данных в Python.

Еще одна вещь, на которую стоит обратить внимание — не все данные можно отсортировать или сравнить. Например, [None, 'hello', 10] невозможно отсортировать, поскольку целые числа нельзя сравнивать со строками, а None нельзя сравнивать с другими типами. Кроме того, существуют типы данных, которые не имеют определённого отношения порядка. Например, 3+4j < 5+7j не является допустимым сравнением.

5.1.1. Использование списка в качестве стека

Методы списка позволяют очень легко использовать список как стек, где последний добавленный элемент является первым извлекаемым («последним пришёл — первым ушёл»). Чтобы добавить элемент на вершину стека, используйте append(), а для извлечения элемента с вершины стека — pop() без индекса. Например:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

5.1.2. Использование списка в качестве очереди

Список также можно использовать как очередь, где первый добавленный элемент — первый извлекаемый («первым пришёл — первым ушёл»); однако списки неэффективны для этой цели. Быстрыми являются добавления и извлечения элементов с конца списка, но вставки или извлечения из начала списка — медленные (так как все остальные элементы нужно сдвигать на одну позицию).

Для реализации очереди, используйте collections.deque, который создан для быстрого добавления и извлечения элементов с обоих концов. Например:

>>> from collections import deque
>>> queue = deque(["Эрик", "Джон", "Майкл"])
>>> queue.append("Терри")           # Терри пришёл
>>> queue.append("Грэм")            # Грэм пришёл
>>> queue.popleft()                 # Первый пришедший теперь уходит
'Эрик'
>>> queue.popleft()                 # Второй пришедший теперь уходит
'Джон'
>>> queue                           # Оставшаяся очередь в порядке прибытия
deque(['Майкл', 'Терри', 'Грэм'])

5.1.3. Списковые включения

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

Например, предположим, что мы хотим создать список квадратов:

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Обратите внимание, что это создаёт (или перезаписывает) переменную x, которая останется существовать после завершения цикла. Мы можем создать список квадратов без побочных эффектов, используя:

squares = list(map(lambda x: x**2, range(10)))

или, эквивалентно:

squares = [x**2 for x in range(10)]

что короче и читабельнее.

Списковое включение состоит из квадратных скобок, содержащих выражение, за которым следует ветвь for, затем ноль или более ветвей for или if. Результатом будет новый список, полученный вычислением выражения в контексте следующих за ним ветвей for и if. Например, это включение объединяет элементы двух списков, если они не равны:

>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

и эквивалентно следующему коду:

>>> combs = []
>>> for x in [1,2,3]:
...     for y in [3,1,4]:
...         if x != y:
...             combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

Обратите внимание, что порядок инструкций for и if одинаков в обоих фрагментах.

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

>>> vec = [-4, -2, 0, 2, 4]
>>> # создать новый список с удвоенными значениями
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # отфильтровать список, исключив отрицательные числа
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # применить функцию ко всем элементам
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # вызвать метод для каждого элемента
>>> freshfruit = ['  банан', '   логанова ягода ', ' маракуйя  ']
>>> [weapon.strip() for weapon in freshfruit]
['банан', 'логанова ягода', 'маракуйя']
>>> # создать список кортежей их пар вроде (число, квадрат)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # кортеж должен быть в скобках, иначе будет ошибка
>>> [x, x**2 for x in range(6)]
  File "<stdin>", line 1
    [x, x**2 for x in range(6)]
     ^^^^^^^
SyntaxError: did you forget parentheses around the comprehension target?
>>> # развернуть список в плоскую структуру, используя включение с двумя 'for'
>>> vec = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in vec for num in elem]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Включения списков могут содержать сложные выражения и вложенные функции:

>>> from math import pi
>>> [str(round(pi, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

5.1.4. Вложенные списковые включения

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

Рассмотрим следующий пример матрицы 3x4, реализованной в виде списка из 3 списков длины 4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

Следующее включение списка транспонирует строки и столбцы:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Как мы видели в предыдущей секции, вложенное списковое включение вычисляется в контексте внешней ветви for, которая за ним следует, поэтому этот пример эквивалентен:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

что, в свою очередь, тоже самое, что:

>>> transposed = []
>>> for i in range(4):
...     # следующие 3 строки реализуют вложенное списковое включение
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

На практике лучше отдавать предпочтение встроенным функциям, а не сложным управляющим конструкциям. Функция zip() отлично подходит для этой задачи:

>>> list(zip(*matrix))
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

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

5.2. Инструкция del

Есть способ удалить элемент из списка по его индексу, а не по значению: инструкция del. Это отличается от метода pop(), который возвращает значение. Инструкция del также может использоваться для удаления срезов или очистки всего списка (что мы уже делали, присваивая пустой список срезу). Например:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del может также быть использовано для удаления переменных целиком:

>>> del a

Теперь обращение к имени a приведёт к ошибке (по крайней мере до тех пор, пока ему снова не будет присвоено значение). Далее мы увидим и другие применения инструкции del.

5.3. Кортежи и последовательности

Мы видели, что списки и строки имеют много общих свойств, таких как индексация и операции со срезами. Они представляют собой 2 примера типов данных последовательностей (смотри Sequence Types — list, tuple, range). Поскольку Python развивается, могут появляться новые типы последовательностей. Существует также ещё один стандартный тип данных последовательности: кортеж.

Кортеж состоит из ряда значений, разделенных запятыми, например:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
>>> u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Tuples are immutable:
>>> t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # but they can contain mutable objects:
>>> v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

Как видно, при выводе кортежи всегда заключаются в круглые скобки, чтобы вложенные кортежи интерпретировались правильно. Вводить их можно как со скобками, так и без, хотя во многих случаях скобки всё равно необходимы (если кортеж — часть большего выражения). Невозможно присваивать отдельным элементам кортежа, однако можно создавать кортежи, содержащие изменяемые объекты, такие как списки.

Хотя кортежи могут выглядеть похожими на списки, они часто используются в разных ситуациях и для разных целей. Кортежи immutable и обычно содержат гетерогенную последовательность элементов, которая доступна через распаковку (см. далее в этом разделе) или через индексацию (или даже через атрибут, если это namedtuples). Списки mutable, и их элементы обычно однородны и доступны при итерации по ним.

Отдельная сложность заключается в построении кортежей, содержащих 0 или 1 элемент: синтаксис имеет некоторые дополнительные особенности, к которым нужно привыкнуть. Пустой кортеж создаётся пустой парой скобок; кортеж с одним элементом — добавлением запятой после значения (недостаточно заключить это значение в скобки). Некрасиво, но работает. Например:

>>> empty = ()
>>> singleton = 'привет',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('привет',)

Инструкция t = 12345, 54321, 'hello!' — это пример упаковки кортежа: значения 12345, 54321 and 'hello!' упакованы вместе в один кортеж. Также возможна обратная операция:

>>> x, y, z = t

Это называется, соответственно, распаковкой последовательности и работает для любой последовательности с правой стороны. Распаковка последовательности требует, чтобы слева от знака равенства было столько переменных, сколько элементов в последовательности. Обратите внимание, что множественное присваивание — это просто комбинация упаковки кортежа и распаковки последовательности.

5.4. Множества

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

Множества можно создавать с помощью фигурных скобок или функции set(). Примечание: чтобы создать пустое множество, нужно использовать set(), а не {}; потому что последнее выражение создаёт пустой словарь — структуру данных, которую мы обсудим в следующем разделе.

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

Вот краткая демонстрация:

>>> basket = {'яблоко', 'апельсин', 'яблоко', 'груша', 'апельсин', 'банан'}
>>> print(basket)                      # показать, что дубликаты удалены
{'апельсин', 'банан', 'груша', 'яблоко'}
>>> 'апельсин' in basket               # быстрая проверка принадлежности
True
>>> 'пырей' in basket
False

>>> # Демонстрация операций над множествами уникальных букв двух слов
>>>
>>> a = set('абракадабра')
>>> b = set('алакозам')
>>> a                                  # уникальные буквы в a
{'б', 'а', 'р', 'к', 'д'}
>>> a - b                              # буквы в a, но не в b
{'р', 'д', 'б'}
>>> a | b                              # буквы в a или b, или в обоих
{'з', 'б', 'а', 'р', 'о', 'к', 'м', 'л', 'д'}
>>> a & b                              # буквы в a или b, или в обоих
{'к', 'а'}
>>> a ^ b                              # буквы в одном, но не в обоих
{'з', 'б', 'о', 'р', 'м', 'л', 'д'}

Similarly to list comprehensions, set comprehensions are also supported:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. Словари

Ещё один полезный тип данных, встроенный в Python, — это словарь (см. Mapping Types — dict). В других языках словари иногда называют ассоциативной памятью или ассоциативными массивами. В отличие от последовательностей, индексируемых диапазоном чисел, словари индексируются ключами, которыми может быть любой неизменяемый тип; строки и числа всегда могут быть ключами. Кортежи тоже могут быть ключами, если они содержат только строки, числа или кортежи; если же кортеж содержит любой изменяемый объект напрямую или косвенно, его нельзя использовать как ключ. Нельзя использовать списки как ключи, поскольку списки можно изменять на месте с помощью присваивания элементам, присваивания срезам или методов типа append() и extend().

Удобнее всего думать о словаре как о множестве пар ключ: значение с уникальными ключами (в пределах одного словаря). Пара фигурных скобок создаёт пустой словарь: {}. Размещение внутри скобок списка пар ключ:значение, разделённых запятыми, добавляет эти пары в словарь. Этот же формат используется при выводе словарей.

Основные операции со словарём — это сохранение и извлечение значения по ключу. Также можно удалить пару ключ:значение с помощью del. Если сохранить значение по ключу, который уже используется, предыдущее значение, связанное с ним, будет забыто.

Попытка извлечь значение по несуществующему ключу с помощью обращения (d[key]) приводит к возбуждению исключения KeyError. Чтобы избежать этого при обращении к потенциально отсутствующему ключу, используйте метод get(), который возвращает None (или указанное значение по умолчанию), если ключа нет в словаре.

Выполнение list(d) для словаря возвращает список всех ключей в словаре, в порядке их добавления (если они должны быть отсортированы — просто вызовите sorted(d)). Чтобы проверить наличие ключа в словаре, используйте ключевое слово in.

Вот небольшой пример использования словаря:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> tel['irv']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'irv'
>>> print(tel.get('irv'))
None
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'jack': 4098, 'guido': 4127, 'irv': 4127}
>>> list(tel)
['jack', 'guido', 'irv']
>>> sorted(tel)
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Конструктор dict() строит словарь напрямую из последовательности пар ключ-значение:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'guido': 4127, 'jack': 4098}

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

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Когда ключи — простые строки, иногда проще указывать пары через именованные аргументы:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'guido': 4127, 'jack': 4098}

5.6. Техники перебора

При переборе словаря можно одновременно получать ключ и соответствующее значение с помощью метода items().

>>> knights = {'галахад': 'чистый', 'робин': 'храбрый'}
>>> for k, v in knights.items():
...     print(k, v)
...
галахад чистый
робин храбрый

При переборе последовательности индекс позиции и соответствующее значение могут быть получены одновременно с помощью функции enumerate().

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Чтобы перебирать две или более последовательности одновременно, их элементы можно объединить в пары с помощью функции zip().

>>> questions = ['имя', 'замысел', 'любимый цвет']
>>> answers = ['ланселот', 'святой грааль', 'синий']
>>> for q, a in zip(questions, answers):
...     print('Какой у тебя {0}?  Это {1}.'.format(q, a))
...
Какой у тебя имя? Это ланселот.
Какой у тебя замысел? Это святой грааль.
Какой у тебя любимый цвет? Это синий.

Для перебора последовательности в обратном порядке, можно воспользоваться функцией reversed().

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Для перебора последовательности в отсортированном порядке используйте функцию sorted(), которая возвращает новый отсортированный список, оставляя исходную последовательность неизменной.

>>> basket = ['яблоко', 'апельсин', 'яблоко', 'груша', 'апельсин', 'банан']
>>> for i in sorted(basket):
...     print(i)
...
апельсин
апельсин
банан
груша
яблоко
яблоко

Использование set() в последовательности удаляет повторяющиеся элементы. Использование sorted() в сочетании с set() над последовательностью является идиоматическим способом обхода уникальных элементов последовательности в отсортированном порядке.

>>> basket = ['яблоко', 'апельсин', 'яблоко', 'груша', 'апельсин', 'банан']
>>> for f in sorted(set(basket)):
...     print(f)
...
апельсин
банан
груша
яблоко

Иногда возникает соблазн изменить список во время его обхода; однако часто проще и безопаснее вместо этого создать новый список.

>>> import math
>>> raw_data = [56.2, float('NaN'), 51.7, 55.3, 52.5, float('NaN'), 47.8]
>>> filtered_data = []
>>> for value in raw_data:
...     if not math.isnan(value):
...         filtered_data.append(value)
...
>>> filtered_data
[56.2, 51.7, 55.3, 52.5, 47.8]

5.7. Больше о условиях

Условия, используемые в инструкциях while и if, могут содержать любые операторы, а не только сравнения.

Операторы сравнения in и not in проверяют принадлежность, то есть определяют, находится ли значение в контейнере (или нет). Операторы is и is not сравнивают, являются ли два объекта действительно одним и тем же объектом. Все операторы сравнения имеют одинаковый приоритет, который ниже, чем у всех числовых операторов.

Сравнения можно объединять в цепочки. Например, a < b == c проверяет, является ли a меньше значения b и, кроме того, равно ли b значению c.

Сравнения можно объединять с использованием логических операторов and и or, и результат сравнения (или любого другого логического выражения) можно отрицать с помощью not. Они имеют более низкий приоритет, чем операторы сравнения; среди них not имеет наивысший приоритет, а or — наименьший, так что A and not B or C эквивалентно (A and (not B)) or C. Как всегда, скобки могут быть использованы для выражения нужной структуры.

Логические операторы and и or вычисляются по так называемой короткой схеме: их аргументы вычисляются слева направо, и вычисление прекращается, как только определён результат. Например, если A и C истинны, но B ложно, A and B and C не вычисляет выражение C. При использовании таких выражений в качестве обычных значений, а не логических, возвращаемым значением оператора, вычисляемого по короткой схеме, является последний вычисленный аргумент.

Переменной можно присвоить результат сравнения или другое логическое выражение. Например,

>>> string1, string2, string3 = '', ' Тронхейм', 'Танец Хаммера'
>>> non_null = string1 or string2 or string3
>>> non_null
' Тронхейм'

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

5.8. Сравнение последовательностей и других типов

Объекты-последовательности обычно можно сравнивать с другими объектами того же типа последовательности. При сравнении используется лексикографический порядок: сначала сравниваются первые два элемента, и если они отличаются, это определяет результат сравнения; если они равны, сравниваются следующие два элемента, и так далее, пока одна из последовательностей не закончится. Если два сравниваемых элемента сами по себе являются последовательностями одного типа, лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей оказываются равными, последовательности считаются равными. Если одна последовательность является начальной подпоследовательностью другой, то более короткая последовательность является меньшей. Лексикографический порядок строк использует номер кодовой точки Unicode для упорядочивания отдельных символов. Некоторые примеры сравнений между последовательностями одного типа:

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Обратите внимание, что сравнение объектов разных типов с помощью < или > допустимо при условии, что объекты имеют соответствующие методы сравнения. Например, смешанные числовые типы сравниваются по их числовому значению, поэтому 0 равно 0.0 и т.д. В противном случае, вместо того чтобы вводить какой-либо произвольный порядок сравнения, интерпретатор выбросит исключение TypeError.

Примечания