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

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

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

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

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

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

При создании кортежей из 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'}

Подобно генераторам списков, поддерживаются и генераторы множеств:

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

5.5. Словари

Ещё один полезный встроенный тип данных Python — словарь (см. раздел Типы отображений — 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 = {'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, присваивание внутри выражений должно быть явно обозначено с помощью оператора моржа :=. Это помогает избежать распространённого класса ошибок в программах на 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.

Сноски