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

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

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

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

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() удаляет и возвращает последний элемент в списке. Если список пуст или индекс выходит за пределы диапазона списка, вызывается сообщение IndexError.

list.clear()

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

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

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

Необязательные аргументы start и end интерпретируются как в нотации slice и используются для ограничения поиска определенной подпоследовательностью списка. Возвращаемый индекс вычисляется относительно начала полной последовательности, а не аргумента 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)  # Find next banana starting at position 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 arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

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. Например, этот 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]
>>> # create a new list with the values doubled
>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]
>>> # filter the list to exclude negative numbers
>>> [x for x in vec if x >= 0]
[0, 2, 4]
>>> # apply a function to all the elements
>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]
>>> # call a method on each element
>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> # create a list of 2-tuples like (number, square)
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
>>> # the tuple must be parenthesized, otherwise an error is raised
>>> [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?
>>> # flatten a list using a listcomp with two '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):
...     # the following 3 lines implement the nested 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. Кортежи и последовательности

Мы видели, что списки и строки имеют много общих свойств, таких как операции индексирования и нарезки. Они являются двумя примерами последовательных типов данных (см. Типы последовательностей — 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 = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

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

>>> x, y, z = t

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

5.4. Наборы

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

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

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

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # show that duplicates have been removed
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # fast membership testing
True
>>> 'crabgrass' in basket
False

>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # letters in a but not in b
{'r', 'd', 'b'}
>>> a | b                              # letters in a or b or both
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # letters in both a and b
{'a', 'c'}
>>> a ^ b                              # letters in a or b but not both
{'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}

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

>>> {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 i in sorted(basket):
...     print(i)
...
apple
apple
banana
orange
orange
pear

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

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

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

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

Обратите внимание, что в Python, в отличие от C, присваивание внутри выражений должно выполняться явно с помощью walrus operator :=. Это позволяет избежать распространенного класса проблем, встречающихся в программах на 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.

Сноски