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

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.

Сноски