Глава 5

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

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

5.1 Подробнее о списках

Ранее мы уже говорили, что метод 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)

>>> print a.count(333), a.count(66.6), a.count(x)

Метод remove() позволяет удалить из списка (первый) элемент, имеющий заданное значение:

>>> a.remove(333) >>> a

[66.6, -1, 333, 1, 1234.5, 333]

5.1.1 Стеки

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

5.1.2 Очереди

Еще одно применение списков - очереди, где элементы извлекаются в том же порядке, в котором они добавлялись (FIFO, "first-in, first-out"). Для добавления элемента в стек, используйте метод append(), для извлечения "очередного" элемента - метод pop() с индексом 0 :

Элементы списка можно отсортировать (метод sort() ) и изменить порядок следования элементов на противоположный (метод reverse() ):

>>> a.sort() # сортируем по возрастанию

>>> a

[-1, 1, 66.6, 333, 333, 1234.5] >>> a.reverseO >>> a

[1234.5, 333, 333, 66.6, 1, -1]

Более подробно эти и другие операции над списками описаны в разделе 11.2.6. Приведем лишь несколько примеров, показывающих насколько широка область их применения.

5.2 Средства функционального программирования

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

>>> queue = ["Eric", "John", "Michael"]

>>> queue.append("Terry") # Terry добавлен в очередь >>> queue.append("Graham") # Graham добавлен в очередь >>> queue.pop(0) Eric

>>> queue.pop(0) John

>>> queue

[Michael, Terry, Graham]