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(cmp=None, key=None, reverse=False)

Сортирует элементы списка на месте (аргументы можно использовать для настройки сортировки; пояснения см. в sorted()).

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]
>>> a.pop()
1234.5
>>> a
[-1, 1, 66.25, 333, 333]

Вы могли заметить, что методы insert, remove или sort, которые только изменяют список, не выводят возвращаемое значение – они возвращают значение по умолчанию None. Это принцип проектирования для всех изменяемых структур данных в Python.

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

>>> def f(x): return x % 3 == 0 or x % 5 == 0
...
>>> filter(f, range(2, 25))
[3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24]

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]

>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
...
>>> sum(range(1, 11))
55
>>> sum([])
0

>>> squares = []
>>> for x in range(10):
...     squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

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]
>>> # создать новый список с удвоенными значениями
>>> [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 <module>
    [x, x**2 for x in range(6)]
               ^
SyntaxError: invalid syntax
>>> # развернуть список с помощью спискового включения с двумя '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):
...     # следующие 3 строки реализуют вложенное списковое включение
...     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(*matrix)
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

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

Мы видели, что списки и строки имеют много общих свойств, таких как операции индексирования и нарезки. Это два примера типов данных последовательность (см. Sequence Types – str, unicode, list, tuple, bytearray, buffer, xrange). Поскольку 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))
>>> # Кортежи неизменяемы:
... 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])

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

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

Особая проблема – создание кортежей, содержащих 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']
>>> fruit = set(basket)               # создать множество без дубликатов
>>> fruit
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruit                 # быстрая проверка принадлежности
True
>>> 'crabgrass' in fruit
False

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

Аналогично списковым включениям, также поддерживаются множественные включения:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
set(['r', 'd'])

5.5. Словари¶Dictionaries

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

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

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

Метод keys() объекта-словаря возвращает список всех ключей, используемых в словаре, в произвольном порядке (если нужен отсортированный список, просто примените функцию sorted() к нему). Чтобы проверить, находится ли ключ в словаре, используйте ключевое слово 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}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> 'guido' in tel
True

Конструктор 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

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

При переборе словарей ключ и соответствующее значение можно получить одновременно с помощью метода iteritems().

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.iteritems():
...     print k, v
...
gallahad the pure
robin the brave

Иногда возникает соблазн изменить список во время его перебора; однако часто проще и безопаснее создать новый список.

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

The Boolean operators and and or are so-called short-circuit operators: their arguments are evaluated from left to right, and evaluation stops as soon as the outcome is determined. For example, if A and C are true but B is false, A and B and C does not evaluate the expression C. When used as a general value and not as a Boolean, the return value of a short-circuit operator is the last evaluated argument.

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

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

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

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

Обратите внимание, что сравнение объектов разных типов допустимо. Результат детерминирован, но произволен: типы упорядочиваются по их имени. Таким образом, список всегда меньше строки, строка всегда меньше кортежа и т.д. 1 Смешанные числовые типы сравниваются по их числовому значению, так что 0 равно 0.0 и т.д.

Сноски

1

Не следует полагаться на правила сравнения объектов разных типов; они могут измениться в будущей версии языка.