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

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 a 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 не является допустимым сравнением.

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

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

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

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

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

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

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

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

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

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

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();.