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

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

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

list.append(value, /)

Добавляет элемент в конец списка. Аналогично a[len(a):] = [x].

list.extend(iterable, /)

Добавляет в список все элементы из итерируемого объекта. Аналогично a[len(a):] = iterable.

list.insert(index, value, /)

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

list.remove(value, /)

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

list.pop(index=-1, /)

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

list.clear()

Удаляет все элементы из списка. Аналогично del a[:].

list.index(value[, start[, stop]])

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

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

list.count(value, /)

Возвращает количество вхождений value в список.

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.

Сноски