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

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

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

Примечания