5. Структуры данных¶

5.1. Подробнее о списках¶

У типа данных list есть еще несколько методов. Вот все методы объектов list:

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 интерпретируются как в нотации slice и используются для ограничения поиска определенной подпоследовательностью списка. Возвращаемый индекс вычисляется относительно начала полной последовательности, а не аргумента 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. Кортежи и последовательности¶

Мы видели, что списки и строки обладают многими общими свойствами, такими как индексация и операции разбиения на фрагменты. Это два примера типов данных sequence (см. Типы последовательностей — list, tuple, range). Поскольку Python - развивающийся язык, могут быть добавлены другие типы данных sequence. Существует также другой стандартный тип данных последовательности: кортеж.

Кортеж состоит из нескольких значений, разделенных запятыми, например:

>>> 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])

Как вы видите, при выводе кортежи всегда заключаются в круглые скобки, так что вложенные кортежи интерпретируются правильно; они могут вводиться как с окружающими круглыми скобками, так и без них, хотя часто круглые скобки все равно необходимы (если кортеж является частью более крупного выражения). Невозможно присвоить значение отдельным элементам кортежа, однако можно создавать кортежи, содержащие изменяемые объекты, такие как списки.

Хотя кортежи могут показаться похожими на списки, они часто используются в разных ситуациях и для разных целей. Кортежи имеют immutable и обычно содержат разнородную последовательность элементов, доступ к которым осуществляется посредством распаковки (см. далее в этом разделе) или индексации (или даже по атрибуту в случае namedtuples). Списки состоят из mutable, а их элементы обычно однородны, и доступ к ним осуществляется путем итерации по списку.

Особой проблемой является построение кортежей, содержащих 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 также есть тип данных для sets. Set - это неупорядоченная коллекция, в которой нет повторяющихся элементов. Основные области применения включают проверку принадлежности и устранение повторяющихся записей. Объекты Set также поддерживают математические операции, такие как объединение, пересечение, разность и симметричная разность.

Для создания наборов можно использовать фигурные скобки или функцию 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'}

Аналогично list comprehensions, также поддерживаются наборы значений:

>>> 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}

Кроме того, понимание dict можно использовать для создания словарей на основе произвольных выражений ключей и значений:

>>> {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 равны true, а B равно false, то A and B and C не вычисляет выражение C. При использовании в качестве общего значения, а не логического, возвращаемое значение оператора короткого замыкания является последним вычисленным аргументом.

Переменной можно присвоить результат сравнения или другое логическое выражение. Например,

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Обратите внимание, что в Python, в отличие от C, присваивание внутри выражений должно выполняться явно с помощью walrus operator :=. Это позволяет избежать распространенных проблем, возникающих в программах на 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.

Сноски