Структуры Данных
Эта глава описывает подробнее некоторые вещи, которые вы уже изучили, а также раскрывает некоторые новые темы.
Подробнее о списках
У типа данных список также имеются еще несколько методов. Ниже приведены все методы объекта типа список:
-
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 в сигнатуре метода означают, что параметр необязателен, а не необходимость набора квадратных скобок в этой позиции. Вы часто будете встречать такую нотацию в Справочнике по библиотеке.)
-
list.clear() Удалить все элементы из списка. Эквивалентно
del a[:].
-
list.index(x) Вернуть индекс первого найденного в списке элемента, значение которого равно x. Если элемент не найден, генерируется ошибка.
-
list.count(x) Вернуть значение сколько раз, x встречается в списке.
-
list.sort(key=None, reverse=False) Сортировать элементы списка, на месте (аргументы могут быть использованы для настройки сортировки, см. sorted() для их объяснения).
-
list.reverse() Обратить порядок элементов списка, на месте.
-
list.copy() Возвратить неглубокую копию списка. Эквивалентно
a[:].
An example that uses most of the list methods:
>>> 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. [1] Это принцип разработки для всех мутабельных структур данных в Python.
Использование списка в качестве стека
Методы списков позволяют легко использовать список в качестве стека,
где последний добавленный элемент становится первым полученным («первый
вошёл — последний вышел»). Чтобы положить элемент на вершину стека,
используйте метод 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]
Использование списка в качестве очереди
Вы можете без труда использовать список также и в качестве очереди, где первый добавленный элемент оказывается первым полученным («первый вошёл — первый вышел»); однако списки не эффективны для этой цели. Хотя добавления и извлечения из конца списка быстры, делать вставки и извлечения с начала списка медленно (потому что все другие элементы придется сдвинуть на один).
Чтобы реализовать очередь, используйте 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'])
Генераторы списков (List Comprehensions)
Генераторы списков — легкий способ создать список на основе последовательности. В большинстве случаев он применяется для создания списков, в которых каждый элемент является результатом некой операции, произведённой над каждым членом последовательности, или для создания выборок из тех элементов, которые удовлетворяют определённому условию.
Например, предположим, что мы хотим создать список квадратов чисел, например:
>>> 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, затем ноль или более условий for или 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]
>>> # 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 ?
[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']
Вложенные генераторы списков
Первое выражение в генераторе списков может быть любым произвольным выражением, включая другой генератор списков.
Рассмотрим следующий пример матрицы 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, что следует за ним, так что этот пример эквивалентен:
>>> 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]]
В реальном мире вам следует предпочесть встроенные функции сложным потокам инструкций. Функция zip() сделает прекрасную работу для этого случая:
>>> list(zip(*matrix)) [(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]
См. Распаковка списков параметров подробнее о звездочке в этой строке.
Оператор 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.
Кортежи и последовательности
Мы видели, что списки и строки поддерживают много привычных свойств, таких как индексирование и операция получения срезов. Они являются двумя примерами типов данных последовательность (sequence) (см. Последовательные типы — list, tuple, range). Поскольку Python — развивающийся язык, со временем могут быть добавлены другие последовательные типы данных. Также существует другой стандартный последовательный тип данных: tuple.
Кортеж состоит из некоторого числа значений разделённых запятыми, например:
>>> 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). Списки — мутабельны, и их элементы обычно однородны и доступны итерированием по списку.
Определённая проблема состоит в конструировании кортежей, состоящих из нуля или одного элемента: в синтаксисе языка есть дополнительные хитрости, позволяющие достигнуть этого. Пустые кортежи формируются за счёт пустой пары скобок; кортеж с одним элементом конструируется за счёт запятой, следующей за числом (единственное значение не обязательно заключать в скобки). Необычно, но эффективно. Например:
>>> empty = ()
>>> singleton = 'hello', # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)
Выражение t = 12345, 54321, 'hello!' является примером упаковки кортежей (tuple packing): значения 12345, 54321 и 'hello!' упаковываются в кортеж вместе.
Обратная операция также возможна:
>>> x, y, z = t
Такое действие называется, довольно удачно, распаковкой последовательности (sequence unpacking) и работает для любой последовательности на правой стороне. Pаспаковка последовательности требует, чтобы было столько же переменных слева от знака равно, сколько элементов в последовательности. Обратите внимание, что множественное присваивание на самом деле просто комбинация упаковки кортежа и распаковки последовательности.
Множества (Sets)
Python имеет также тип данных
Для создания множеств могут быть использованы фигурные скобки или функция set(). Заметьте: для создания пустого множества нужно использовать set(), а не {}: в последнем случае создаётся пустой словарь (dictionary) — тип данных, который мы обсудим в следующем разделе.
Вот краткая демонстрация:
>>> 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 either a or b
{'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'}
Словари
Другой полезный встроенный в Python тип данных — это словарь (dictionary) (см. Отображаемые типы — dict). Словари иногда встречаются в других языках в виде «ассоциативных
записей» или «ассоциативных массивов». В отличие от последовательностей,
которые индексируются по диапазону чисел, словари индексируются по ключам (keys),
которые, в свою очередь, могут быть любого неизменяемого типа; строки и
числа всегда могут быть ключами. Кортежи могут быть ключами только если
они составлены из строк, чисел или кортежей; если кортеж содержит
какой-либо изменяемый объект, явно или неявно, то он не может быть
использован в качестве ключа.
Вы не можете использовать списки в роли
ключей, поскольку списки могут быть изменены на месте присваиванием по
индексу, присваиванием по срезу или такими методами как append() и extend().
Лучше всего воспринимать словарь как неупорядоченный набор пар ключ: значение с требованием, чтобы ключи были уникальны (в пределах одного словаря). Пара скобок создает пустой словарь: {}. Указывая разделённый запятыми список пар
Главные операции над словарём — это сохранение значения с
каким-либо ключом и извлечение значения по указанному ключу. Также
возможно удалить пару ключ:значение используя оператор del. Если вы сохраняете значение используя ключ, который уже встречается в
словаре — старое значение, ассоциированное с этим ключом,
стирается. Извлечение значения по несуществующему ключу вызывает ошибку.
Выполнение конструкции list(d.keys()) с объектом словаря
возвращает список всех ключей, использующихся в словаре, в случайном
порядке (если вы хотите отсортировать его, вместо этого просто используйте sorted(d.keys())). [2] Чтобы проверить, содержит ли словарь определённый ключ, используйте ключевое слово 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([('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}
Организация циклов
При организации перебора элементов из словаря ключ и соответствующее
ему значение могут быть получены одновременно посредством метода 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]
Подробнее об условиях
Условия в операторах if и while могут содержать любые операции, а не только операции сравнения.
Операции сравнения 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 operators):
их операнды вычисляются слева направо и вычисление заканчивается как
только результат становится определён (очевиден). Например, если 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: указания оператора присваивания (=) в выражении, вместо предполагавшегося сравнения (==).
Сравнение последовательностей и других типов
Объекты последовательностей можно сравнивать с другими объектами с тем же типом последовательности. Сравнение использует лексикографический порядок: сравниваются первые два элемента, и если они различны — результат сравнения определён; если они равны, сравниваются следующие два элемента и так далее до тех пор, пока одна из последовательностей не будет исчерпана. Если сравниваемые два элемента сами являются последовательностями одного типа, лексикографическое сравнение происходит в них рекурсивно. Если все элементы обеих последовательностей оказались равны, последовательности считаются равными. Если одна последовательность оказывается стартовой последовательностью другой, более короткая последовательность считается меньшей. Лексикографическое упорядочивание строк использует порядок в таблице 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)
Обратите внимание, что сравнение объектов различных типов операциями < или >
позволено, если объекты имеют соответствующие методы сравнения. Например, смешанные числовые типы сравниваются в соответствии с их
численными значениями, так что
Сноски
| [1] | Другие языки могут вернуть измененный объект, который допускает сцепление методов, таких как d->insert(“a”)->remove(“b”)->sort();. |
| [2] | Вызо d.keys() вернет объект вид словаря. Он поддерживает такие операции, как проверка членства и итерирование, но его содержимое не является независимым от оригинального словаря — это только вид. |