Stfw.RuСтруктуры данных
описываются более детально ранее изученные возможности, а также некоторые новые особенности.
🕛 11.07.2009, 13:42
Подробнее о спискахРанее мы уже говорили, что метод append() позволяет добавить элемент в конец списка:
>>> a = [66.6, 333, 333, 1, 1234.5]
>>> a.append(333)
>>> a
[66.6, 333, 333, 1, 1234.5, 333]
Однако иногда необходимо вставить элемент в начало или другую позицию списка. Это позволяет сделать метод insert - Вы указываете индекс элемента, перед которым новый элемент будет добавлен:
>>> a.insert(2, -1)
[66.6, 333, -1, 333, 1, 1234.5, 333]
Кроме того, для списка определены методы, позволяющие анализировать его содержимое: найти, в каком положении находится (первый) элемент с определенным значением (метод index), или подсчитать количество таких элементов (метод count):
>>> a.index(333)
1
>>> print a.count(333), a.count(66.6), a.count('x')
3 1 0
Метод remove() позволяет удалить из списка (первый) элемент, имеющий заданное значение:
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
Элементы списка можно отсортировать (метод sort()) и изменить порядок следования элементов на противоположный (метод reverse()):
>>> a.sort() # сортируем по возрастанию
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
>>> a.reverse()
>>> a
[1234.5, 333, 333, 66.6, 1, -1]
Более подробно эти и другие операции над списками описаны в разделе 11.2.6. Приведем лишь несколько примеров, показывающих насколько широка область их применения.
Стеки
Методы, определенные для списков, позволяют использовать список в качестве стека, где последний добавленный элемент извлекается первым (LIFO, "last-in, first-out"). Для добавления элемента в стек, используйте метод 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]
Очереди
Еще одно применение списков - очереди, где элементы извлекаются в том же порядке, в котором они добавлялись (FIFO, "first-in, first-out"). Для добавления элемента в стек, используйте метод append(), для извлечения "очередного" элемента - метод pop() с индексом 0:
>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry") # Terry добавлен в очередь
>>> queue.append("Graham") # Graham добавлен в очередь
>>> queue.pop(0)
'Eric'
>>> queue.pop(0)
'John'
>>> queue
['Michael', 'Terry', 'Graham']
Средства функционального программирования
Существуют четыре встроенные функции, которые могут быть полезны при работе с последовательностями: filter(), map(), zip() и reduce().
filter(function, sequence) возвращает последовательность (по возможности того же типа, что и sequence), состоящую из тех элементов последовательности sequence, для которых function(item) является истиной. Например, выделим простые числа из списка:
>>> def f(x):
... for y in xrange(2, x):
... if x%y==0: return 0
... return 1
...
>>> filter(f, xrange(2, 40))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
map(function, sequence [. . . ]) возвращает список значений, полученных применением функции function к элементам одной или нескольких последовательностей. Например, создадим список кубов натуральных чисел:
>>> def cube(x): return x*x*x
...
>>> map(cube, xrange(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
Функция function должна воспринимать столько аргументов, сколько последовательностей передается. Она вызывается с соответствующими элементами из каждой последовательности или None, если какая-нибудь последовательность оказалась короче других. Если function равно None, то используется функция, возвращающая свои аргументы.
Учитывая эти две особенности, мы видим, что 'map(None, list1, list2)' является удобным способом превращения пары списков в список пар:
>>> seq = xrange(8)
>>> def square(x): return x*x
...
>>> map(None, seq, map(square, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25),
(6, 36), (7, 49)]
Таким образом Вы можете перебирать элементы одновременно несколько последовательностей одинаковой длины:
>>> seq1 = ['cat', 'mouse', 'bird']
>>> seq2 = ['кот', 'мышь', 'птица']
>>> for x, y in map(None, seq1, seq2):
... print x, y
...
cat кот
mouse мышь
bird птица
Как мы уже говорили, если какая-либо последовательность оказывается короче других, функция map() дополняет ее элементами, равными None. Такое поведение не всегда желательно. Поэтому в версии 2.0 была добавлена функция zip(). zip(sequence [...]) возвращает список кортежей, каждый из которых состоит из соответствующих элементов аргументов-последовательностей. При этом длина полученной последовательности будет равна длине самой короткой последовательности среди аргументов. Например:
>>> a = (1, 2, 3, 4)
>>> b = (5, 6, 7, 8)
>>> c = (9, 10, 11)
>>> d = (12, 13)
>>> zip(a, b)
[(1, 5), (2, 6), (3, 7), (4, 8)]
>>> zip(a, d)
[(1, 12), (2, 13)]
>>> zip(a, b, c, d)
[(1, 5, 9, 12), (2, 6, 10, 13)]
Если последовательности имеют одинаковую длину, поведение функции zip() полностью аналогично поведению map() с None в качестве первого аргумента. Кроме того, в этом случае действие функций zip() и map() обратимо:
>>> a = (1, 2, 3)
>>> b = (4, 5, 6)
>>> x = zip(a, b)
>>> y = zip(*x) # или apply(zip, x)
>>> z = zip(*y) # или apply(zip, y)
>>> x
[(1, 4), (2, 5), (3, 6)]
>>> y
[(1, 2, 3), (4, 5, 6)]
>>> z
[(1, 4), (2, 5), (3, 6)]
>>> x == z
1
reduce(function, sequence [, initial]) возвращает значение, полученное путем последовательного применения бинарной функции function сначала к первым двум элементам последовательности sequence, затем к результату и следующему элементу и т. д. Например, вычислим сумму арифметической последовательности:
>>> def add(x, y): return x+y
...
>>> reduce(add, xrange(1, 11))
55
Если последовательность содержит единственный элемент, возвращается его значение, если же последовательность пуста, то генерируется исключение TypeError.
В качестве третьего аргумента можно указать начальное значение. В этом случае оно возвращается для пустой последовательности, и функция сначала применяется к начальному значению и первому элементу последовательности, затем к результату и следующему элементу и т. д.:
>>> def sum(seq):
... def add(x,y): return x+y
... return reduce(add, seq, 0)
...
>>> sum(xrange(1, 11))
55
>>> sum([])
0
5.3. Дополнительные возможности при конструировании списков
Начиная с версии 2.0, языка Python, существуют дополнительные возможности конструирования списков, не прибегая к средствам функционального программирования. Такие определения списков записываются с использованием в квадратных скобках выражения и следующих за ним блоков for:
>>> freshfruit = [' banana',
... ' loganberry ',
... 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> 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}]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
Элементы можно фильтровать, указав условие, записываемое с помощью ключевого слова if:
>>> [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 [x, x**2 for x in vec] ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
Если в конструкторе указано несколько блоков for, элементы второй последовательности перебираются для каждого элемента первой и т. д., то есть перебираются все комбинации:
>>> 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]
Инструкция del
Существует способ удалить не только элемент по его значению, но и элемент с определенным индексом, элементы с индексами в определенном диапазоне (ранее мы производили эту операцию путем присваивания пустого списка срезу): инструкция del:
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]
Инструкция del может быть также использована для удаления переменных:
>>> del a
После этого ссылка на переменную a будет генерировать исключение NameError, пока ей не будет присвоено другое значение. Позже мы расскажем о других применениях инструкции del.
Кортежи
Списки и строки имеют много общего, например, для них можно получить элемент по индексу или применить операцию среза. Это два примера последовательностей. Еще одним встроенным типом последовательностей является кортеж (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))
Как Вы заметили, при выводе кортежи всегда заключаются в круглые скобки, для того, чтобы вложенные кортежи воспринимались корректно. Вводить их можно как в скобках, так и без них, хотя в некоторых случаях скобки необходимы (если кортеж является частью более сложного выражения).
Кортежи имеют множество применений: пара координат (x, y), запись в базе данных и т. д. Кортежи, как и строки, не допускают изменений: нельзя присвоить значение элементу кортежа (тем не менее, Вы можете имитировать такую операцию с помощью срезов и последующего объединения).
Для того, чтобы сконструировать пустые или содержащие один элемент кортежи, приходится идти на синтаксические ухищрения. Пустой кортеж создается с помощью пустой пары скобок, кортеж с одним элементом - с помощью значения и следующей за ним запятой (не достаточно заключить значение в скобки). Несколько неприятно, но эффективно. Например:
>>> empty = ()
>>> # обратите внимание на завершающую запятую
... singleton = 'hello',
>>> len(empty)
0
>>> empty
()
>>> len(singleton)
1
>>> singleton
('hello',)
Инструкция t = 12345, 54321, 'hello!' - пример упаковки в кортеж: значения 12345, 54321 и 'hello!' упаковываются вместе в один кортеж. Также возможна обратная операция - распаковки кортежа:
>>> x, y, z = t
Распаковка кортежа требует, чтобы слева стояло столько переменных, сколько элементов в кортеже. Следует заметить, что множественное присваивание является всего лишь комбинацией упаковки и распаковки кортежа. Иногда может оказаться полезной распаковка списка:
>>> a = ['spam', 'eggs', 100, 1234]
>>> a1, a2, a3, a4 = a
Как мы уже говорили, кортежи, как и строки, не допускают изменений. Однако, в отличие от строк, кортежи могут содержать объекты, которые можно изменить с помощью методов:
>>> t = 1, ['foo', 'bar']
>>> t
(1, ['foo', 'bar'])
>>> t[1] = [] # Ошибка
Traceback (innermost last): File "<stdin>", line 1, in ?
TypeError: object doesn't support item assignment
>>> t[1].append('baz') # Правильно
>>> t
(1, ['foo', 'bar', 'baz'])
СловариЕще один встроенный в Python тип данных - словарь (dictionary) - часто называют ассоциативным массивом. В отличие от последовательностей, индексируемых диапазоном чисел, доступ к элементам словаря производится по ключу, который может быть любого типа, не допускающего изменений [На самом деле, в качестве ключа может служить любой объект (в том числе допускающий изменения), для которого определена функция hash(). Правило относится, скорее, к стандартным типам данных языка.] - строки и числа всегда могут быть ключами. Кортежи могут использоваться в качестве ключа, если они содержат строки, числа и кортежи, удовлетворяющие этому правилу. Нельзя использовать списки, так как их можно изменить (не создавая нового объекта-списка) с помощью, например, метода append().
Лучше всего представлять словарь как неупорядоченное множество пар ключ: значение, с требованием уникальности ключей в пределах одного словаря. Пара фигурных скобок {} создает пустой словарь. Помещая список пар key: value, разделенных запятыми, в фигурные скобки, Вы задаете начальное содержимое словаря. В таком же виде записывается словарь при выводе.
Основные операции над словарем - сохранение с заданным ключом и извлечение по нему значения. Также можно удалить пару key: value с помощью инструкции del. Если Вы сохраняете значение с ключом, который уже используется, то старое значение забывается. При попытке извлечь значение с несуществующим ключом, генерируется исключение KeyError.
Метод keys() для словаря возвращает список всех используемых ключей в произвольном порядке (если Вы хотите, чтобы список был отсортирован, просто примените к нему метод sort()). Чтобы определить, используется ли определенный ключ - используйте метод has_key().
Приведем простой пример использования словаря в качестве телефонного справочника:
>>> 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']
>>> tel.has_key('guido')
1
Подробнее об условиях
Помимо описанных ранее операторов сравнения, существует еще несколько условных операторов.
Операторы in и not in проверяют, есть указанное значение в последовательности. Операторы is и is not определяют, ссылаются ли две переменные на один и тот же объект. Все приведенные здесь операторы имеют одинаковый приоритет, который ниже, чем у арифметических операторов.
Логические выражения могут быть сцеплены: например, 'a < b == c' проверяет, меньше ли a чем b и равны ли b и c.
Логические выражения можно группировать с помощью логических операторов and и or, а также результат можно инвертировать оператором not. Все логические операторы имеют меньший приоритет, чем операторы сравнения. Среди логических операторов, not имеет наибольший приоритет и or - наименьший. Таким образом, 'A or not B and C' эквивалентно 'A or ((not B) or C)'. Безусловно, можно использовать скобки для определения порядка вычисления.
Аргументы логических операторов and и or вычисляются справа налево до тех пор, пока результат не будет определен. Например, если выражения A и C истинны, но B ложно, в 'A and B and C' выражение C вычисляться не будет. Вообще говоря, возвращаемое значение операторов and и or является не логическим, а равно значению последнего вычисленного аргумента.
Можно присвоить результат сравнения или логического выражения переменной:
>>> string1, string2, string3 = \
... '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'
Обратите внимание, что, в отличие от C, присваивание не может находиться внутри выражения. Такое ограничение позволяет избежать ошибок, типичных для программ на C: использование = вместо ==.
Сравнение последовательностей
Объекты-последовательности можно сравнивать с другими объектами того же типа. Сравнение производится лексикографически: сначала сравниваются первые элементы последовательностей, и, если они отличаются, то результат их сравнения определяет результат; если они равны, сравниваются следующие элементы и т. д., пока не будет определен результат или одна из последовательностей не будет исчерпана. Если два элемента сами являются последовательностями одного типа, то лексикографическое сравнение выполняется рекурсивно. Если все элементы двух последовательностей в результате сравнения оказываются равными, то последовательности считаются равными. Если одна из последовательностей является началом другой, то меньшей считается последовательность с меньшим количеством элементов. Лексикографический порядок строк определяется порядком следования 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)
Заметим, что сравнение объектов различного типа допустимо. Результат будет вполне определенным, однако не следует на него полагаться - правила сравнения объектов различного типа могут измениться в следующих версиях языка. Числа сравниваются в соответствии с их значениями, так 0 равен 0.0, и т. д.