Python, списки

В Python-е списки один из самых используемых типов данных. Они отдаленно напоминают массивы в Java или C — это тоже упорядоченный список объектов. В частности, аналогию можно провести с массивом в Java — с классом Vector, который способен содержать произвольные объекты. Питоновские списки можно также сравнить с массивами на языке Perl. По своей мощи, гибкости, простоте использования список превосходит аналоги из других языков программирования.
В этой заметке будут рассмотрены следующие темы.

1. Что такое список.
2. Операции со списками.
3. Встроенные функции.
4. Стек и очередь.
5. Кортежи (Tuple).
6. Сеты (Set).
7. Встроенные функции filter(), map(), zip(), reduce().

1. Что такое список
Для группировки множества элементов в питоне используется список list, который может быть записан как индексированная последовательность значений, разделенных запятыми, заключенная в квадратные скобки. Списки имеют произвольную вложенность, т.е. могут включать в себя любые вложенные списки. Физически список представляет собой массив указателей (адресов) на его элементы. С точки зрения производительности (performance) списки имеют следующие особенности.

1. Время доступа к элементу есть величина постоянная и не зависит от размера списка.
2. Время на добавление одного элемента в конец списка есть величина постоянная.
3. Время на вставку зависит от того, сколько элементов находится справа от него, т.е. чем ближе элемент к концу списка, тем быстрее идет его вставка.
4. Удаление элемента происходит так же, как и в пункте 3.
5. Время, необходимое на реверс списка, пропорционально его размеру — O(n).
6. Время, необходимое на сортировку, зависит логарифмически от размера списка.

Элементы списка не обязательно должны быть одного типа. Приведем вариант статического определения списка:

>>> lst = ['spam', 'drums', 100, 1234]

Как и для строк, для списков нумерация индексов начинается с нуля. Для списка можно получить срез, объединить несколько списков и так далее:

>>> lst[1:3] ['drums', 100]

Можно менять как отдельные элементы списка, так и диапазон:

>>> lst[3] = 'piano' >>> lst[0:2] = [1,2] >>> lst [1, 2, 100, 'piano']

Вставка:

>>> lst[1:1] = ['guitar','microphone'] >>> lst [1, 'guitar', 'microphone', 2, 100, 'piano']

Можно сделать выборку из списка с определенной частотой:

>>> numbers = [1,2,3,4,5,6,7,8,9,0] >>> numbers[::4] [1, 5, 9]

2. Операции со списками
К операциям мы относим:

• копирование списка;
• сложение и умножение списков;
• итерацию — проход в цикле по элементам списка;
• конструктор списков (list comprehension);
• распаковку списка — sequence unpacking.

Создание копии списка.

1. L1 = L2[:] — создание второй копии списка. Здесь создается вторая копия обьекта.
2. L1 = list(L2) — тоже создание второй копии списка.
3. L1 = L2 — создание второй ссылки, а не копии. 3-й вариант показывает, что создаются две ссылки на один и тот же обьект, а не две копии.

Сложение или конкатенация списков:

L1 + L2

Умножение, или повтор списков:

L1 * 2

Итерацию списков в питоне можно делать несколькими различными способами:

• простая итерация списка:

  for x in L:

• сортированная итерация:

  for x in sorted(L):

• уникальная итерация:

  for x in set(L):

• итерация в обратном порядке:

  for x in reversed(L):

• исключающая итерация — например, вывести элементы 1-го списка, которых нет во 2-м списке:

  for item in set(L).difference(L2)

Для генерации списков, кроме статической формы, можно использовать конструктор списков — list comprehension — цикл внутри квадратных скобок — на примере списка квадратов первых 10 натуральных чисел:

>>> a = [ i*i for i in range(1,10)] >>> a [1, 4, 9, 16, 25, 36, 49, 64, 81]

Конструктор может быть условным — найдем квадраты четных натуральных чисел:

>>> a = [ i*i for i in range(1,10) if i % 2 == 0] >>> a [4, 16, 36, 64]

С помощью конструктора решим конкретную задачу — отсортируем слова в предложении в порядке их длительности:

words = ' to perform the task of sorting the words in a string by their length'.split() wordlens = [(len(word), word) for word in words] wordlens.sort() print ' '.join(w for (_, w) in wordlens) >>> a by in of to the the task their words length string perform sorting

Операция Sequence unpacking — присваивание списку переменных списка значений:

a, b = [1,2]

3. Встроенные функции
Списки имеют большой набор функций:

• append , extend — добавление;
• insert — вставка;
• index — найти индекс первого вхождения конкретного элемента;
• count — подсчет повторов элемента;
• remove , del — удаление элемента;
• sort — сортировка;
• reverse — реверс;
• pop — извлечение элемента;
• len — длина списка;
• max — максимальный элемент;
• min — минимальный элемент;
• оператор in — проверка элемента на вхождение.

Добавлять можно как одинарные элементы, так и набор элементов. Списки могут быть вложенными — вложенный список добавим в конец с помощью append():

>>> lst = [1, 'guitar', 'microphone', 2, 100, 'piano'] >>> lst2 = ['sintezator','drums'] >>> lst.append(lst2) >>> lst [1, 'guitar', 'microphone', 2, 100, 'piano', ['sintezator', 'drums']]

Элемент можно добавить в произвольную позицию списка с помощью метода insert:

>>> lst.insert(0,'vocal') >>> lst ['vocal', 1, 'guitar', 'microphone', 2, 100, 'piano', ['sintezator', 'drums']]

Для проверки, является ли элемент членом списка, есть оператор in:

>>> 2 in lst True >>> 10 in lst False

index() — взять элемент списка по индексу:

>>> lst.index('guitar') 2

count() — подсчет числа повторов какого-то элемента:

>>> lst.count('vocal') 1

remove() — удаление конкретного элемента:

>>> lst.remove(100) >>> lst ['vocal', 1, 'guitar', 'microphone', 2, 'piano', ['sintezator', 'drums']]

del — удаление по индексу:

del lst[1]

При удалении нужно помнить о том, что нельзя одновременно делать итерацию по списку — последствия будут непредсказуемы.
sort() — сортировка списка:

>>> lst.sort() >>> lst [1, 2, ['sintezator', 'drums'], 'guitar', 'microphone', 'piano', 'vocal']

reverse() — реверс списка:

>>> lst.reverse() >>> lst ['vocal', 'piano', 'microphone', 'guitar', ['sintezator', 'drums'], 2, 1]

pop() — извлечение элемента из списка, функция без параметра удаляет по умолчанию последний элемент списка, в качестве параметра можно поставить произвольный индекс:

>>> lst.pop() >>> lst ['vocal', 'piano', 'microphone', 'guitar', ['sintezator', 'drums'], 2]

len() — длина списка:

>>> len(lst) 6

max() — максимальный элемент списка:

>>> max(lst) 'vocal'

min() — минимальный элемент списка:

>>> min(lst) 2

extend() — аналогичен append(), добавляет последовательность элементов:

>>> lst.extend([3,4]) >>> lst ['vocal', 'piano', 'microphone', 'guitar', ['sintezator', 'drums'], 2, 3, 4]

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

>>> stack = [1,2,3,4,5] >>> stack.append(6) >>> stack.append(7) >>> stack.pop() >>> stack [1, 2, 3, 4, 5, 6]

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

>>> queue = ['rock','in','roll'] >>> queue.append('alive') >>> queue.pop(0) >>> queue ['in', 'roll', 'alive']

5. Кортежи (Tuple)
Список так же может быть неизменяемым (immutable), как и строка, в этом случае он называется кортеж (tuple). Кортеж использует меньше памяти, чем список. Кортеж вместо квадратных скобок использует круглые (хотя можно и совсем без скобок). Кортеж не допускает изменений, в него нельзя добавить новый элемент, хотя он может содержать объекты, которые можно изменить:

>>> t = 1,[2,3] >>> t (1, [2, 3]) >>> t[1] = 2 TypeError: 'tuple' object does not support item assignment >>> t[1].append(4) >>> t (1, [2, 3, 4])

Функция tuple() берет в качестве аргумента строку или список и превращает его в кортеж:

>>> tuple('abc') ('a', 'b', 'c')

6. Сеты (Set)
Сеты — неотсортированная коллекция уникальных элементов. Сеты поддерживают итерацию, добавление и удаление объектов и т.д. Индексация и срезы в сетах не поддерживаются. Сгенерировать сет можно с помощью функции:

>>> s = set('abcde') >>> s set(['a', 'c', 'b', 'e', 'd']) >>> s2 = set('aghij') >>> s2 set(['a', 'h', 'j', 'g', 'f'])

Над сетами можно выполнять разные операции, например:

• вычитание:

  >>> s3 = s - s2 >>> s3 set(['c', 'b', 'e', 'd'])

• сложение:

  >>> s3 = s | s2 >>> s3 set(['a', 'c', 'b', 'e', 'd', 'g', 'i', 'h', 'j'])

• пересечение:

  >>> s3 = s & s2 >>> s3 set(['a'])

Сеты имеют встроенные функции:
add() — добавление элемента:

>>> s.add(6) >>> s set(['a', 'c', 'b', 'e', 'd', 6])

remove() — удаление элемента:

>>> s.remove('a') >>> s set(['c', 'b', 'e', 'd', 6])

Итерация:

>>> for item in s:print (item) c b e d 6

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

>>> L = [1,2,3,4,1,2,6,7] >>> set(L) set([1, 2, 3, 4, 6, 7]) >>> L = list(set(L)) >>> L [1, 2, 3, 4, 6, 7]

Сеты можно использовать для работы с большими наборами данных:
допустим, у нас имеются базы данных программистов и менеджеров:

>>> programmers = set(['ivanov','petrov','sidorov']) >>> managers = set(['ivanov','moxov','goroxov'])

Найти тех, кто одновременно и программист, и менеджер:

>>> programmers & managers set(['ivanov'])

Найти всех программистов и менеджеров:

>>> programmers | managers set(['ivanov', 'petrov', 'sidorov', 'goroxov', 'moxov'])

Найти программистов, которые не менеджеры:

>>> programmers - managers set(['petrov', 'sidorov'])

7. Встроенные функции filter(), map(), zip(), reduce().
filter(function, sequence) возвращает последовательность, состоящую из тех элементов последовательности sequence, для которых function(item) является истиной. Функция применяется для каждого элемента последовательности. Пример: определим простые числа в диапазоне до 100:

def f(x): for y in xrange(2, x): if x%y==0: return 0 return 1 print filter(f, xrange(2, 100)) >>> [2, 3, 5, 7, 11, 13, 17, 19, 23, ... , 59, 61, 67, 71, 73, 79, 83, 89, 97]

map(function, sequence) возвращает список значений, полученных применением функции function к элементам одной или нескольких последовательностей. Например, создадим список кубов натуральных чисел от 1 до 10:

def cube(x): return x*x*x print map(cube, xrange(1, 11))

Можно перебирать элементы одновременно нескольких последовательностей одной длины:

seq1 = [1,2,3] seq2 = [11,12,13] for x, y in map(None, seq1, seq2): print x, y >>> 1 11 >>> 2 12 >>> 3 13

zip(sequence) — функция, аналогичная map() в последнем варианте, но может работать с последовательностями разной длины, возвращает список кортежей:

>>> a = (1, 2, 3, 4) >>> b = (5, 6, 7, 8) >>> zip(a, b) [(1, 5), (2, 6), (3, 7), (4, 8)]

reduce(function, sequence) возвращает значение, полученное путем последовательного применения бинарной функции function сначала к первым двум элементам последовательности sequence, затем к результату и следующему элементу и т. д. Например, вычислим сумму арифметической последовательности:

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