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

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, in <module>
    [x, x**2 for x in range(6)]
               ^
SyntaxError: invalid syntax
>>> # 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();.