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

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

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

У типа данных список также имеются еще несколько методов. Ниже приведены все методы объекта типа список:

list.append(x)

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

list.extend(iterable)

Расширить список за счёт добавления всех элементов переданного списка. Эквивалентно a[len(a):] = iterable.

list.insert(i, x)

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

list.remove(x)

Удалить первый найденный элемент из списка, значение которого — x. Если элемент не найден, то поднимается ValueError.

list.pop([i])

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

list.clear()

Удалить все элементы из списка. Эквивалентный del a[:].

list.index(x[, start[, end]])

Возвращает отсчитываемый от нуля индекс в списке первого элемента, значение которого равно x. Вызывает ValueError при отсутствии такого элемента.

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

list.count(x)

Вернуть значение сколько раз, x появляется в списке.

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

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

list.reverse()

Обратить порядок элементов списка, на месте.

list.copy()

Вернуть поверхностную копию списка. Эквивалентно a[:].

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

>>> fruits = ['orange', 'apple', 'pear', 'banana', 'kiwi', 'apple', 'banana']
>>> fruits.count('apple')
2
>>> fruits.count('tangerine')
0
>>> fruits.index('banana')
3
>>> fruits.index('banana', 4)  # Найти следующий банан, начиная с позиции 4
6
>>> fruits.reverse()
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange']
>>> fruits.append('grape')
>>> fruits
['banana', 'apple', 'kiwi', 'banana', 'pear', 'apple', 'orange', 'grape']
>>> fruits.sort()
>>> fruits
['apple', 'apple', 'banana', 'banana', 'grape', 'kiwi', 'orange', 'pear']
>>> fruits.pop()
'pear'

Вы могли заметить, что такие методы, как 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(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry прибывает
>>> queue.append("Graham")          # Graham прибывает
>>> queue.popleft()                 # Первый прибывший сейчас уходит
'Eric'
>>> queue.popleft()                 # Второй прибывающий теперь уходит
'John'
>>> queue                           # Оставшаяся очередь в порядке поступления
deque(['Michael', 'Terry', 'Graham'])

5.1.3. Cписковое включение (List Comprehensions)

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

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

>>> 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)]

Который является более кратким и удобочитаемым.

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

>>> [(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 = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # создать список из двух кортежей, например (number, square)
>>> [(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, in <module>
    [x, x**2 for x in range(6)]
               ^
SyntaxError: invalid syntax
>>> # сгладить список с помощью listcomp с двумя '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]]

Как мы видели в предыдущем разделе, вложенный listcomp вычислется в контексте следующего за ним 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 строки реализуют вложенный listcomp
...     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. Кортежи и последовательности

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

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

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Кортежи могут быть вложенными:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
>>> # Кортежи неизменяемы:
... t[0] = 88888
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> # но они могут содержать изменяемые объекты:
... v = ([1, 2, 3], [3, 2, 1])
>>> v
([1, 2, 3], [3, 2, 1])

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

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

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

>>> empty = ()
>>> singleton = 'hello',    # <-- обратите внимание на конечную запятую
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

Выражение t = 12345, 54321, 'hello!' является примером упаковки кортежей: значения 12345, 54321 и 'hello!' упаковываются в кортеж. Возможна также обратная операция:

>>> x, y, z = t

Такое действие называется, довольно удачно, распаковкой последовательности (sequence unpacking) и работает для любой последовательности на правой стороне. Pаспаковка последовательности требует, чтобы было столько же переменных слева от знака равно, сколько элементов в последовательности. Обратите внимание, что множественное присваивание на самом деле просто комбинация упаковки кортежа и распаковки последовательности.

5.4. Множества

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

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

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

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # показать, что дубликаты были удалены
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # быстрое тестирование членства
True
>>> 'crabgrass' in basket
False

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

Аналогично списковым включениям (list comprehensions), также поддерживаются генераторы множеств:

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

5.5. Словари

Другим полезным типом данных, встроенным в Python, является словарь (см. Типы сопоставления — dict). Словари иногда встречаются в других языках как «ассоциативные записи» или «ассоциативные массивы». В отличие от последовательностей, которые являются индексируемыми по диапазону чисел, словари индексируются по ключам, которые могут быть любым неизменным типом; строки и числа всегда могут быть ключами. Кортежи могут быть ключами только если они составлены из строк, чисел или кортежей; если кортеж содержит какой-либо изменяемый объект, явно или неявно, то он не может быть использован в качестве ключа. Вы не можете использовать списки в роли ключей, поскольку списки могут быть изменены на месте присваиванием по индексу, присваиванием по срезу или такими методами как append() и extend().

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

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

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

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

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'jack': 4098, 'sape': 4139, 'guido': 4127}
>>> tel['jack']
4098
>>> 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 = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

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

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

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

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

Для обхода последовательности в обратном порядке сначала укажите последовательность в прямом направлении и затем вызовите функцию reversed().:

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

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

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

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

>>> 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 True, а B false, A and B and C не вычисляет выражение C. Короткозамкнутый оператор возвращает последний элемент, который был вычислен, что может быть применено не только в целях задания логики.

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

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Обратите внимание, что в 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.

Сноски

[1]	Другие языки могут возвращать измененный объект, который допускает цепочку методов, например d->insert("a")->remove("b")->sort();.