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

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

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