§10. Методы класса list. Обработка исключений. Сортировка. Cтек, дек и очередь

Методы класса list

Класс изменяемой коллекции list обладает большим количеством методов (функций класса) позволяющих быстро и эффективно решать сложные задачи, которые часто возникают при работе с массивами: поиск, сортировка, вставка, удаление и проч. Методы, которые не изменяют исходной последовательности являются общими и для неизменяемых коллекций.

Методы List
Метод Описание
list.append(x) Добавляет элемент в конец списка. Эквивалентно a[len(a):] = [x]
list.extend(iterable) Расширяет список, добавляя все элементы из коллекции Iterable. Эквивалентно a[len(a):] = iterable
list.insert(i, x) Вставляет элемент в заданной позиции. Первый аргумент является индексом элемента перед которым осуществляется вставка
list.remove(x) Удаляет из списка первый элемент, значение которого равно х. Возвращается ошибка, если такой элемент не будет найден
list.pop([i]) Удаляет элемент в данной позиции i и возвращает его. Если не указан индекс, a.pop() удаляет и возвращает последний элемент из списка. (Квадратные скобки означают, что параметр является необязательным)
list.clear() Удаляет из списка все его элементы. Эквивалентно del a[:]
list.index(x[, start[, end]]) Возвращает позицию первого вхождения элемента равного x. Необязательные аргументы: start, end – поиск элемента в срезе. В любом случае, отсчет идет от начала (с нулевого индекса) списка
list.count(x) Возвращает количество вхождений в списке элемента равного x
list.sort(key=None, reverse=False) Сортировка списка (подробнее см. ниже)
list.reverse() Реверс элементов списка (расположение элементов меняется на обратный порядок)
list.copy() Возвращает неполную копию списка. Эквивалентно a[:]

Программа 10.1

from random import randint, seed
seed()
L = []
for j in range(20):
    L.append(randint(10, 99))
    print(L[j], end=' ')
L.sort()
print()
for it in L:
    print(it, end=' ')
L.reverse()
print()
for it in L:
    print(it, end=' ')
print()
print(L.index(71, 5, 15))
29 34 58 25 69 39 26 34 52 63 62 22 84 28 40 99 73 51 11 75 
11 22 25 26 28 29 34 34 39 40 51 52 58 62 63 69 73 75 84 99 
99 84 75 73 69 63 62 58 52 51 40 39 34 34 29 28 26 25 22 11 
Traceback (most recent call last):
  File "/home/andrew/workspace_2017_18/class_py_2018/class_9/lesson-9-10-1.py", line 16, in 
    print(L.index(71, 5, 15))
ValueError: 71 is not in list

Обработка исключительных ситуаций

В программе 10.1, при выполнении последней задачи (поиска элемента в списке), программа завершила свою работу выводом сообщения об ошибке. Такой вывод вряд ли устроит разработчика программы. В python для перехвата и обработки вывода об ошибке и иных исключительных ситуаций используется инструкция try-except-else-finally. Синтаксис обработчика исключений следующий:

try:
    # Здесь располагается код, который может вызвать исключение
    [raise Exception("message")] 
    # Инструкция raise возбуждает исключение
    # Exception, это один из стандартных типов исключения, может 
    # использоваться любой другой, в том числе пользовательский
except (Тип исключения1, Тип исключения2, ...) [as Переменная]:
    # Код в блоке выполняется, если тип исключения совпадает 
    # с одним из типов (Тип исключения1, Тип исключения2, ...)
    # или является наследником одного из этих типов. 
    # Полученное исключение доступно в необязательной Переменной.
[except (Тип исключения3, Тип исключения4, ...):]
    # Количество блоков except не ограничено
    [raise]  
    # Сгенерировать исключение "поверх" полученного; 
    # без параметров - повторно сгенерировать полученное
[except:]
    # Будет выполнено при любом исключении, 
    # не обработанном типизированными блоками except
[else:]
    # Выполняется код блока, если не было перехвачено исключений.
[finally:]
    # Будет исполнено в любом случае, после соответствующего
    # блока except или else

Типов ошибок довольно много. Познакомиться с ними можно на страницах документации python. Чаще всего, при работе с методами list, возникают ошибки работы с индексами. Тип такого исключения ValueError. Оно возбуждается, когда встроенная операция или функция получает аргумент, который имеет правильный тип, но несоответствующее значение, или ситуация не описывается более точным исключением таким, как IndexError.
Составим программу в которой такие исключительные ситуации будут учитываться.
Дан массив удалить из этого массива элементы со значениями, которые пользователь вводит с клавиатуры. Вывести сообщения об успешности удаления или о том, что такие элементы не найдены.
Программа 10.2

from random import randint, seed
seed()
L = []
for j in range(20):
    L.append(randint(10, 99))
    print(L[j], end=' ')
print()
while True:
    N = int(input('Введите значение элемента '
                  'для удаления или 0 для выхода\nN = '))
    if not N: 
        print('Вы вышли из программы')
        break
    try:
        x = L.index(N)
    except ValueError:
        print('Такого элемента в массиве не существует!')
    else:
        L.remove(N)
        print('Элемент в позиции', x, 'успешно удален!')
    finally:
        for it in L:
            print(it, end=' ')
        print()
50 58 13 41 53 65 27 29 73 52 31 13 64 18 97 42 95 24 37 60 
Введите значение элемента для удаления или 0 для выхода
N = 43
Такого элемента в массиве не существует!
50 58 13 41 53 65 27 29 73 52 31 13 64 18 97 42 95 24 37 60 
Введите значение элемента для удаления или 0 для выхода
N = 65
Элемент в позиции 5 успешно удален!
50 58 13 41 53 27 29 73 52 31 13 64 18 97 42 95 24 37 60 
Введите значение элемента для удаления или 0 для выхода
N = 0
Вы вышли из программы

Сортировка списка

Чтобы упорядочить элементы массива по возрастанию (по неубыванию – для массива в котором есть равные элементы) или по убыванию (по невозрастанию – для массива в котором есть равные элементы) необходимо использовать один из существующих алгоритмов. Самый простой алгоритм – это алгоритм линейной сортировки (или, подобный ему, алгоритм пузырьковой сортировки). Составим программу для сортировки массива этим алгоритмом.
Идея алгоритма заключается в следующем. Допустим, массив сортируется по возрастанию. Будем использовать структуру вложенных циклов. Во внешнем цикле поочередно берутся элементы массива, которые во вложенном цикле проверяются с остальными. Если текущий элемент меньше проверяемого элемента, то они меняются местами. Произведем замер производительности алгоритма с помощью модуля timeit. Разница последовательных вызовов таймера timeit.default_timer() показывает прошедшее время в секундах.
Для наглядности производится замер производительности метода списка sort().
Программа 10.3

import timeit
from random import randint, seed
seed()
L = []
for N in range(100, 10000, 1500):
    for j in range(N):
        L.append(randint(10, 99))
    B = list(L)
    a = timeit.default_timer()
    for k in range(N):
        for m in range(N):
            if L[k] < L[m]:
                L[k], L[m] = L[m], L[k]
    print(N)
    print(timeit.default_timer()-a)
    a = timeit.default_timer()
    B.sort()
    print(timeit.default_timer()-a)
    print()
100
0.003563623999070842
2.2972999431658536e-05

1600
0.7252020140003879
0.0004654750009649433
...
7600
15.674677310002153
0.005247565000900067

9100
22.505065210003522
0.007381265000731219

Замер производительности наглядно демонстрирует на сколько алгоритм линейной сортировки не эффективен! Последний замер пришлось ожидать почти пол-минуты! В большинстве своем быстрые алгоритмы сортировки не являются тривиальными. Более сложные алгоритмы мы рассмотрим с вами позднее.
Помимо метода списка list.sort() существует встроенная функция sorted(). Синтаксис этих функций:

sorted(iterable, key=None, reverse=False)
list.sort(key=None, reverse=False)

sorted() отличается от метода списка тем, что принимает в качестве аргумента коллекцию, а возвращает копию отсотированного массива, в то время как sort() сортирует взятый список на месте, в памяти. sort() определен только как метод списков, sorted() можно использовать для любой коллекции. Обе функции имеют необязательный аргумент key – ключ сортировки. Значением ключевого параметра должна быть функция, которая принимает один аргумент и возвращает ключ, используемый для сортировки целевого массива. Ниже в программе, для большей убедительности, используется список строк, который упорядочивается по длине, регистру и лексикографически, соответственно.
Программа 10.4

L = ['a', 'aa', 'aaa', 'A', 'AA', 'AAA', 'b', 'dd', 'ZZZ', 'ZZ', 'Z']
L.sort(key=len)
print(L)
L.sort(key=str.lower)
print(L)
L.sort(key=max)
print(L)
['a', 'A', 'b', 'Z', 'aa', 'AA', 'dd', 'ZZ', 'aaa', 'AAA', 'ZZZ']
['a', 'A', 'aa', 'AA', 'aaa', 'AAA', 'b', 'dd', 'Z', 'ZZ', 'ZZZ']
['A', 'AA', 'AAA', 'Z', 'ZZ', 'ZZZ', 'a', 'aa', 'aaa', 'b', 'dd']

По умолчанию сортировка выполняется по возрастанию, аргумент reverse со значением True изменит направление на обратное.

Лямбда-выражение

В качестве значения аргумента key в функциях сортировки часто используется лямбда-выражение (или просто “лямбда”). Лямбда представляет собой анонимную функцию, т. е. функцию без имени, поэтому лямбда должна использоваться там, где она определяется. Синтаксис лямбды прост:

lambda [параметры] : выражение

На использование лямбды накладываются определенные ограничения (помимо того, что такая функция может быть вызвана только в определенном месте программы). В теле такой функции нельзя использовать операцию “=”, инструкции if, while, try и for, а также return и yield, но можно использовать логическое выражение (тернарную операцию). Разработаем программу в которой одна и та же операция над элементами списка производится с помощью обычной функции и с помощью лямбды.
Программа 10.5

from random import randint, seed
seed()

def sum(x):
    return x + 2

L = [randint(10, 99) for i in range(10)]
A = list(L)

print(L)

L = [sum(i) for i in L]
print(L)

A = list(map(lambda x: x + 2, A))
print(A)
[26, 14, 77, 10, 87, 41, 75, 16, 78, 48]
[28, 16, 79, 12, 89, 43, 77, 18, 80, 50]
[28, 16, 79, 12, 89, 43, 77, 18, 80, 50]

Для изменения списка А в программе 10.5 использовалась уже известная нам встроенная функция map(), которая применяет функцию ко всем элементам списка, поэтому код с лямбдой будет значительно короче. Эта функция может работать с несколькими списками одинаковой длины.
Вернемся к разговору о применении лямбды как key-значение в функциях сортировки. Приведем пример такой задачи. Пусть нам дан неотсортированный список строк некоторых идентификаторов в формате год.месяц.день.час.минуты. Необходимо выполнить сортировку массива по значению дня, по убыванию.
Программа 10.6

L = ['2018.11.05.18.4', 
     '2018.02.12.05.12', 
     '2018.12.10.14.33', 
     '2018.03.20.15.15',
     '2018.06.12.12.10',
     '2018.06.12.45.50',
     '2018.01.01.01.01',
     '2018.05.14.17.00']
L.sort(key=lambda x: int(x.split('.')[2]), reverse=True)
for j in L:
    print(j, sep='\n')
2018.03.20.15.15
2018.05.14.17.00
2018.02.12.05.12
2018.06.12.12.10
2018.06.12.45.50
2018.12.10.14.33
2018.11.05.18.4
2018.01.01.01.01

Выражение x.split('.')[2] означает, что мы берем элемент списка (строку) и разбиваем её на элементы по символу разделителю с помощью, уже известной нам, функции split(). Как известно, эта функция возвращает список. В этом списке нам нужен 2-ой элемент, который мы берем операцией взятия по индексу. Наконец, функция преобразования int вернет нам целое число, которое и берется за основу для сортировки строк списка.
Несложно заметить, что лямбды могут сделать код программы по работе с элементами массива очень лаконичными. Приведем ещё один пример задачи. Дан массив. Каждый элемент массива с четным значением увеличить в два раза, а нечетные элементы обнулить.
Программа 10.7

from random import randint, seed
seed()

L = [randint(10, 99) for i in range(20)]
print(L)

L = list(map(lambda x : 0 if x % 2 else x * 2, L))
print(L)
[19, 25, 39, 80, 81, 97, 94, 95, 99, 84, 92, 44, 43, 70, 34, 54, 93, 98, 72, 59]
[0, 0, 0, 160, 0, 0, 188, 0, 0, 168, 184, 88, 0, 140, 68, 108, 0, 196, 144, 0]

С лямбдами используются полезные функции при работе с массивами, такие как filter() и reduce(). Они подобны функции map, тоже принимают в качестве одного из аргументов другую функцию.
Назначение filter() – фильтровать значения последовательности. В результате мы получаем новый список в котором имеются только те значения, для которых функция возвращает значение True.
Функция reduce() из модуля functools организует цепочечные вычисления в списке. Приведем пример программы, в которой используются эти функции. Дан массив получить новый массив в который войдут элементы кратные 3, но не кратные 5 из исходного массива. Получить произведение элементов созданного массива.
Программа 10.8

from random import randint, seed
from functools import reduce
seed()
A = [randint(10, 99) for i in range(15)]
print('A =', A, '\n')

B = list(filter(lambda x: not x % 3 and x % 5, A))
print('B =', B, '\n')

p = reduce(lambda res, x: res*x, B, 1)
print('p =', p)
A = [52, 89, 93, 22, 77, 83, 96, 23, 71, 24, 68, 27, 39, 13, 81] 

B = [93, 96, 24, 27, 39, 81] 

p = 18275901696

Структуры данных stack (стек), deque (дек) и queue (очередь)

Существуют структуры данных, которые часто используются в решении некоторого типа задач связанных с графами. Для хранения положения и/или значения узла графа (или дерева) используются массивы. Структура данных стек легко смоделировать на основе list, который имеет для этого подходящие методы и реализацию. Структура данных Дек реализована в модуле collections в виде класса collections.deque. С помощью дека можно моделировать очередь.

stack

Стек – это структура данных в которой элементы добавляются и удаляются в вершине стека. Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Обычно такую структуру представляют как стопка тарелок: доступ ко второй (сверху) тарелке можно получить только после того, как будет взята первая тарелка.

Для вставки элемента в вершине применяется метод append(), а для извлечения – метод pop() (без аргумента). Поскольку элементы вставляются и извлекаются в конце массива, то для списков такие операции производятся очень эффективно.
Рассмотрим одну из задач, которую легко можно решить с помощью стека. В постфиксной записи арифметического выражения операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операций для своего чтения.
Дано выражение в постфиксой записи, содержащее однозначные числа, операции +, , *. Вычислите значение выражения, записанного в постфиксной форме (называемой также обратной польской записью). Числа и символы разделяются одним пробелом.
Программа 10.9

S = input('S => ').split()
stack = []
for r in S:
    if r == '*':
        a = stack.pop()
        b = stack.pop()
        stack.append(a * b)
    elif r == '+':
        a = stack.pop()
        b = stack.pop()
        stack.append(a + b)
    elif r == '-':
        a = stack.pop()
        b = stack.pop()
        stack.append(a - b)
    else:
        stack.append(int(r))
print(stack.pop())
S => 5 5 4 + 10 * +
95
queue

Очередь — структура данных в которой добавление элемента возможно лишь в конец очереди, а выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется. Массив элементов, организован по принципу FIFO (англ. First In — First Out, «первый пришёл — первый вышел»).
Для реализации очереди списки не подходят, так как удаление элемента в начале списка очень дорогостоящая операция (по смещению всех элементов массива влево). Для реализации такой задачи используются деки. В python деки реализованы в виде класса входящего в модуль collections. Deque – является обобщением стека, дека и очереди (включая двустороннюю очередь). Предыдущую задачу можно было бы решить и с помощью дека. Деки в python реализованы очень эффективно.

Конструктор дека выглядит следующим образом:

collections.deque([iterable[, maxlen]])

Ниже перечислены методы этого класса.

Методы класса Deque
Метод Описание
append(x) Добавляет элемент справа
appendleft(x) Добавляет элемент слева
clear() Удаляет все элементы и обнуляет длину
copy() Создаёт неполную копию дека
count(x) Подсчитывает количество элементов равных х
extend(iterable) Добавление коллекции справа
extendleft(iterable) Добавление коллекции слева
index(x[, start[, stop]]) Возвращает позицию первого вхождения элемента равного x. Возбуждает исключение ValueError, если он не найден.
insert(i, x) Вставка x в позицию i. Если вставка невозможна по причине MAXLEN, возбуждается исключение IndexError.
pop() Удаляет и возвращает элемент с правой стороны двусторонней очереди. Если нет ни одного элемента, то возбуждается исключение IndexError
popleft() Тоже, слева
remove(value) Удаляет первое вхождение элемента со значением value. Если не найден, то возбуждается ValueError
reverse() Реверс элементов дека на месте, а затем возвращается None
rotate(n=1) Поворот Deque на n шагов вправо. Если n является отрицательным, то поворот влево. Если Deque не пустой, то вращение на один шаг вправо эквивалентно d.appendleft(d.pop()), а вращение на один шаг влево эквивалентно d.append(d.popleft())
maxlen Максимальный размер дека или None, если неограничен.

Очередь нашла свое применение в алгоритмах так называемого обхода дерева (или графа) в ширину (англ. breadth-first search, BFS). Не вдаваясь глубоко в теорию графов, рассмотрим пример такой задачи на основе задачи ЕГЭ.
Вася, решая задачи формата ЕГЭ, дошел до задачи об исполнителе:
«У исполнителя Калькулятор две команды:

  1. прибавь 3
  2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4».
graf
Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел a и b построить программу наименьшей длины получения числа b из числа a. Напишите программу, которая по заданным числам a и b вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из a число b (при условии, что команды используются теже).
Программа 10.10

from collections import deque
a = int(input("Корень => "))
b = int(input("Искомая вершина => "))
queue = deque()
f = False
i = 0
#Помещаем исходную вершину в очередь
queue.append(a)
#Пока очередь не пуста
while len(queue) != 0:
    # Берем элемент из очереди (посещаем вершину)
    p = queue.popleft()
    # Определяем потомков и добавляем их в очередь
    queue.append(p * 4)
    queue.append(p + 3)
    i += 2
    # Если найдена вершина с необходимым значением - выходим
    if p * 4 == b or p + 3 == b:
        f = True
        break
        # Также выходим, если достигли лимита
    if len(queue) > 1000:
        break;

j = 0;
# Определяем количество команд
if f:
    while i > 1:
        j+=1
        i //= 2
    print("Наименьшее число команд =", j)
else:
    print("Алгоритм не найден")

Корень => 3
Искомая вершина => 57
Наименьшее число команд = 5
Ссылки
  1. Функциональное программирование на Python
  2. Синтаксис Python: lambda-функции
  3. functools — Higher-order functions and operations on callable objects
  4. Функции map и zip и lambda. Python
  5. Примеры программ на языке Python
Print Friendly, PDF & Email

Comments are closed