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

• 5.1. Подробнее о списках
• 5.1.1. Использование списков в качестве стеков
• 5.1.2. Использование списков в качестве очередей
• 5.1.3. Генераторы списков
• 5.1.4. Вложенные генераторы списков
• 5.2. Оператор del
• 5.3. Кортежи и последовательности
• 5.4. Множества
• 5.5. Словари
• 5.6. Приемы использования цикла
• 5.7. Подробнее об условиях
• 5.8. Сравнение последовательностей и других типов

Эта глава более подробно описывает некоторые моменты, с которыми вы уже знакомы, и также добавляет некоторые новые факты.

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. Возникает ошибка, если такого элемента нет.

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

list.clear()
Удаляет все элементы из списка. Эквивалентно del a[:].

list.index(x[, start[, end]])
Возвращает индекс (отсчет с нуля) первого элемента в списке, чье значение равно x. Возникает ValueError (docs.python.org/3/library/exceptions.html#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) # Находит следующий banana, начиная с позиции 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.

5.1.1. Использование списков в качестве стеков

Методы списков делают возможным очень легко использовать список как стек, в котором последний добавленный элемент есть первый извлеченный элемент ("последним вошел, первым вышел"). Для добавления элемента вверх стека используйте append(). Для извлечения элемента из верха стека, используйте pop() без конкретного индекса. Например:

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

5.1.2. Использование списков в качестве очередей

Также возможно использовать список как очередь, где первый добавленный элемент есть первый извлеченный элемент ("первым вошел, первым вышел"); однако списки не эффективны для этой цели. В то время как добавление с помощью append() и извлечение с помощью pop() с конца списка осуществляются быстро, добавление с помощью insert() или извлечение с помощью pop() из начала списка происходит медленно (потому что все другие элементы должны быть сдвинуты на один).

Для реализации очереди используйте collections.deque (docs.python.org/3/library/collections.html#collections.deque), который был разработан для быстрых добавлений и извлечений с обоих концов. Например:

>>> from collections import deque

>>> queue = deque(["Eric", "John", "Michael"])

>>> queue.append("Terry") # Terry прибыл

>>> queue.append("Graham") # Graham прибыл

>>> queue.popleft() # Первый прибывший теперь покинул

'Eric'

>>> queue.popleft() # Второй прибывший теперь покинул

'John'

>>> queue # Остальная очередь в порядке прибытия

deque(['Michael', 'Terry', 'Graham'])

5.1.3. Генераторы списков

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

Например, предположим, мы хотим создать такой список квадратов:

>>> squares = []

>>> for x in range(10):

... squares.append(x**2)

...

>>> squares

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Заметьте, что создается (или перезаписывается) переменная под именем x, которая продолжает существовать после завершения цикла. Мы можем вычислить список квадратов без какого-либо побочного эффекта так:

squares = list(map(lambda x: x**2, range(10)))

что эквивалентно:

squares = [x**2 for x in range(10)]

Это более кратко и читабельно.

Генератор списка состоит из скобок, содержащих выражение, за которым следует for (docs.python.org/3/reference/compound_stmts.html#for), затем ни одной или больше for или условий if (docs.python.org/3/reference/compound_stmts.html#if). Результатом будет новый список, полученный от вычисления выражения в данном контексте присутствующих записей for и if. Например, этот listcomp сочетает в себе элементы двух списков, если они не равны:

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

Заметьте, что порядок операторов for и if одинаков в обоих данных частях кода.

Если выражение является кортежем (как (x, y) в предыдущем примере), оно должно быть заключено в скобки.

>>> vec = [-4, -2, 0, 2, 4]

>>> # создает новый список с удвоенными значениями

>>> [x*2 for x in vec]

[-8, -4, 0, 4, 8]

>>> # фильтрует список, исключая отрицательные числа

>>> [x for x in vec if x >= 0]

[0, 2, 4]

>>> # применяет функцию для всех элементов

>>> [abs(x) for x in vec]

[4, 2, 0, 2, 4]

>>> # вызывает метод для каждого элемента

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']

>>> [weapon.strip() for weapon in freshfruit]

['banana', 'loganberry', 'passion fruit']

>>> # создает список двойных кортежей как (число, квадрат)

>>> [(x, x**2) for x in range(6)]

[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

>>> # кортеж должен быть заключен в скобки, иначе возбуждается ошибка

>>> [x, x**2 for x in range(6)]

File "<stdin>", line 1, in ?

[x, x**2 for x in range(6)]

^

SyntaxError: invalid syntax

>>> # делает список одноуровневым, используя listcomp с двумя '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']

5.1.4. Вложенные генераторы списков

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

Рассмотрим следующий пример матрицы 3x4, реализованной как список из 3-х списков длиной по 4:

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

Как мы видели в предыдущем разделе, вложенный listcomp оценивается в контексте for (docs.python.org/3/reference/compound_stmts.html#for), который следует за ним, таким образом этот пример есть эквивалент для:

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

... # следующие 3 строки реализуют вложенный 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]]

В действительности вам следует предпочитать встроенные функции сложным цепочкам выражений. Функция zip() прекрасно выполнить работу в данном случае:

>>> list(zip(*matrix))

[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

См. Распаковка списков аргументов для деталей о звездочке в этой строке.

5.2. Оператор del

Существует способ удалить элемент из списка, передав его индекс вместо значения: оператор del (docs.python.org/3/reference/simple_stmts.html#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. Кортежи и последовательности

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

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

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

>>> # Кортежи неизменяемые:

... t[0] = 88888

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

TypeError: 'tuple' object does not support item assignment

>>> # но они могут содержать изменяемые объекты:

... v = ([1, 2, 3], [3, 2, 1])

>>> v

([1, 2, 3], [3, 2, 1])

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

Хотя кортежи могут показаться подобными спискам, они часто используются в разных ситуациях и для различных целей. Кортежи неизменяемые (docs.python.org/3/glossary.html#term-immutable) и обычно включают разнородную последовательность элементов, которые доступны через распаковку (см. позже в этом разделе) или индексирование (или даже по атрибуту в случае namedtuples (docs.python.org/3/library/collections.html#collections.namedtuple)). Списки изменяемы (docs.python.org/3/glossary.html#term-mutable), а их элементы обычно однородны и доступны посредством итерации списка.

Особая проблема - создание кортежей, включающих 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. Множества

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

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

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

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

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

Применение list(d.keys()) к словарю возвращает список всех ключей, используемых в словаре в произвольном порядке (если вы хотите отсортировать, просто вместо этого используйте sorted(d.keys())). [ 2] Чтобы проверить, есть ли какой-нибудь один ключ в словаре, используйте ключевое слово in (docs.python.org/3/reference/expressions.html#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. Приемы использования цикла

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

Объекты последовательностей могут сравниваться с другими объектами того же типа. Сравнение использует лексикографический порядок: сначала сравниваются первые два элемента, если они разные, то они и определяют результат сравнения; если они равны, сравниваются следующие два элемента, и т. д., пока одна из двух последовательностей не будет исчерпана. Если два сравниваемых элемента сами являются последовательностями одного типа, то лексикографическое сравнение осуществляется рекурсивно. Если все элементы последовательностей равны, то последовательности считаются равными. Если одна последовательность совпадает с началом другой, более короткая последовательность считается меньшей. Лексикографический порядок для строк использует численный код 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 (docs.python.org/3/library/exceptions.html#TypeError).

Примечания

[ 1] Другие языки могут возвращать измененный объект, что позволяет цепочка методов, такая как d->insert("a")->remove("b")->sort();.

[ 2] Вызов d.keys() вернет объект dictionary view. Он поддерживает такие операции, как проверка членства и итерация, но его содержание не зависит от исходного словаря - это только вид.

Создано

2015-08-28

Обновлено

2017-05-21