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

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

Тип данных list имеет ещё несколько методов. Ниже перечислены все методы объектов list:

list.append(x)

Добавляет элемент в конец списка; эквивалентно a[len(a):] = [x].

list.extend(L)

Расширяет список, добавляя все элементы из переданного списка; эквивалентно a[len(a):] = L.

list.insert(i, x)

Вставляет элемент в заданную позицию. Первый аргумент – это индекс элемента, перед которым нужно вставить, поэтому a.insert(0, x) вставляет в начало списка, а a.insert(len(a), x) эквивалентно a.append(x).

list.remove(x)

Удаляет первый элемент списка, значение которого равно x. Возникает ошибка, если такого элемента нет.

list.pop([i])

Удаляет элемент в заданной позиции в списке и возвращает его. Если индекс не указан, a.pop() удаляет и возвращает последний элемент списка. (Квадратные скобки вокруг i в сигнатуре метода указывают, что параметр является необязательным, а не на то, что нужно вводить квадратные скобки в этой позиции. Эта нотация часто встречается в Справочнике по библиотеке Python.)

list.index(x)

Возвращает индекс первого элемента в списке, значение которого равно x. Если такого элемента нет, возникает ошибка.

list.count(x)

Возвращает количество вхождений x в список.

list.sort()

Сортирует элементы списка на месте.

list.reverse()

Разворачивает элементы списка на месте.

Пример, использующий большинство методов списка:

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count(66.25), a.count('x'))
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sort()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]

>>> 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")           # Терри прибывает
>>> queue.append("Graham")          # Грэм прибывает
>>> queue.popleft()                 # Первый прибывший теперь уходит
'Eric'
>>> queue.popleft()                 # Второй прибывший теперь уходит
'John'
>>> queue                           # Оставшаяся очередь в порядке прибытия
deque(['Michael', 'Terry', 'Graham'])

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

>>> [x, x**2 for x in vec]  # ошибка – для кортежей требуются скобки
  File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

>>> mat = [
...        [1, 2, 3],
...        [4, 5, 6],
...        [7, 8, 9],
...       ]

>>> print([[row[i] for row in mat] for i in [0, 1, 2]])
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

for i in [0, 1, 2]:
    for row in mat:
        print(row[i], end="")
    print()

>>> list(zip(*mat))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

5.2. Оператор del¶The del statement

Существует способ удалить элемент из списка по его индексу, а не по значению: оператор 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. Кортежи и последовательности¶Tuples and Sequences

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

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

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Кортежи могут быть вложенными:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

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

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

Особая проблема – создание кортежей, содержащих 0 или 1 элемент: в синтаксисе есть некоторые дополнительные особенности для таких случаев. Пустые кортежи создаются с помощью пустой пары круглых скобок; кортеж с одним элементом создается путем добавления запятой после значения (недостаточно заключить одно значение в скобки). Некрасиво, но эффективно. Например:

>>> empty = ()
>>> singleton = 'hello',    # <-- обратите внимание на завершающую запятую
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

Оператор t = 12345, 54321, 'hello!' является примером упаковки кортежа: значения 12345, 54321 и 'hello!' упаковываются вместе в кортеж. Возможна и обратная операция:

>>> x, y, z = t

Это называется, что вполне уместно, распаковкой последовательности и работает для любой последовательности в правой части. Распаковка последовательности требует, чтобы переменных в левой части знака равенства было столько же, сколько элементов в последовательности. Обратите внимание, что множественное присваивание – это на самом деле комбинация упаковки кортежа и распаковки последовательности.

5.4. Множества¶Sets

Python также включает тип данных для множеств. Множество – это неупорядоченная коллекция без повторяющихся элементов. Основные применения: проверка принадлежности и удаление дубликатов. Объекты-множества также поддерживают математические операции, такие как объединение, пересечение, разность и симметрическая разность.

Фигурные скобки или функция set() могут использоваться для создания множеств. Примечание: чтобы создать пустое множество, нужно использовать set(), а не {}; последнее создаёт пустой словарь – структуру данных, которую мы обсудим в следующем разделе.

Вот краткая демонстрация:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # показать, что дубликаты удалены
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # быстрая проверка принадлежности
True
>>> 'crabgrass' in basket
False

>>> # Демонстрация операций над множествами с уникальными буквами из двух слов
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # уникальные буквы в a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # буквы, которые есть в a, но нет в b
{'r', 'd', 'b'}
>>> a | b                              # Буквы из a или b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # буквы, которые есть и в a, и в b
{'a', 'c'}
>>> a ^ b                              # буквы, которые есть в a или в b, но не в обоих
{'r', 'd', 'b', 'm', 'z', 'l'}

Как для списков, существует синтаксис генератора множеств:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

5.5. Словари¶Dictionaries

Ещё одним полезным типом данных, встроенным в Python, является словарь (см. Типы отображений – dict). В других языках словари иногда называются «ассоциативными запоминающими устройствами» или «ассоциативными массивами». В отличие от последовательностей, которые индексируются диапазоном чисел, словари индексируются ключами, которые могут быть любого неизменяемого типа; строки и числа всегда могут быть ключами. Кортежи могут использоваться как ключи, если они содержат только строки, числа или кортежи; если кортеж содержит любой изменяемый объект прямо или косвенно, он не может быть использован как ключ. Списки нельзя использовать как ключи, поскольку списки можно изменять на месте с помощью присваиваний по индексу, срезу или методов, таких как append() и extend().

Словарь лучше всего представлять как неупорядоченное множество пар ключ: значение, при этом ключи должны быть уникальными (в пределах одного словаря). Пара фигурных скобок создает пустой словарь: {}. Размещение внутри скобок списка пар ключ:значение, разделенных запятыми, добавляет начальные пары ключ:значение в словарь; так же словари отображаются при выводе.

Основные операции над словарём – это сохранение значения по некоторому ключу и извлечение значения по заданному ключу. Также можно удалить пару ключ:значение с помощью del. Если сохранить значение по уже используемому ключу, старое значение, связанное с этим ключом, будет забыто. Извлечение значения по несуществующему ключу является ошибкой.

Выполнение list(d.keys()) над словарём возвращает список всех ключей, используемых в словаре, в произвольном порядке (если требуется отсортированный список, используйте вместо этого sorted(d.keys())). [1] Чтобы проверить, находится ли отдельный ключ в словаре, используйте ключевое слово in.

Вот небольшой пример использования словаря:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Конструктор dict() создаёт словари непосредственно из последовательностей пар ключ-значение:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}

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

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

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

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}

5.6. Техники циклов¶Looping Techniques

При переборе словарей ключ и соответствующее значение можно получить одновременно с помощью метода 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

5.7. Подробнее об условиях¶More on Conditions

Условия, используемые в операторах 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 являются так называемыми short-circuit операторами: их аргументы вычисляются слева направо, и вычисление прекращается, как только результат становится определённым. Например, если 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 могут ворчать по этому поводу, но это позволяет избежать распространённого класса проблем, встречающихся в программах на C: ввод = в выражении, когда подразумевался ==.

5.8. Сравнение последовательностей и других типов¶Comparing Sequences and Other Types

Объекты последовательностей можно сравнивать с другими объектами того же типа последовательности. Сравнение использует лексикографический порядок: сначала сравниваются первые два элемента, и если они различаются, это определяет результат сравнения; если они равны, сравниваются следующие два элемента, и так далее, пока одна из последовательностей не закончится. Если два сравниваемых элемента сами являются последовательностями того же типа, лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей равны, последовательности считаются равными. Если одна последовательность является начальной подпоследовательностью другой, более короткая последовательность считается меньшей (меньшей). Лексикографический порядок для строк использует номер кодовой точки Unicode для упорядочивания отдельных символов. Некоторые примеры сравнений между последовательностями одного типа:

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

Сноски