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

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