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

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. Если сохранить значение по уже существующему ключу, прежнее значение, связанное с этим ключом, будет забыто. Попытка извлечь значение по несуществующему ключу приводит к ошибке.

Выполнение 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 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.

Сноски