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

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

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 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. Кортежи и последовательности

Мы видели, что списки и строки обладают многими общими свойствами, такими как индексирование и операции срезов. Они являются двумя примерами последовательностей типов данных (см. Типы последовательностей — список, кортеж, диапазон). Поскольку 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. Сравнение последовательностей и других типов

Объекты последовательностей обычно могут быть сравнимы с другими объектами того же типа последовательности. Сравнение использует лексикографическое упорядочение: сначала сравниваются первые два элемента, и если они отличаются, это определяет результат сравнения; если они равны, сравниваются следующие два элемента и так далее, пока одна из последовательностей не будет исчерпана. Если два сравниваемых элемента сами являются последовательностями одного и того же типа, то лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей сравниваются как равные, последовательности считаются равными. Если одна последовательность является начальной подпоследовательностью другой, то более короткая последовательность является меньшей (меньше). Лексикографическое упорядочение для строк использует число кода символа Юникода для упорядочения отдельных символов. Вот некоторые примеры сравнений между последовательностями одного и того же типа:

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