Массивы

В математике одна из распространённых моделей понятия последовательность элементов множества M — отображение из промежутка целых чисел в M. В программировании аналогичная модель называется термином массив.

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

Под термином структура данных обычно понимают некий способ хранения и организации данных, поддерживающий как минимум следующий набор операций:

1. добавление новых данных
2. извлечение (поиск) данных

Многие структуры данных также поддерживают:

3. мутацию хранящихся данных
4. получение всего набора хранящихся данных
5. удаление каких-то из хранящихся данных

Массив как структура данных

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

Такое ограничение на множество ключей связано с тем, что чаще всего поиск данных в массиве осуществляется эффективно за счёт последовательного хранения в памяти компьютера этих данных (или ссылок на них). При последовательном хранении данных единицу данных номер i можно получить, отступив от начальной единицы данных (номер a) на (i-a) «ячеек памяти» (для простоты считаем, что одна ячейка хранит одну единицу данных).

В большинстве языков программирования начальная единица данных получает номер 0. Есть небольшое количество языков программирования, в которых нумерация начинается с единицы. Также некоторые языки предоставляют самому программисту выбор конкретного промежутка возможных индексов.

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

Идеальный массив

Сейчас мы опишем «идеальный» массив — некий общий знаменатель встречающихся в реальных языках программирования массивов. Для того, чтобы придать словам некую формальную семантику, описание будем сопровождать кодом на языке python. Самым близким к «идеальному» массиву типом данных в python является «список» list. В терминах этого типа мы и дадим описание.

Основные операции с массивом: создание с одновременным заполнением данными и получение данных по номеру.

def array_new(size, gen):
    return [gen(i) for i in range(size)]
    
def array_get(array, i):
    return array[i]
    
def array_size(array):
    return len(array)

Именно эти три операции (в тех или иных разновидностях) предоставляют все языки программирования, в которых есть встроенный тип данных массив. Они связаны между собой следующим свойством (для всех i в промежутке [0,size)):

array_get(array_new(size, gen), i) == gen(i)

Также часто есть возможность мутировать массив:

def array_set(array, i, x):
    array[i] = x
    return array

Естественно, мутация должна удовлетворять свойству:

array_get(array_set(a, i, x), i) == x

Также очень желательно, чтобы два любых вызова array_get(_,i), между которыми не было вызова array_set(_,i,_) на тот же массив, давали один и тот же результат.

Поиск по массиву

Хотя массив предоставляет возможность быстро получить доступ к элементу по его номеру, зачастую это совсем не то, что нужно. Обычно нам нужно найти все элементы, удовлетворяющие какому-то свойству p. Если есть возможность как-то связать это свойство с номерами элементов, то, можно сказать, нам повезло. Обычно же верно одно из двух:

1. свойство p вообще никак не увязывается с номерами данных
2. свойство p можно увязать с номерами данных, но при этом разброс номеров данных оказывается слишком большим, и массив неэффективно расходует память

Поясним вторую ситуацию на простом примере: допустим, что мы храним слова. Каждое слово можно тривиально преобразовать в число. Например, если слово состоит из символов таблицы ASCII, подойдёт следующая процедура:

def str_to_int(s):
    result = 0
    for x in s: 
        result *= 128
        result += ord(x)
    return result

Но вот только слово foobar преобразуется в число 3534724051186, а слово banana — в число 3393524889441. Разность между этими числами равна 141199161745 — именно такой минимальный размер должен иметь массив, позволяющий хранить одновременно слова banana и foobar.

На самом деле, конечно, всё не так плохо: если не требовать инъективность отображения, преобразующего данные в числа, и хранить эти данные в массиве массивов (по номеру i хранится массив всех данных, которые преобразуются в число i) или же каким-то другим образом договориться о разрешении конфликта одинаковых номеров, то можно получить довольно эффективную схему хранения данных. Такой подход называется хэш-таблицами и, например, лежит в основе типа dict языка python.

Добавление элемента

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

def array_append(a,x):
    n = array_size(a)

    return array_new(n+1, lambda i: array_get(a,i) if i < n else x)

Основная её проблема — время работы, пропорциональное длине массива. Это приводит к тому, что время добавления n элементов становится пропорционально квадрату n (что катастрофически плохо — миллион элементов за разумное время уже не добавить).

Тем не менее, в терминах идеального массива можно определить расширяемый массив:

def earray_new():
    return [0, array_new(8, lambda x: None)]
    
def earray_get(a, i):
    if i >= a[0]: raise RuntimeError("выход за пределы массива")
    return array_get(a[1], i)

def earray_size(a):
    return a[0]

def earray_set(a, i, x):
    if i >= a[0]: raise RuntimeError("выход за пределы массива")
    array_set(a[1], i, x)
    return a

def earray_append(a, x):
    current_size = a[0]
    old_array    = a[1]
    
    if current_size < array_size(old_array):
        new_array = old_array
    else:
        new_array = array_new(current_size*2, lambda i: array_get(old_array, i) if i < current_size else None)
    
    array_set(new_array, current_size, x)
    
    a[0] = current_size+1
    a[1] = new_array
    
    return a

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

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

В заключение скажем, что расширяемый массив никак не решает проблему добавления элементов в начало (и тем более — в середину) массива. Также расширяемый массив, очевидно, ничем не лучше обычного с точки зрения поиска данных. Эффективному поиску данных при помощи массивов как раз и посвящены остальные разделы этой главы.

Бинарный поиск

Задача эффективного поиска данных, хранящихся в массиве, существенно упрощается, если данные в массиве расположены не произвольно, а упорядочены (для определённости — по неубыванию).

Простейшая разновидность бинарного поиска

Для начала поставим простую задачу: есть упорядоченный массив haystack и некий объект needle (на который единственное ограничение — должна быть возможность сравнивать его с элементами массива при помощи операций больше/меньше). Требуется, в случае, если в массиве присутствует элемент, равный needle, выдать его номер (если таких элементов несколько, можно выдать номер любого). Если такого элемента нет, выдать None.

Решение оформим в виде функции:

def search0(haystack, needle): ...

Мы знаем, что искомый элемент (если он есть) находится на отрезке массива между номерами left (включительно) и right (исключительно), где:

left = 0
right = len(haystack)

Алгоритм бинарного поиска состоит в последовательном сужении диапазона между left и right (на каждом шагу — примерно в два раза) по следующему принципу.

Пусть m = (left+right)//2 (это — примерно середина между left и right). У нас есть три ситуации:

1. haystack[m] < needle
2. haystack[m] > needle
3. haystack[m] == needle

В первой ситуации мы можем сделать вывод о том, что искомый элемент (если он есть) находится на промежутке от m+1 (включительно) до right (исключительно).

Во второй ситуации искомый элемент (опять же, при его наличии) находится между left (включительно) и m (исключительно).

В третьей ситуации мы нашли то, что искали.

Поэтому напрашивается следующий алгоритм:

def search0(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 0:
        m = (left + right) // 2
        if   haystack[m] < needle: left  = m+1
        elif haystack[m] > needle: right = m
        else: return m
    
    ## эту строчку можно и не писать (результат функции по-умолчанию равен None)
    return None

Единственный важный вопрос, связанный с этим алгоритмом: «а всегда ли заканчивается цикл?» Ответ на этот вопрос утвердительный по следующим соображениям:

1. Если right>left, то m<right.
2. При этом m+1>left.
3. Отсюда следует, что на каждом шаге разность right-left уменьшается хотя бы на 1. Поэтому всегда оставаться положительной она не может.

Теперь поймём, насколько бинарный поиск эффективнее полного перебора. Для этого нужно заметить, что разность right-left на каждом шагу уменьшается не меньше, чем в два раза. Поэтому количество шагов, требующееся для завершения работы алгоритма на массиве размера n не превосходит ни одно целое k, для которого 2**k > n.

В частности, увеличение количества данных в два раза влечёт увеличение времени работы не больше чем на время выполнения одного шага алгоритма (если оставить за рамками модели наблюдающееся на практике увеличение времени доступа к элементу массива с увеличением размера массива, то время выполнения одного шага не зависит от размера массива).

Например, массив размера миллиард элементов будет обработан бинарным поиском не дольше чем за 30 шагов. Нетрудно заметить, что 30 шагов, в каждом из которых не более двух сравнений и ещё чуть-чуть арифметики, существенно приятнее, чем миллиард сравнений при поиске полным перебором.

Поиск первого среди равных

Немного усложним задачу (как выяснится чуть позже, решение от этого усложнения только упростится). Потребуем, чтобы в случае наличия нескольких элементов, равных needle, алгоритм выдавал номер самого первого из них. Например, результат вычисления

search1([1,2,2,2,3],2)

должен быть равен 1 (первая двойка находится в массиве именно под номером 1).

Анализ, аналогичный приведённому в предыдущем разделе, говорит о том, что есть две кардинально разные ситуации:

1. haystack[m] < needle
2. haystack[m] >= needle

В первом случае искомый элемент, как и прежде, находится между m+1 и right. А вот во втором случае всё несколько хуже: искомый элемент находится между left и m+1. Хуже эта ситуация тем, что разность right-left при заменах вида:

if haystack[m] < needle: left  = m+1
else:                    right = m+1

не изменяется в случае m+1 == right. А такое наблюдается при right-left == 1 или же right-left == 2.

Есть два очевидных выхода из этой ситуации:

1. Заменить условие цикла right-left>0 на right-left>2. После отдельно обработать ситуации right-left == 1 и right-left == 2.
2. Заменить m = (left + right) // 2 на m = (left + right - 1) // 2.

Остановимся на втором решении: оно банально проще.

def search1(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:  ## тут 0 поменялся на 1
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    ## случай right - left == 1
    if right > left and haystack[left] == needle: return left

Поиск по ключу

На практике вышеизложенные задачи поиска почти не встречаются: обычно мы ищем не положение «Василия Ивановича Чапаева номер паспорта 1234 567890» в массиве людей, упорядоченном по ФИО и номеру паспорта, а номер паспорта человека по имени «Василий Иванович Чапаев».

Те данные, которые мы подаём на вход процедуре поиска, традиционно называются ключом поиска (вспомните терминологию, связанную с типом данных «словарь»). В примере с Василием Ивановичем ключом поиска является ФИО. Отображение, сопоставляющее единице данных соответствющий ей ключ, называется ключевой функцией.

Ниже приведена версия процедуры бинарного поиска, принимающая на вход ключевую функцию. При этом преполагается, что массив haystack упорядочен по ключу.

def search2(haystack, needle, keyfunc):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if keyfunc(haystack[m]) < needle: left  = m+1
        else:                             right = m+1
    
    if right > left and keyfunc(haystack[left]) == needle: return left

И заодно приведём пример использования (с тем самым Василием Ивановичем):

def name(human): return human[0]+' '+human[1]+' '+human[2]

## все совпадения с реальными людьми случайны!
people = [
    ('Чапаев',  'Василий', 'Иванович', 1234, 567890),
    ('Сидоров', 'Иван',    'Петрович', 3210, 456789),
    ('Нектов',  'Некто',   'Нектович', 1111, 111112),
]

sorted_people = sorted(people, key=name)

index = search2(sorted_people, 'Чапаев Василий Иванович', name)

print('Номер паспорта Василия Ивановича:', *sorted_people[index][3:])

Разбор ДЗ №1

Последний среди равных

Требовалось написать функцию, которая ищет последний элемент среди равных.

Вспомним, что первый среди равных ищется кодом вида

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    if right > left and haystack[left] == needle: return left

Теперь нужно аккуратно «симметрично отразить» этот код относительно середины массива. Получается вот что:

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right) // 2
        if haystack[m] > needle: right = m
        else:                    left  = m
    
    if right > left and haystack[left] == needle: return left

Ранг элемента

Нужно было написать функцию, которая ищет ранг элемента needle в упорядоченном массиве haystack — количество элементов, меньших needle.

Ранг элемента находится примерно так же, как и первый среди равных:

def search(haystack, needle):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if haystack[m] < needle: left  = m+1
        else:                    right = m+1
    
    if right > left and haystack[left] >= needle: return left
    
    return len(haystack)

Тут ровно два изменения: знак >= вместо == и возвращаемое значение функции в случае неудачного поиска.

Функция вместо массива

Нужно было найти ранг элемента в случае, когда массив моделируется функцией.

Нужно просто взять решение предыдущего упражнения и специализировать под требования задания:

def search(haystack, needle):
    f,left,right = haystack  ## именно так подаются данные на вход
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if f(m) < needle: left  = m+1
        else:             right = m+1
    
    if right > left and f(left) >= needle: return left
    
    return haystack[2]

Диапазонный запрос

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

Делается это очень просто: считаем ранг элемента, и пляшем от него.

import sys

numbers = [int(x) for x in sys.stdin.read().split()]

a,b = numbers[-2:]
numbers = numbers[1:-2]

for i in range(search(numbers, a), len(numbers)): ## здесь search из 2-го задания
    x = numbers[i]
    if x < b: print(x)
    else:     break

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

Ранг с ключом

Данные подаются в формате:

def read_data():
    n = int(input())
    a0, b0 = [int(x) for x in input().split()]

    pairs = []
    for i in range(n):
        pairs.append([i]+[int(x) for x in input().split()])
    
    return a0, b0, sorted(pairs, key = lambda x: x[1]+x[2])

Требуется вывести (в порядке возрастания) номера тех пар чисел, сумма которых не больше суммы заданной пары a0,b0.

Сначала перепишем функцию нахождения ранга следующим образом:

def search(haystack, needle, keyfunc):
    left  = 0
    right = len(haystack)
    
    while right - left > 1:
        m = (left + right - 1) // 2
        if keyfunc(haystack[m]) < needle: left  = m+1
        else:                             right = m+1
    
    if right > left and keyfunc(haystack[left]) >= needle: return left
    
    return len(haystack)

затем воспользуемся ей:

a0, b0, numbers = read_data()

n = search(numbers, a0+b0+1, lambda x: x[1]+x[2])
##                       ^^=====\\
##                              ||
## стоит обратить внимание на ==//

print(*sorted([numbers[i][0]+1 for i in range(n)]))

Бинарный поиск ответа

Была задача с немного нетривиальным условием. Вот её решение:

def check(segments, k, l):
  total = sum([x // l for x in segments])
  return total >= k

## это последний среди True (специализация решения 1-й задачи)
def solve(segments, k):
  left  = 1
  right = max(segments)+1
  
  while right - left > 1:
    m = (right + left) // 2
    if check(segments, k, m): left  = m
    else:                     right = m
  
  if check(segments, k, left): return left
  
  return 0
  
import sys

n, k, *numbers = [int(x) for x in sys.stdin.read().split()]
print(solve(numbers,k))

Идея в том, что если нельзя выпилить K отрезков некоторой длины, то нельзя выпилить и K отрезков любой большей длины. Поэтому предикат «L -> можно ли выпилить нужное количество отрезков длины L?» является монотонным и к нему можно применить бинарный поиск.

Возведение в степень

Без лишних комментариев:

def power(a,b):
    if b == 0:     return 1
    
    root = power(a,b//2)

    if b%2 == 0: return root*root
    return            a*root*root

Быстрое вычисление чисел Фибоначчи

Есть замечательное соотношение (вы его должны были изучать на спецматематике):

F(n+k) = F(n)*F(k+1) + F(n-1)*F(k)

Те, кто в него не верит, могут воспользоваться индукцией по k:

F(n)*F(1) + F(n-1)*F(0) = F(n)*1 + F(n-1)*0 = F(n)*1 = F(n)
F(n)*F(2) + F(n-1)*F(1) = F(n)*1 + F(n-1)*1 = F(n+1)

  F(n)*F(k+2) + F(n-1)*F(k+1) = по определению F =
= F(n)*F(k+1) + F(n)*F(k)   +   F(n-1)*F(k) + F(n-1)*F(k-1) = переупорядочиваем =
= F(n)*F(k+1) + F(n-1)*F(k)   +   F(n)*F(k) + F(n-1)*F(k-1) = предположение индукции =
= F(n+k) + F(n+k-1) = F(n+k+1)

Из этого соотношения, в частности, следует:

F(2n)   = F(n)*F(n+1) + F(n-1)*F(n) = 2 F(n)*F(n+1) - F(n)*F(n)
F(2n+1) = F(n+1)*F(n+1) + F(n)*F(n)

Ну и из этой пары соотношений следует очевидное решение (сравните с решением предыдущего номера):

def two_fibs(n):  ## f(n), f(n+1)
    if n == 0: return 0,1
    if n == 1: return 1,1
    
    root = two_fibs(n//2)
    
    a = 2*root[0]*root[1] - root[0]*root[0]
    b = root[1]*root[1] + root[0]*root[0]
    
    if n%2 == 0: return a,b
    return b,a+b

def fib(n): return two_fibs(n)[0]

Слияние упорядоченных массивов

Добавление элемента к упорядоченному массиву — весьма ресурсоёмкая операция: легко найти (бинарным поиском) то место, куда элемент этот нужно вставить, но для самой вставки часть массива нужно подвинуть. В худшем случае это требует времени, пропорционального длине массива.

Тем не менее, если требуется добавить сразу много элементов, можно (как и в случае с обычным массивом) сделать среднее время добавления элемента малочувствительным к размеру массива. Особенно просто это осуществляется, если новые элементы уже упорядочены.

Алгоритм слияния

Приведём код без каких-либо предварительных комментариев:

def merge(a,b):
    i,j = 0,0
    c = []
    
    while i < len(a) and j < len(b):
        if a[i] < b[j]: c.append(a[i]); i += 1
        else:           c.append(b[j]); j += 1

    c += a[i:]
    c += b[j:]

    return c

Нетрудно видеть, что в результирующем массиве присутствуют все элементы входных, причём в правильном порядке (если, конечно, оба входных массива были упорядочены).

Время работы этого алгоритма пропорционально размеру результата (если, конечно, считать время доступа к элементу массива не зависящим от длины массива). Получается, например, что если мы сливаем массивы одинаковых размеров, то удельное время слияния в пересчёте на один элемент перестаёт зависеть от размера сливаемых массивов.

Алгоритм сортировки

При помощи слияния нетрудно описать рекурсивный алгоритм, позволяющий достаточно быстро упорядочить произвольный массив. Опять же, приведём сперва соответствующий код:

def merge_sort(a):
    if len(a) < 2: return a[:]

    m = len(a)//2
    
    l = merge_sort(a[:m])
    r = merge_sort(a[m:])

    return merge(l,r)

Комментарий первый: a[:] во второй строчке нужно для того, чтобы выходной массив всегда отличался от входного (такие же гарантии, например, даёт встроенная в питон функция sorted).

Комментарий второй: этот алгоритм работает за конечное время и выдаёт результат упорядочивания элементов входного массива. Доказывается тривиальной индукцией по размеру входного массива.

Комментарий третий: этот алгоритм работает за время, пропорциональное n log(n), где n — размер входного массива. Доказательству этого факта посвящён следующий раздел (те, кто в это сразу верит, могут его не читать).

Анализ времени работы алгоритма сортировки

Пусть S(n) — максимально возможное время работы алгоритма сортировки на входном массиве длины n (измеренное, например, в шагах исполнителя). Для корректности определения будем считать, что для тех n, для которых нет максимума, S(n) равно бесконечности (нечто, большее любого целого числа).

Пусть M(m,n) — максимально возможное время слияния массивов длины m и n. Единственная гипотеза, которую придётся принять за аксиому — о том, что M(m,n) <= k*(m+n) для некоторого числа k.

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

Вернёмся к нашему анализу. Нетрудно заметить следующие два факта:

1. для некоторого целого A верно S(0) <= A и S(1) <= A.
2. для некоторого целого B верно S(n) <= S(n//2) + S(n - n//2) + k*n + B

Теперь осталось многократно применить неравенство из пункта 2 к S из правой части этого же неравенства до тех пор, пока все аргументы всех получившихся S не станут равны 0 или 1.

Общий вид такого перехода выглядит так:

S(a_1)+...+S(a_n) <= S(a_1//2)+S(a_1-a_1//2)+...+S(a_n)+S(a_n-a_n//2) + k*(a_1+a_2+...+a_n) + n*B

Поскольку у нас всегда a_1+...+a_n равно n, каждый переход добавляет к сумме n*(k+B).

Осталось заметить, что нам явно хватит log(n) + 1 переходов: это следует из (немного неочевидного) равенства (x//a)//b = x//(a*b).

Каждый переход удваивает количество S в сумме. Поэтому, после того, как в окончательной сумме мы применим S(0) <= A и S(1) <= A, мы получим

S(n) <= A * 2 ** (log(n) + 1) + (k+b)*n*(log(n) + 1)

Учитывая, что 2 ** log(n) по определению равно n, мы получаем:

S(n) <= (2*A+k+b)*n + (k+b)*n*log(n) <= 2*(A+k+b)*n*log(n)

То есть время работы алгоритма (с точностью до постоянного множителя) не больше, чем n log(n). Ровно таким же образом можно получить и аналогичную нижнюю оценку на время работы.

PS. Те, кого не устроил несколько неформальный характер вышеприведённых рассуждений, могут просто взять (полученную этими самыми рассуждениями) оценку 2*(A+k+b)*log(n) и банально доказать её по индукции.

Добавление к упорядоченному массиву большого количества элементов

Алгоритм сортировки позволяет реализовать следующий способ добавления к упорядоченному массиву элементов:

def extend(sorted_list, new_elements):
    return merge(sorted_list, merge_sort(new_elements))

При добавлении к n-элементому массиву n элементов за один раз удельное время работы в пересчёте на один элемент получается пропорциональным log(n), что на практике зачастую вполне удобоваримо.

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

В заключение

В реальных программах на python (и сходных по производительности скриптовых языках) все вышеописанные функции достаточно бесполезны: функции sorted и lambda a,b: sorted(a+b) работают существенно эффективнее написанных вручную аналогов. Тем не менее, они демонструруют полезную в целом идеологию решения задач «разделяй и властвуй»: иногда задачу можно эффективно решить, разбив её на несколько меньших подзадач, рекуррентно решив их, а затем соединив их решения в решение исходной задачи.

Биномиальные списки

Биномиальные списки — частный случай бинарно динамизированной структуры данных. Бинарная динамизация — простой способ «научить» почти любую структуру данных эффективному добавлению новых элементов.

Бинарная динамизация в общем виде

Предположим, у нас имеется некая структура данных foo с операциями:

## новый экземпляр структуры, хранящий указанный набор данных
def foo_new(elements): ...

## список всех данных с указанным ключом
def foo_get(foo, key): ...

## список всех хранимых элементов
def foo_elements(foo): ...

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

Например, для списков пар ключ-значение эти функции могут выглядеть так:

def list_new(elements): return elements[:]
def list_get(l,x): return [v for k,v in l if k==x]
def list_elements(l): return l[:]

А для словарей эти функции могут выглядеть так:

def dict_new(elements): 
    d = {}
    for k,v in elements:
        if k in d: d[k].append(v)
        else:      d[k] = [v]
    return d

def dict_get(d,k): return d[k] if k in d else []
def dict_elements(d): return [(k,v) for k in d for v in d[k]]

Суть динамизации заключается в том, что структура заменяется на набор уровней — аналогичных структур меньшего размера. При этом добавление элементов осуществляется на нижний уровень, а каждый уровень при превышении его вместимости переносится на следующий: ровно тем же образом происходит прибавление единицы к числу методом «в столбик».

Бинарная динамизация характеризуется тем, что каждый уровень вмещает 0 или 1 экземпляр структуры данных. Если на какой-то занятый уровень переносятся данные, они сливаются с имеющейся на этом уровне структурой, а результат слияния переносится на следующий уровень:

def dynfoo_new(): return {}

def dynfoo_append(d,k,v):
    new = foo_new( [(k,v)] )
    level = 0
    while level in d:
        old = d.pop(level)
        new = foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

def dynfoo_get(d,k):
    return [v for level in d for v in foo_get(d[level], k)]

Отметим две вещи:

1. если необходимо по каждому ключу хранить только одно значение (например, последнее добавленное, как в словарях языка python), то можно перед добавлением элемента искать его и модифицировать соответствующий уровень
2. если единственное требование — возможность по ключу получить хоть какой-то элемент, который добавлялся по этому ключу — можно особо не заморачиваться насчёт потери части данных при переносе на следующий уровнеь

В частности, вот два способа динамизировать стандартный словарь языка python:

## динамизация с уникальными ключами
def dict1_new(): return {}

def dict1_set(d,k,v):
    for level in d:
        if k in d[level]:
            d[level][k] = v
            return d

    new = {k: v}
    level = 0
    while level in d:
        old = d.pop(level)
        for k in old: new[k] = old[k]
        level += 1
    
    d[level] = new
    
    return d

def dict1_get(d,k):
    for level in d:
        if k in d[level]: return d[level][k]
    return None


## динамизация с потерей устаревших данных
def dict2_new(): return {}

def dict2_set(d,k,v):
    new = {k: v}
    level = 0
    while level in d:
        old = d.pop(level)
        for k in new: old[k] = new[k]  ## заменяем старые данные новыми
        new = old
        level += 1
    
    d[level] = new
    
    return d

def dict2_get(d,k):
    for level in sorted(d.keys()): ## более актуальные данные находятся раньше
        if k in d[level]: return d[level][k]
    return None

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

Анализ времени работы динамизированной структуры

Предположим, что структура данных, которую мы хотим динамизировать, создаётся из списка данных и разбивается на список данных за время, пропорциональное количеству этих данных. Тогда при слиянии двух таких структур одного размера среднее время слияния в пересчёте на один элемент не зависит от размера структуры.

Нетрудно заметить, что в динамизированной структуре, в которую N раз добавляли элемент, количество уровней не превосходит log(N), а размер k-го уровня не превосходит 2**k (если слияние двух структур даёт структуру суммарного размера, то размер k-го уровня всегда будет в точности 2**k).

Отсюда сразу следует, что при добавлении элемента среднее время слияния в пересчёте на один элемент увеличивается (по сравнению со слиянием двух экземпляров динамизируемой структуры одного размера) не более чем в log(N) раз. Ровно то же самое происходит и со временем (уже не средним) поиска элемента.

Биномиальный список

Биномиальный список — результат бинарной динамизации упорядоченного списка. Можно было бы и не приводить здесь соответствующий код (всё, что нужно, есть выше), но мы всё же приведём вариант для списка-множества (когда поиск происходит не по ключу, а по значению): такой вариант нами ещё не рассматривался.

def binlist_new(): return {}

def binlist_append(d,x):
    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

from bisect import bisect_left, bisect_right

def binlist_count(d,x):
    total = 0
    for level in d:
        l = d[level]
        total += bisect_right(l,x) - bisect_left(l,x)
    return total

Удаление элементов

См. решения упражнений.

Разбор ДЗ №2

Просьба как можно более срочно сообщать об ошибках/опечатках в случае их обнаружения. Они, очень вероятно, здесь есть по чисто статистическим соображениям.

Множество с размером

Ниже — обычный биномиальный список:

def binlist_new(): return {}

def binlist_append(d,x):
    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

from bisect import bisect_left, bisect_right

def binlist_count(d,x):
    total = 0
    for level in d:
        l = d[level]
        total += bisect_right(l,x) - bisect_left(l,x)
    return total
    
def binlist_size(d):
    return sum([len(d[level]) for level in d])

Требовалось поменять в нём функцию добавления элемента binlist_append так, чтобы нельзя было добавить более одного экземпляра каждого элемента. Модификация довольно тривиальна:

def binlist_append(d,x):
    if binlist_count(d, x) > 0: return d  ## вот она!

    new = [x]
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

Словарь

Просто немного изменим код предыдущей задачи. Изменения помечены комментариями.

def bindict_new(): return {}

def bindict_append(d,k,x): ## появился ключ
    if bindict_replace(d,k,x): return d
    ## вместо проверки наличия элемента сразу пытаемся его вставить

    new = [(k,x)] ## пара ключ-значение
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

## бинарный поиск приходится писать вручную (взят из материалов)
def binsearch(l, k):
    left, right = 0, len(l)
    while right - left > 1:
        m = (right + left - 1) // 2
        if l[m][0] < k: left  = m+1
        else:           right = m+1
    
    if right - left == 1 and l[left][0] == k: return left
    

def bindict_get(d,k):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: return haystack[index][1]
        
def bindict_replace(d,k,x):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            haystack[index] = (k,x)
            return True
    
    return False

    
    
def bindict_size(d):
    return sum([len(d[level]) for level in d])

На первый взгляд реализации функций bindict_get и bindict_replace похожи друг на друга. На второй — тоже. Да и на третий... Довольно естественно их обобщить:

def bindict_act(d,k,on_success,on_failure):
    for level in d:
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            return on_success(haystack, index)
    
    return on_failure
    

def bindict_get(d,k):
    return bindict_act(d, k, lambda l,i: l[i][1], None)
    
def bindict_replace(d,k,x):
    def replace(l,i):
        l[i] = x
        return True
        
    return bindict_act(d, k, replace, False)

Функциональный ключ

Изменения ещё менее значительны: нужно лишь вычислять ключ по значению, храня вычислитель ключа вместе со структурой данных. Приведены лишь изменившиеся функции:

def bindict_new(keyfunc): return { "keyfunc": keyfunc }

def bindict_append(d,x): ## исчез ключ
    kf = d["keyfunc"]
    k  = kf(x)
    
    if bindict_replace(d,k,x): return d

    new = [(k,x)] ## пара ключ-значение
    level = 0
    while level in d:
        old = d.pop(level)
        new = sorted(old + new)
        level += 1
    
    d[level] = new
    
    return d

def bindict_act(d,k,on_success,on_failure):
    for level in d:
        if level == "keyfunc": continue ## это не уровень, а ключевая функция!
        haystack = d[level]
        index = binsearch(haystack, k)
        if index != None: 
            return on_success(haystack, index)
    
    return on_failure
    
def bindict_size(d):
    ## тут тоже не забываем про исключение ключевой функции из набора
    ## обрабатываемых данных
    return sum([len(d[level]) for level in d if level != "keyfunc"])

Динамизация суммы

Требовалось дописать функцию sum_append к данному в условии коду. Достаточно было взять общий алгоритм динамизации:

def dynfoo_append(d,k,v):
    new = foo_new( [(k,v)] )
    level = 0
    while level in d:
        old = d.pop(level)
        new = foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

И специализировать его:

def sum_append(s,x):  ## k,v ==> x
    new = x ## foo_new( [(k,v)] ) ==> foo_new( x ) ==> x
    level = 0
    while level in d:
        old = d.pop(level)
        new = old+new ## foo_new(foo_elements(old)+foo_elements(new))
        level += 1
    
    d[level] = new
    
    return d

Всё!

Удаление с призраками

Требовалось научить биномиальный список «удалять» свои элементы. Три из пяти функций уже приведены в условии. Осталось написать ещё две. Вот они:

## полностью аналогично spectred_size
def spectred_count(s,x):
    return binlist_count(s["main"],x) - binlist_count(s["spectre"],x)


def spectred_remove(s,x):
    binlist_append(s["spectre"],x)

    if binlist_size(s["spectre"])*2 > binlist_size(s["main"]):
        ## отсев дубликатов
        elements = set(binlist_elements(s["main"]))
        
        to_append = []
        for x in elements:
            to_append += [x]*spectred_count(s,x)
            ## каждый элемент берём столько раз, сколько он должен встречаться
        
        new = binlist_new()
        for x in to_append:
            binlist_append(new,x)

        s["main"]    = new
        s["spectre"] = binlist_new()

    return s

Удаление по ключу

Эта задача существенно проще предыдущей, если помнить об одном «но»: нельзя пересчитывать количество «трупов» при каждом удалении — это приводит к общей квадратичной зависимости многократного удаления от количества удалённых элементов (и линейной в среднем в пересчёте на один элемент).

Здесь приведём лишь интересную часть — функцию bindict_remove:

def bindict_new():
    ## счётчик количества удалённых элементов (наравне с уровнями структуры)
    return { "removed_count": 0 }

def bindict_remove(d,k):
    bindict_append(d,k,None)
    d["removed_count"] += 1

    if d["removed_count"]*2 > bindict_size(d):
        new = bindict_new()
        for k,v in [x for level in d 
                      if level != "removed_count" 
                      for x in d[level] 
                      if x[1] != None]:
            bindict_append(new,k,v)
        
        d.clear()
        
        for level in new:
            if level == "removed_count": d[level] = 0
            d[level] = new[level]

    return d

Косодвоичная система счисления

Это задание для отдыха (только почему-то никто почти этого не заметил...).

def digits(x):
    d = 1
    while d <= x:
        d = 2*d + 1
    
    result = []
    while d > 1:
        d //= 2
        result.append(x // d)
        x = x % d
        
    return result

def digits_str(digits):
    if len(digits) == 0: return "0"
    
    return "".join([str(d) for d in digits])
    
print(digits_str(digits(int(input()))))

Косодвоичная динамизация

А вот тут код уже без особых комментариев (если Вы внимательно изучили всё вышенаписанное, тут вообще всё будет знакомо):

def sum_new(): return [{},None]

def sum_append(s,x):
    d = s[0]
    if s[1] == None:
        return append_to_level(s,0,x)

    l, s[1] = s[1], None
    a,b = d.pop(l)
    return append_to_level(s,l+1,a+b+x)


def append_to_level(s,l,x):
    d = s[0]
    if l in d:
        d[l] = tuple(sorted([x,d[l]]))
        s[1] = l
    else:
        d[l] = x

    return s
    
    
def sum_total(s):
    d = s[0]
    total = 0
    for l in d:
        if type(d[l]) == tuple:
            total += sum(d[l])
        else:
            total += d[l]
    return total

def sum_levels(s):
    s = s[0]
    max_level = max(sorted(s.keys()))
    return [(s[level] if level in s else 0) 
            for level in range(max_level+1)]

Интерлюдия 1: меташары

В этом разделе для вывода изображений на экран используется библиотека pygame, а для арифметических операций над массивами — библиотека numpy. Если Вы хотите попробовать запустить нижеприведённый код, Вам потребуется их установить (как именно — зависит от используемой Вами комбинации ОС и дистрибутива языка Python). В простейшем случае (большинство дистрибутивов Linux) достаточно воспользоваться системным менеджером пакетов. В экзотических случаях (Mac OS, Windows, прочее) следует обратиться к руководству pygame и numpy.

Деревья

В математике деревом называется произвольный связный ациклический неориентированный граф. В информатике же под деревом по-умолчанию понимают существенно более конкретную структуру, называемую в математике рекуррентным или алгебраическим деревом. Говоря неформально, дерево — это либо «лист», либо последовательность деревьев.

Дерево как АДТ

Несколько более формально можно дать следующее определение: дерево — это абстрактный тип данных (АДТ), изоморфный следующему

def leaf(x):
    return ("leaf", x)

def branch(x, trees):
    return ("branch", x, list(trees))
    
def reduce(tree, leaf_op, branch_op):
    if tree[0] == "leaf":
        return leaf_op(tree[1])
    elif tree[0] == "branch":
        return branch_op(
            tree[1], 
            [reduce(subtree, leaf_op, branch_op) 
                for subtree in tree[2]])
    else:
        raise RuntimeError("wrong tree")

Напомним, что под изоморфизмом типов данных имеется в виду биекция между этими типами, «коммутирующая» со всеми операциями, ассоциированными с этими типами.

Например, следующий тип данных (называемый катаморфным представлением или кодировкой Чёрча) тоже является деревом:

def cata_leaf(x):
    return (lambda l, b: l(x))

def cata_branch(x, trees):
    return (lambda l, b: b(x, [t(l,b) for t in trees]))
    
def cata_reduce(tree, leaf_op, branch_op):
    return tree(leaf_op, branch_op)

А вот — биекция между ними:

def tree_to_cata(tree):
    return lambda l, b: reduce(tree, l, b)
    
def cata_to_tree(cata):
    return cata(
        lambda x: ("leaf", x),
        lambda x, trees: ("branch", x, trees))

Или, если на неё посмотреть немного повнимательнее:

def tree_to_cata(tree):
    return reduce(tree, cata_leaf, cata_branch)

def cata_to_tree(cata):
    return cata_reduce(cata, leaf, branch)

Общее у двух вышеописанных моделей лишь поведение reduce относительно leaf и branch. А именно, выполняются следующие свойства:

• reduce(leaf(x), l, b) = l(x)
• reduce(branch(x,trees), l, b) = b(x, [reduce(t,l,b) for t in trees])

Именно они и задают дерево как абстрактный тип данных.

Что это вообще было?

Теперь поясним подробнее то, что сейчас произошло. Для того, чтобы всё встало на свои места, достаточно понять одну простую вещь:

• деревья — то же самое, что алгебраические формулы (с которыми вы общаетесь уже не менее 9 лет)

Слова «то же самое» нужно понимать совершенно буквально: деревья (в информатике) и алгебраические формулы (в математике) — одно и то же.

Например, вот формула:

foo(1,2) + 3*(4**5 + foo(6,7))

Вот — соответствующиее ей дерево:

branch("+", [
  branch("foo", [leaf(1), leaf(2)]),
  branch("*", [
    leaf(3),
    branch("+", [
      branch("**", [leaf(4), leaf(5)]),
      branch("foo", [leaf(6), leaf(7)])])])])

А таинственный на первый взгляд метод reduce всего лишь описывает процесс вычисления формулы для заданных интерпретаций операций, в ней фигурирующих. Например, чтобы получить из дерева выше значение формулы выше, аналогичное тому, которое получит интерпретатор языка Python, достаточно применить reduce к следующим аргументам:

def interpret_leaf(x): return x

def interpret_branch(op, args):
    a,b = args
    
    if op == "+": return a+b
    if op == "*": return a*b
    if op == "**": return a**b
    if op == "foo": return foo(a,b)

Кодировка Чёрча же всего лишь иллюстрирует тот факт, что формула — это то же самое, что и алгоритм её вычисления, параметризованный интерпретациями операций (а термином катаморфизм или свёртка называется как раз алгоритм вычисления формулы, параметризованный интерпретациями операций).

Очередь с приоритетом

Напомним, что очередь с приоритетом относится к структурам данных, грубо говоря, типа «ящик»: в неё можно класть что-нибудь (по собственному выбору) и забирать что-нибудь (без возможности выбрать, что именно). Структуры такого плана возникали в нашем курсе ранее, во время обсуждения разнообразных обходов графов. Конкретно очередь с приоритетом, например, лежит в основе алгоритма Дейкстры.

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

Наивная реализация

Очередь с приоритетом работает так:

class pqueue:
    def __init__(self):
        self.data = []
    
    ## этот метод вызывается стандартной функцией len
    def __len__(self):  
        return len(self.data)

    def put(self, priority, datum):
        self.data.append( (priority, datum) )

    def take(self):
        min_priority = min([x[0] for x in self.data])
        
        for i, x in enumerate(self.data):
            if x[0] == min_priority:
                self.data = self.data[:i]+self.data[i+1:]
                return x

Эта реализация хороша в качестве описания того, как именно работает очередь с приоритетом. Но она обычно плохо себя ведёт на практике: взятие из неё одного элемента занимает время, пропорциональное количеству хранимых элементов.

Одноразовая очередь

Будем говорить, что очередь (с приоритетом) является одноразовой, если она не поддерживает операцию добавления элемента (а вместо этого позволяет добавить все необходимые элементы при создании).

Самой простой реализацией такой очереди является просто упорядоченный массив:

class array_pqueue1:
    def __init__(self, data):
        self.data = sorted([(p,v) for p,v in data],
                           key = lambda x: -x[0]) ## в обратном порядке
    
    def __len__(self):  
        return len(self.data)

    def take(self):
        return self.data.pop()

Альтернативной реализацией является сбалансированное дерево минимумов. Под словом «сбалансированное» понимается логарифмическая зависимость между количеством элементов и высотой дерева, по ним построенного.

Обратите внимание, что нижеприведённый код использует конкретную модель дерева (а именно, S-выражения). Это связано с тем, что катаморфное описание процедуры извлечения элемента из мультимножества требует дополнительных технических деталей, существенно затрудняющих изложение.

def tree_priority(tree):
    ## (p,v) -> p
    ## [p, t1, t2, ... tn] -> p
    return tree[0]

def min_branch(trees):
    return [min(map(tree_priority,trees))] + trees

class tree_pqueue1:
    def __init__(self, data, branching_factor=8):
        trees = [(p,v) for p,v in data]
        self.len = len(trees)
        self.bf = branching_factor  ## self.bf пока не используется
        
        if len(trees) == 0:
            self.tree = None
            return

        while len(trees) > 1:
            new_trees = []
            
            for i in range(0,len(trees),branching_factor):
                to_wrap = trees[i:i+branching_factor]
                new_trees.append(min_branch(to_wrap))

            trees = new_trees

        self.tree = trees[0]

    def __len__(self):
        return self.len

    def take(self):
        ## вспомогательный рекуррентный обход, возвращающий
        ## дерево без удалённого элемента и этот элемент
        def extract(tree, priority):
            if type(tree) != list: return None, tree

            new_trees = []
            result = None
            extracted = False  ## именно из-за этой мутабельной переменной
                               ## катаморфное описание несколько затруднено
            for t in tree[1:]:
                if t == None: continue
                
                if tree_priority(t) == priority and not extracted:
                    new_tree, result = extract(t, priority)
                    extracted = True
                    if new_tree != None: new_trees.append(new_tree)
                else:
                    new_trees.append(t)

            if len(new_trees) == 0: return None, result
            return min_branch(new_trees), result

        if self.tree == None: raise RuntimeError("queue is empty")
        
        p = self.tree[0]
        self.tree, result = extract(self.tree, p)
        self.len -= 1

        return result

Динамизированный упорядоченный массив

Обе вышеописанные структуры можно динамизировать, чтобы получить эффективное добавление элементов. Но на практике лучше динамизировать упорядоченный массив — он банально проще и эффективнее.

def rev_sorted(xs):
    return sorted(xs, key=lambda x: -x[0])

class array_pqueue:
    def __init__(self):
        self.clean()

    def __len__(self):
        return self.inserted_count - self.deleted_count

    def clean(self):
        self.levels = {}
        self.inserted_count = 0
        self.deleted_count = 0

    def reconstruct(self):
        if self.inserted_count == self.deleted_count:
            return self.clean()

        elements = rev_sorted([x for l in self.levels 
                                 for x in self.levels[l]])
        level = 0
        good_size = 1
        
        while good_size < len(elements):
            level += 1
            good_size *= 2

        self.levels = { level: elements }
        self.inserted_count = len(elements)
        self.deleted_count = 0

    def put(self, priority, datum):
        new = [(priority, datum)]
        level = 0
    
        while level in self.levels:
            old = self.levels.pop(level)
            new = rev_sorted(old + new)
            level += 1
    
        self.levels[level] = new
        self.inserted_count += 1

    def take(self):
        best_level = None
        best_priority = None
        for level in self.levels:
            priority = self.levels[level][-1][0]
            if best_level == None or best_priority > priority:
                best_level = level
                best_priority = priority

        if best_level == None: raise RuntimeError("queue is empty")
        
        elements = self.levels[best_level]
        result = elements.pop()

        if len(elements) == 0: del self.levels[best_level]
        
        self.deleted_count += 1
        if self.deleted_count*2 >= self.inserted_count:
            self.reconstruct()

        return result

А вот с деревом можно произвести более интересную модификацию.

Самобалансирующееся B-дерево

Дерево называют самобалансирующимся, если оно поддерживает операцию добавления новых данных с сохранением сбалансированности (засчёт изменения своей структуры). Исторически первой разновидностью самобалансирующихся деревьев считаются деревья Адельсон-Вельского и Ландиса. На настоящий момент (2018 год) существенно более популярны разновидности т.н. B-деревьев.

B-дерево отличается от вышеописанного одноразового дерева, грубо говоря, следующим:

• каждая ветка одноразового дерева содержит не более branching_factor поддеревьев
• B-дерево допускает менее чем двукратное превышение этого количества; при двукратном превышении дерево «разрывается» на две части

Одноразовое дерево можно преобразовать в B-дерево, просто добавив к нему метод вставки нового элемента:

def put(self, priority, datum):
    def insert(tree, priority, datum):
        if type(tree) != list: return [tree, (priority, datum)]
        
        trees = tree[1:-1] + insert(tree[-1], priority, datum)
        if len(trees) >= 2*self.bf:
            part1 = trees[:self.bf]
            part2 = trees[self.bf:]
            return [ min_branch(part1), min_branch(part2) ]

        return [ min_branch(trees) ]
    
    if self.tree == None:
        self.tree = [priority, (priority, datum)]
    else:
        roots = insert(self.tree, priority, datum)
        if len(roots) == 1: self.tree = roots[0]
        else: self.tree = min_branch(roots)

    self.len += 1

Классическая реализация (т.н. бинарная куча)

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

Все данные хранятся в массиве, обладающим следующим свойством: для всех i элемент на i-м месте не больше (по приоритету) элементов на местах (2*i+1) и (2*i+2) (если таковые места есть).

def swap(array, i, j):
    array[i], array[j] = array[j], array[i]

class heap_pqueue:
    def __init__(self):
        self.data = []
    
    def __len__(self):
        return len(self.data)
    
    def put(self, priority, datum):
        i = len(self.data)

        ## новый элемент добавляется в конец, а затем прогоняется к началу
        self.data.append( (priority, datum) )

        while i > 0:
            parent = (i-1)//2
            if self.data[i][0] >= self.data[parent][0]: break

            swap(self.data, i, parent)
            i = parent

    def take(self):
        ## первый элемент обменивается с последним
        swap(self.data, 0, -1)
        result = self.data.pop()
        
        ## затем (бывший) последний элемент прогоняется к концу массива
        i = 0
        while True:
            a = 2*i+1
            b = 2*i+2
            if a >= len(self.data): return result

            if b < len(self.data) and self.data[b][0] < self.data[a][0]: a = b
            
            if self.data[i][0] <= self.data[a][0]: return result
            
            swap(self.data, i, a)
            i = a

Реализация очереди с приоритетом при помощи бинарной кучи по количеству кода короче почти любой другой эффективной реализации (за исключением, разве что, динамизированного массива без реконструкции). При этом она обладает неплохой производительностью, хотя и меньшей универсальностью: в отличие от бинарной кучи, как динамизированный массив, так и B-дерево (после незначительной модификации операции добавления элемента) можно использовать ещё и как словарь.

Об использовании дерева минимумов в качестве словаря (называемого в этом случае деревом поиска) будет следующий раздел, а сейчас скажем чуть-чуть о производительности всех вышеописанных подходов.

Сравнение производительности

Начнём с очень важной вещи: все тесты производительности — одна большая ложь. Реальная производительность зависит от огромного количества факторов, которые трудно исключить из сравнения. Приведённые ниже числа отражают лишь поведение конкретного кода на конкретной реализации конкретного языка программирования на конкретном компьютере.

Для других сочетаний код/язык/компилятор/компьютер относительная скорость работы алгоритмов может быть (и является) другой. Скажем лишь, что среди вышеприведённых трёх «эффективных» подходов нет однозначного лидера или же однозначного аутсайдера: для каждого из них есть обстоятельства, при которых он работает лучше других.

Теперь, собственно, опишем тесты, на которых измерялась производительность:

1. добавление N элементов к пустой очереди
2. удаление N элементов из заполненной очереди
3. предварительное добавление 1000 элементов (не измерялось), а затем N-кратное добавление/удаление одного элемента

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

Сначала результаты для добавления N элементов.

|алгоритм|мкс/эл N=100|мкс/эл N=1000|мкс/эл N=10000|мкс/эл N=100000|мкс/эл N=1000000| |-|-|-|-|-| |наивный|1|1|1|-|-| |массив|8|8|10|12|14| |дерево|14|22|30|38|46| |куча|3|3|3|3|3|

Для удаления N элементов.

|алгоритм|мкс/эл N=100|мкс/эл N=1000|мкс/эл N=10000|мкс/эл N=100000|мкс/эл N=1000000| |-|-|-|-|-| |наивный|15|102|987|-|-| |массив|3|3|3|4|4| |дерево|21|34|45|58|79| |куча|8|14|21|28|37|

Для продолжительной работы.

|алгоритм|мкс/эл N=100|мкс/эл N=1000|мкс/эл N=10000|мкс/эл N=100000|мкс/эл N=1000000| |-|-|-|-|-| |наивный|147|150|273|-|-| |массив|20|15|12|8|6| |дерево|59|57|73|79|83| |куча|19|19|24|25|26|

Разбор ДЗ №3

Интерлюдия 2: разбор S-выражений

Задача разбора выражений состоит в том, чтобы преобразовывать текст (понимаемый как последовательность символов) в какой-либо структурированный формат. В этом разделе мы изложим подход к разбору выражений, называемый комбинаторами парсеров.

Парсеры

Парсером мы будем называть функцию, получающую на вход текст, а в качестве результата выдающая хвост этого текста (хвостом или суффиксом текста t называется любой текст y такой, что для какого-то x выполнено t = x+y), спаренный с некоторыми данными произвольного вида. Будем говорить, что эти данные получены путём разбора или, как ещё говорят, парсинга вырезанного из текста куска.

Вот типичный пример парсера:

def parse_digit(text):
    if len(text) > 0 and '0' <= text[0] <= '9':
        return text[0], text[1:]

Этот парсер разбирает одну цифру из текста. Обратите внимание на то, что в случае неудачи этот парсер возвращает значение None. Договоримся и дальше придерживаться такого соглашения. В связи с этим уточним понятие парсера.

Любой парсер обрабатывает поданный ему на вход текст t так:

• если удалось найти такой x, что t = x + y и x можно разобрать, парсер возвращает пару (r, y), где r — результат разбора текста x;
• если же такого x нет, парсер возвращает None

Приведём ещё один пример парсера:

def parse_spaces(text):
    for i, x in enumerate(text):
        if x != ' ': return i, text[i:]

Этот парсер разбирает все пробелы из начала текста, преобразуя их в их количество.

Генераторы парсеров

Обычно парсеры создаются «на ходу» при помощи функций, называемых генераторами парсеров (далее мы будем их называть просто генераторами; не путать с одноимённым типом данных языка Python!). Вот — типичный пример генератора:

def gen_parse_char(x):
    def parse(text):
        if len(text) > 0 and text[0] == x: return x, text[1:]

    return parse

Но нам в первую очередь будет интересен генератор тривиальных парсеров:

def gen_trivial(x):
    return (lambda text: (x, text))

Тривиальный парсер разбирает пустой текст, выдавая в качестве результата разбора заранее заданные данные. На первый взгляд такой парсер совершенно бесполезен. Но только до тех пор, пока мы не перешли к следующей части рассказа.

Связывание

Парсерным связыванием называется следующая операция:

def bind(parse, gen):
    def composite(text):
        result = parse(text)
        
        if result == None: return None
        
        value, text_tail = result
        
        return gen(value)(text_tail)


    return composite

Её определение говорит само за себя: она «связывает» парсер с генератором в единую цепочку: парсер передаёт генератору свой результат, а сгенерированному по этому результату второму парсеру — оставшийся после разбора текст.

При помощи операции связывания можно писать странные (на первый взгляд) вещи. Например, вот парсер, распознающий двухзначное число:

parse_two_digit_number = (
    bind(parse_digit, lambda d1:
    bind(parse_digit, lambda d2:
    gen_trivial( int(d1+d2) )))
)

Этот код довольно сильно напоминает программу вида

def extract_two_digit_number():
    d1 = extract_digit()
    d2 = extract_digit()
    return int(d1 + d2)

за тем исключением, что:

• не содержит неявного глобального состояния
• корректно обрабатывает возможные промежуточные ошибки разбора текста (например, неудачное извлечение первой цифры)

Альтернатива

Парсерное связывание иногда называют горизонтальным: оно отвечает за последовательность операций. Бывает ещё вертикальное связывание (будем его в дальнейшем называть операцией альтернативы)

def alt(parsers):
    def parse(text):
        for p in parsers:
            result = p(text)
            if result != None: return result

    return parse

и выражающаяся в его терминах операция «провала»:

parse_fail = alt([])

Альтернатива позволяет писать рекуррентные парсеры в терминах связывания:

def parse_digits(text):
    p = alt([
        # цифры числа -- это либо цифра, за которой следуют ещё цифры
            bind(parse_digit, lambda d:
            bind(parse_digits, lambda ds:
            gen_trivial(d+ds))), 
        # либо одна цифра
            parse_digit])

    return p(text)

parse_number = bind(parse_digits, lambda ds: 
               gen_trivial(int(ds)))

Разбор S-выражений

Собственно, мы готовы написать простой разбиратель S-выражений. Сначала сделаем чуть более умный парсер числа:

parse_sign = alt([gen_parse_char('-'), gen_parse_char('+'), gen_trivial('')])

parse_number = bind(parse_sign, lambda s:
               bind(parse_digits, lambda ds:
               gen_trivial(int(s+ds))))

Далее сделаем парсер нечисловых слов:

def gen_parse_alphabet(a):
    def parse(text):
        if len(text) > 0 and text[0] in a: 
            return text[0], text[1:]
    
    return parse

def gen_parse_word(a):
    pc = gen_parse_alphabet(a)

    def parse_word(text):
        p = alt([
            bind(pc, lambda c:
            bind(parse_word, lambda w:
            gen_trivial(c+w))),

            pc])

        return p
    
    return parse_word

Определение parse_word почти полностью повторяет определение parse_digits. Эти определения абстрагируются комбинатором many1:

def many1(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            bind(p, lambda x:
            gen_trivial([x]))])

        return r(text)

    return parse

В терминах этого комбинатора

def gen_parse_word(a):
    return bind(many1(gen_parse_alphabet(a)), lambda xs:
           gen_trivial(''.join(xs)))

parse_digits = gen_parse_word('1234567890')

Также бывает полезен комбинатор many:

def many(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            gen_trivial([])
        ])

        return r(text)

    return parse

В терминах которого выражается many1:

def many1(p):
    return bind(p,       lambda x:
           bind(many(p), lambda xs:
           gen_trivial( [x] + xs )))

Теперь, наконец, мы можем описать всю грамматику S-выражений:

parse_word = gen_parse_word(
'qwertyuiop[]asdfghjkl;\'zxcvbnm,./1234567890-'+
'=!@#$%^&*_+\\|QWERTYUIOP{}ASDFGHJKL:"ZXCVBNM<>?'
)

def parse_sexp(text):
    p = bind(parse_spaces, lambda _:
        alt([
            bind(gen_parse_char('('), lambda _:
            bind(many(parse_sexp), lambda exps:
            bind(parse_spaces,        lambda _:
            bind(gen_parse_char(')'), lambda _:
            gen_trivial( exps )))),

            parse_number,
            parse_word
        ]))

    return p(text)

Итоговый код

Приведём для полноты картины итоговую программу, разбирающую S-выражения.

## Комбинаторы парсеров

def gen_trivial(x):
    return (lambda text: (x, text))

def bind(parse, gen):
    def composite(text):
        result = parse(text)
        
        if result == None: return None
        
        value, text_tail = result
        
        return gen(value)(text_tail)


    return composite

def alt(parsers):
    def parse(text):
        for p in parsers:
            result = p(text)
            if result != None: return result

    return parse

def many(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            gen_trivial([])
        ])

        return r(text)

    return parse

def many1(p):
    return bind(p,       lambda x:
           bind(many(p), lambda xs:
           gen_trivial( [x] + xs )))


## И сами парсеры

def gen_parse_alphabet(a):
    def parse(text):
        if len(text) > 0 and text[0] in a: 
            return text[0], text[1:]
    
    return parse


def gen_parse_word(a):
    return bind(many1(gen_parse_alphabet(a)), lambda xs:
           gen_trivial(''.join(xs)))


gen_parse_char = gen_parse_alphabet

parse_sign = alt([gen_parse_char('-'), gen_parse_char('+'), gen_trivial('')])

parse_digits = gen_parse_word('1234567890')

parse_number = bind(parse_sign, lambda s:
               bind(parse_digits, lambda ds:
               gen_trivial(int(s+ds))))

parse_word = gen_parse_word(
'qwertyuiop[]asdfghjkl;\'zxcvbnm,./1234567890-'+
'=!@#$%^&*_+\\|QWERTYUIOP{}ASDFGHJKL:"ZXCVBNM<>?'
)

parse_spaces = many(gen_parse_char(' '))

def parse_sexp(text):
    p = bind(parse_spaces, lambda _:
        alt([
            bind(gen_parse_char('('), lambda _:
            bind(many(parse_sexp), lambda exps:
            bind(parse_spaces,        lambda _:
            bind(gen_parse_char(')'), lambda _:
            gen_trivial( exps ))))),

            parse_number,

            parse_word
        ]))

    return p(text)

Деревья поиска

Этот раздел обобщает материалы практических заданий (а именно, «домашнего задания №3»). Структура данных, в нём рассмотренная, является, по-видимому, самой распространённой иерархической структурой данных: различные её вариации встречаются повсеместно и используются для решения самых разных практических задач.

Геометрические запросы и алгебра регионов

Представим себе типичный запрос к базе данных: найти количество всех людей мужского пола старше 17 лет. Этот запрос можно охарактеризовать прямоугольником \([1,1]\times[18,+\infty]\) в двухмерном целочисленном пространстве.

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

Ключевым «геометрическим» инструментом является отношение «фигура \(A\) является частью фигуры \(B\)». Мы будем это кратко записывать как \(A\subset B\). От такого отношения мы ожидаем как минимум следующих свойств:

1. каждая фигура является своей частью: \(A\subset A\)

2. часть части — часть: из \(A\subset B\subset C\) следует \(A\subset C\)

3. часть своей части — эта самая часть: из \(A\subset B\subset A\) следует \(A=B\)

Такие отношения называются отношениями (частичного) порядка. Числовые нестрогие неравенства, делимость, теоретико-множественное вложение, логическое следование — четыре самых распространённых примера частичных порядков. Из них наиболее соответствует геометрической интуиции теоретико-множественное вложение, но на практике оно довольно бесполезно: его трудно эффективно моделировать. Тем не менее, всю последующую терминологию мы позаимствуем именно у него.

Договоримся те объекты, на множестве которых мы будем рассматривать отношение «быть частью» называть регионами. Будем говорить, что регион \(A\) является объединением регионов \(A_i\), если:

• для всех \(i\) выполнено \(A_i\subset A\)
• если для всех \(i\) выполнено \(A_i\subset B\), то \(A\subset B\)

Проще говоря: объединение — наименьший регион, содержащий объединяемые регионы. Это же понятие можно встретить под названиями: максимум и точная верхняя грань (для числовых неравенств), наименьшее общее кратное (для делимости), дизъюнкция и квантор существования (в логике). Обозначается объединение так: \(A=\cup_i A_i\).

Аналогично определяется пересечение:

• для всех \(i\) выполнено \(A_i\supset A\)
• если для всех \(i\) выполнено \(A_i\supset B\), то \(A\supset B\)

Нетрудно угадать, что это понятие также носит названия: минимум, точная нижняя грань, наибольший общий делитель, конъюнкция, квантор общности. Обозначается пересечение знаком \(\cap\).

Объединение пустого набора регионов (регион, являющийся частью любого региона) будем называть пустым. Часто также можно встретить термин низ (bottom) и обозначение \(\bot\). Пересечение пустого набора регионов традиционно называется верх (top) и обозначается \(\top\), но нам оно не понадобится.

Интересен тот факт, что отношение «быть частью» выражается в терминах операций, им порождённых. А именно, высказывание \(A\subset B\) эквивалентно любому из следующих:

• \(A\cap B = A\)
• \(A\cup B = B\)

Хотя мы и определили пересечение регионов, оно нам дальше не понадобится. А понадобится следующее:

• операция объединения набора регионов
• отношение равенства регионов или же отношение «быть частью»
• подмножество (его элементы будем называть точками) множества всех регионов
• отношение раздельности регионов

Будем требовать, чтобы каждая точка была непуста и не содержала ничего, кроме себя и пустого региона (аналог точек в порядке делимости — простые числа).

Отношение раздельности определим так: регионы раздельны, если их пересечение не содержит ни одной точки (это отличается от непересекающихся регионов: мы не обязаны объявлять любой «простой» регион точкой).

Указанные четыре вещи мы будем моделировать функциями:

join(regions)  ## на вход -- список регионов
contains(a,b)  ## a содержит b
point(p)       ## на вход -- "метка" точки
disjoint(a,b)  ## a и b раздельны

Функция point разделяет типы данных «точка как регион» и «точка как вещь-в-себе». А именно, она преобразует второе в первое. Справедливости ради, более идиоматическим для динамически типизированных языков (каковым является Python) была бы функция is_point(region), проверяющая, является ли входной регион точкой. Но для рассматриваемой нами задачи point гораздо полезнее: например, преобразование \((x\mapsto [x,x])\), сопоставляющее точке числовой прямой отрезок, состоящий только из этой точки, — типичный пример функции point. Такие преобразования нам придётся делать. А вот проверять, является ли результат такого преобразования точкой-как-регионом, уже не понадобится, так как ответ заранее известен.

Дерево регионов

Дерево регионов — дерево, у которого в каждом узле (будь то лист или ветка) хранится регион (вместе с какой-либо дополнительной информацией), причём регион ветки является объединением регионов поддеревьев.

Как было сказано ранее, основное назначение дерева регионов — эффективно выполнять геометрические запросы. Заметим, что пока мы так и не формализовали понятие геометрического запроса. Исправляемся:

## на вход -- список пар (точка,значение)
def query_list(region, pv):
    good = [v for (p,v) in pv 
              if contains(region,point(p))]
    return combine(good)

Это определение зависит от функции combine. Будем считать, что она нам также дана. От неё мы будем требовать лишь ассоциативности. Это означает, что если разбить входной список на несколько (с сохранением относительного порядка элементов), применить к каждому combine, а затем применить combine к списку результатов, получится то же самое, как если бы combine была применена к исходному списку. Формально это означает, что равны результаты следующих двух формул:

• combine([combine(x) for x in xs])
• combine([y for x in xs for y in x])

Также встречается свойство combine([x]) == x, которое часто включают в понятие ассоциативности. Нам же будет удобно не требовать его выполнения. Например, операция «сложить все входные числа по модулю 42» с нашей точки зрения является ассоциативной.

Задача эффективного выполнения геометрического запроса состоит в реализации пары таких функций

preprocess(pv)
query(region,data)

что выполнено

query_list(region,pv) == query(region,preprocess(pv))

Будем считать, что мы достигли цели, если

data = preprocess(pv)
for i in range(N): query(r[i],data)

начиная с некоторого N выполняется быстрее, чем

for i in range(N): query_list(r[i],pv)

В идеале сделать так, чтобы первый пример тратил в среднем (на одну итерацию цикла) время, пропорциональное логарифму количества данных.

Построение дерева сверху и снизу

Зададимся некоторой моделью дерева с функцией extract, которая по своему результату эквивалентна следующему определению:

def extract(t):
    return reduce(t, lambda x: x, lambda x,y: x)
## _именно такое_ определение неэффективно из-за того, 
## что reduce проходится по поддеревьям, хотя они вообще 
## не влияют на результат

Дерево регионов строится очень просто. Либо рекурсией (это называется «сверху вниз»):

def combine_trees(trees):
    region = join([extract(t)[0] for t in trees])
    val = combine([extract(t)[1] for t in trees])
    
    return branch( (region,val), trees )
    

def topdown_tree(b,l,pv):
    if len(pv) <= l:
        trees = [leaf( (point(p),v) ) for (p,v) in pv]
    else:
        d = (len(pv)+b-1) // b
        trees = [topdown_tree(b,l,pv[i:i+d]) for i in range(0,len(pv),d)]
    
    return combine_trees(trees)

Либо же циклом («снизу вверх»):

def bottomup_tree(b,l,pv):
    if len(pv) == 0: return combine_trees([])

    leaves = [leaf( (point(p),v) ) for (p,v) in pv]

    trees = [combine_trees(leaves[i:i+l]) for i in range(0,len(pv),l)]
    
    while len(trees) > 1:
        trees = [combine_trees(trees[i:i+b]) for i in range(0,len(trees),b)]

    return trees[0]

На практике чаще встречается первый способ: если операция combine коммутативна (то есть её результат не зависит от порядка элементов в списке), то засчёт правильного распределения точек по регионам можно добиться маленького размера их пересечений (что, как мы увидим ниже, сильно убыстряет запросы). Управлять же распределением, строя дерево снизу вверх, сильно труднее, чем при построении сверху вниз (особенно легко это увидеть в многомерных пространствах: такие структуры как квадродерево или же бинарное разбиение пространства тривиально строятся сверху вниз, но совершенно непонятно на первый взгляд, как их строить снизу вверх).

Геометрический запрос к дереву

Нам понадобится функция subtrees, возвращающая список поддеревьев входного дерева (у листа он пустой). Формальное определение для абстрактных деревьев приводить не будем, поскольку одним катаморфизмом здесь не обойтись (нужно катаморфно преобразовать дерево к удобной модели, в ней взять поддеревья, каждое из которых катаморфизмом этой самой удобной модели преобразовать обратно к абстрактной).

В свете всего предыдущего геометрический запрос к дереву регионов совершенно тривиален:

def query_tree(region, tree):
    r,v = extract(tree)

    if contains(region,r): return v
    if disjoint(region,r): return combine([])

    return combine([query_tree(region, t) for t in subtrees(tree)])

Дерево отрезков

Дерево отрезков является модификацией дерева минимумов из предыдущего раздела. Оно является деревом регионов для следующего набора операций:

def join(segments):
    nonempty = [s for s in segments if s != None]
    if len(nonempty) == 0: return None

    a = min([x for (x,y) in nonempty])
    b = max([y for (x,y) in nonempty])

    return (a,b)

def contains(a,b): return join([a,b]) == a

def point(x): return (x,x)

def disjoint(a,b): 
    if a == None or b == None: return True
    
    a1,a2 = a
    b1,b2 = b
    return b2 < a1 or a2 < b1

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

Также заметим, что дерево отрезков вполне можно строить снизу вверх: в тех языках программирования, которые позволяют управлять расположением данных в памяти, построение снизу вверх позволяет все узлы одного уровня хранить в одном массиве — такой способ хранения неплохо ложится на архитектуру современных компьютеров, обеспечивая повышенное быстродействие за счёт возможности хранить большие куски дерева в кэш-памяти.

Обобщённые запросы и динамизация

Деревья регионов в том виде, в котором они изложены выше, являются статическими: в них нельзя добавлять новые данные или же удалять уже имеющиеся. К счастью, с удалением данных ситуация решается очень просто:

def remove_from_tree(region, tree):
    r,v = extract(tree)

    if contains(region,r): return None
    if disjoint(region,r): return tree

    trees = [remove_from_tree(region, t) for t in subtrees(tree)]
    return combine_trees([t for t in trees if t != None])

Как нетрудно заметить, что эта функция, что функция query являются частными случаями более общей схемы:

def gquery_tree(f,g,c,region,tree):
    r,v = extract(tree)
    
    if contains(region,r): return f(tree)
    if disjoint(region,r): return g(tree)

    return c([gquery(f,g,c,region, t) for t in subtrees(tree)])

А именно, можно использовать следующие альтернативные определения:

def query_tree(region, tree):
    return gquery_tree(lambda t: extract(t)[1], lambda t: combine([]), combine)

def remove_from_tree(region, tree):
    def combine_nonempty(ts):
        return combine_trees([t for t in ts if t != None])

    return gquery_tree(lambda t: None, lambda t: t, combine_nonempty)

Но мы отвлеклись: изначально мы обсуждали проблему динамизации статического дерева. Удалять данные мы научились. Ну а добавлять, на самом деле, уже умели.

Конечные автоматы

Особенности парсерного подхода к обработке данных

Во второй интерлюдии мы обсуждали разбор выражений при помощи парсеров — механизмов, преобразующих куски текста в какие-то данные. Мы увидели, что, соединяя простые парсеры при помощи комбинаторов, можно добиться весьма сложных схем течения и преобразования данных. Основной недостаток подхода, основанного на комбинировании парсеров — монолитность результата их комбинирования: сложный парсер, собранный из простых, невозможно разобрать обратно на составляющие его части, не прибегая к манипуляциям вида «установим внутреннюю структуру, скормив парсеру много разных данных и сопоставив результаты его работы».

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

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

Автоматы

У любого сложного парсера в любой момент в процессе обработки текста есть «внутреннее состояние» — текущий «атомарный» парсер вместе со всеми существенными данными, распознанными к настоящему моменту. Работа парсера заключается в отрезании от текста некоторого куска (зависящего от текущего состояния) и следующей за этим смене внутреннего состояния (возможно, на то же самое).

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

\[ t: S\times A\to S \]

где \(S\) — множество всевозможных внутренних состояний, а \(A\) — алфавит (множество всевозможных символов, из которых можно составлять текст). Такое отображение и называется термином автомат (точнее, детерминированный автомат).

Интересно сравнить эту модель с моделью парсера — парсер (если временно закрыть глаза на поддержку возможности неудачного распознавания) описывается отображением

\[ p: T \to B\times T \]

где \(T\) — множество всевозможных внешних состояний (текстов), а \(B\) — множество возможных результатов распознавания.

Двойственность здесь наблюдается как минимум в трёх аспектах:

• у автоматов множество несостояний находится со стороны входа отображения, а у парсеров — со стороны выхода
• сами несостояния в случае автоматов — то, что забирается (из внешних состояний), а в случае парсеров — то, что добавляется (во внутреннее состояние)
• а состояния в одном случае внешние, а в другом — внутренние

Далее мы будем рассматривать только конечные автоматы — такие, у которых множество состояний и алфавит конечны.

Детерминированные конечные автоматы

Ещё раз напомним, что детерминированным конечным автоматом (далее ДКА) называется произвольное отображение \(t:S\times A\to S\), для которого множества \(S\) и \(A\) конечны. Множество \(S\) называется множеством состояний автомата, а \(A\) — алфавитом.

Обработка текста

Пусть \(a=a_0a_1a_2\ldots\) — текст (то есть последовательность элементов множества \(A\)). По тексту и начальному состоянию \(s_0\) можно построить последовательность \(s_0s_1s_2\ldots\) по следующему правилу:

\[ s_{n+1} = t(s_n, a_n) \]

Последний элемент этой последовательности называется результатом работы автомата на тексте \(a\). Функция вычисления результата работы автомата может выглядеть, например, так:

def run_dfa(dfa, s0, text):
    s = s0
    for a in text: s = dfa(s, a)
    return s

Иногда начальное состояние \(s_0\) включают в понятие автомата, но мы это делать не будем.

Примеры автоматов

Поиск символа

При помощи конечного автомата можно тривиально определить, входит ли некоторый символ в текст:

def search_for_char_dfa(x):
    return (lambda s, a: (s or a == x))

У такого автомата два состояния: True и False.

Подсчёт количества символов

Можно подсчитать количество символов по какому-нибудь модулю:

def count_chars_modulo(x, n):
    def dfa(s, a):
        if a == x: return (s+1)%n
        return s

    return dfa

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

def count_chars(x, n):
    def dfa(s, a):
        if a == x: return s+1
        return s

    return dfa

Поиск последовательности

Вот такой автомат определяет, есть ли в тексте последовательность xy:

def find_xy(s, a):
    if s == 2: return s
    if s == 1:
        if a == 'y': return 2
        return 0

    if a == 'x': return 1
    return 0

Если автомат остановился в состоянии 2, это означает, что искомая последовательность присутствует в тексте.

Моделирование автомата словарём

Во всех вышеприведённых примерах автомат моделировался явными условными переходами. Для сколько-нибудь крупных автоматов такой способ, очевидно, неудобен. Существенно удобнее строить автомат по его графику, закодированному словарём:

def dfa_from_dict(d):
    return (lambda s,a: d[s][a])

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

Автомат Кнута-Морриса-Пратта

В качестве иллюстрации процедуры последовательного построения автомата приведём распространённый алгоритм поиска подтекста внутри текста. А именно, построим автомат, который определяет, какой наидлиннейший префикс искомого текста совпадает с хвостом входного текста. Например, для искомого текста foobar и входного текста barfoo автомат должен выдать foo (ну или 3, если называть состояния длиной найденного префикса).

Интересное свойство такого автомата (в отличие от автоматов со схожими, но немного другими определениями) — его можно построить рекуррентным образом:

def kmp_add_char(kmp_dict, x):
    n = len(kmp_dict) - 1
    kmp_dict[n+1] = {}
    old = kmp_dict[n][x]
    kmp_dict[n][x] = n+1
    
    for a in kmp_dict[old]:
        kmp_dict[n+1][a] = kmp_dict[old][a]

def kmp_dfa(alphabet, needle):
    kmp_dict = {0:{}}
    
    for a in alphabet:
        kmp_dict[0][a] = 0

    for x in needle:
        kmp_add_char(kmp_dict, x)

    return dfa_from_dict(kmp_dict)

Корректность

Докажем, что этот автомат (если его запускать, начиная с состояния 0) удовлетворяет сформулированному нами определению. Точнее, приведём краткий набросок доказательства (аккуратное «лобовое» доказательство довольно сложно).

Будем вести индукцию по длине искомого текста. Предположим, что для всех текстов needle длины, меньшей \(N\), автомат kmp_dfa(alphabet,needle) делает то, что нужно (а именно, выдаёт самое большое k, для которого needle[:k] совпадает с хвостом входного текста).

Если \(N=0\), то наш автомат всегда выдаёт 0, что, очевидно, удовлетворяет его определению. Если \(N\gt0\), проведём индукцию по длине входного текста.

С пустым входным текстом всё хорошо. Если же в тексте есть хотя бы один символ, этот текст можно представить в виде T+x, где x — этот самый последний символ. По индуктивному предположению, обработав текст T, автомат остановится в состоянии, соответствующем наиболее длинному хвосту T, являющемуся префиксом needle. При этом автомат мог остановиться в одном из трёх состояний:

• одно из первых \(N-2\) состояний
• состояние \(N-1\)
• состояние \(N\)

Посмотрим, как среагирует автомат на последний символ x. В первом случае мы находимся в пределах автомата для слова needle[:N-1], который по предположению внешней индукции делает то, что нужно. Во втором случае тоже всё хорошо: если x == needle[N-1], то мы перейдём в состояние \(N\); если же нет, то мы опять в пределах автомата для слова needle[:N-1].

Единственный нетривиальный случай — если мы сейчас в состоянии \(N\). Тут нужно разобрать два подслучая.

Подслучай первый: после обработки символа x длина префикса остаётся N. Но так бывает только тогда, когда needle состоит из одинаковых символов, равных x. Нетрудно проверить, что для такого автомата переход из состояния N по символу x ведёт в N.

Подслучай второй: длина префикса изменяется. Но тогда автомат должен остановиться в том же состоянии, в котором остановился бы автомат для needle[:N-1]. Отмотаем на два шага назад: мы окажемся в состоянии, отличном от N (и в том же, в котором бы остановился автомат для needle[:N-1]). А теперь обратно пройдём на два шага вперёд. По построению мы окажемся там же, где оказался бы автомат для needle[:N-1].

Всё.

Недетерминированные конечные автоматы

Приведённое в конце прошлого раздела доказательство корректности автомата Кнута-Морриса-Пратта было весьма сложным (и, мягко говоря, очень наброскообразным). Оказывается, обобщив понятие детерминированного автомата, можно кардинально упростить подобные доказательства.

Недетерминированные автоматы

Недетерминированным автоматом (далее НДА) называется отображение \(t:S\times A\to PA\), где \(PA\) — множество всех подмножеств множества \(A\). Результатом работы НДА (на начальном множестве \(S_0\) и тексте \(a\)) является последний элемент последовательности

\[ S_{n+1} = \cup \{ t(s)\,|\, s\in S_n \} \]

Результат работы НДА можно вычислить функцией

def run_nda(nda, s0, text):
    s = set(s0)
    for a in text: s = set([y for x in s for y in nda(x,a)])
    return s

Нетрудно заметить, что НДА можно превратить в ДА вида \(PS\times A\to PA\) функцией

def determinize_nda(nda):
    def da(s,a):
        return set([y for x in s for y in nda(x,a)])

    return da

Корректность автомата КМП

Теперь приведём простое (и существенно более формальное) доказательство корректности работы автомата КМП. Нам потребуется лишь одинарная индукция (по длине needle). Пусть \(T\) — ДКА для слова needle[:N-1], а также пусть \(Z\) — последний символ needle.

Рассмотрим НДА, определённый следующим образом:

\[ t(x,a) = \{ T(x,a) \},\; x \lt N-1 \]

\[ t(N-1,x) = \{ T(N-1,x) \},\; x\ne Z \]

\[ t(N-1,Z) = \{ T(N-1,Z), N \} \]

\[ t(N,x) = \{\} \]

Если этот автомат запустить на начальном состоянии \(\{0\}\), то про его результат очевидно, что искомая длина префикса является наибольшим из состояний результата.

При этом единственный результат, содержащий более одного состояния, выглядит как \(R=\{ T(N-1,Z), N \}\). Нетрудно заметить, что по символу x такое состояние переходит в \(t(T(N-1,Z),x)\). Поэтому, если мы назовём состояние R числом \(N\), мы получим детерминированный автомат

\[ t(x,a) = T(x,a),\; x \lt N-1 \]

\[ t(N-1,x) = T(N-1,x),\; x\ne Z \]

\[ t(N-1,Z) = N \]

\[ t(N,x) = t(T(N-1,Z), x) \]

Именно такой автомат и строится функцией kmp_dfa.

Регулярные выражения

Двузначные НДА

Пусть выделено некоторое подмножество T состояний НДА. Будем называть состояния этого подмножества терминальными. Также пусть выделено одно из состояний НДА, которое мы будем называть начальным.

Будем говорить, что такой НДА распознаёт текст X, если текст X переводит этот НДА из начального состояния в подмножество, пересекающееся с T. Например, если взять автомат КМП (со стандартным начальным состоянием), построенный по тексту Y, и объявить его наибольшее состояние терминальным, то такой автомат будет распознавать те и только те тексты, которые заканчиваются на Y.

Автомат с множеством терминальных состояний мы будем дальше называть двузначным.

Регулярные выражения, математическая сторона

Есть важный класс двузначных НДКА, называемый регулярными автоматами. Этот класс обладает следующими свойствами:

1. Регулярные автоматы обладают текстовым представлением.
2. Любой двузначный конечный автомат эквивалентен (в смысле равенства множеств распознаваемых текстов) некоторому регулярному.

Понятие регулярного автомата проще всего определить, определив текстовое представление, называемое регулярным выражением, и изложив алгоритм построения автомата по текстовому представлению.

Регулярное выражение — это формула, составленная из букв алфавита и трёх операций:

1. бинарная конкатенация
2. бинарная дизъюнкция
3. звёздочка

Семантика этих операций такова:

1. выражение AB распознаёт те и только те тексты, которые имеют вид XY, где X распознаётся A, а Y распознаётся B
2. выражение A|B распознаёт те и только те тексты, которые распознаются хотя бы одним из A или B
3. выражение (A)* распознаёт те и только те тексты, которые можно представить в виде конечной (возможно, пустой) последовательности текстов, каждый из которых распознаётся A

Приведём несколько примеров.

1. Выражение aba распознаёт только текст aba.
2. Выражение ab*a распознаёт тексты aa, aba, abba, abbba и т.д. Стоит отметить, что если звёздочка относится только к одной букве, скобки традиционно не ставятся.
3. Выражение ab*|b*a распознаёт тесты a, ab, abb, abbb и т.д., а также — тексты ba, bba, bbba и т.д.

Осталось описать соответствие между регулярными выражениями и автоматами. Можно, например, применить алгоритм Томпсона для построения двузначного НДКА по регулярному выражению.

Регулярные выражения, практическая сторона

Почти во всех языках программирования есть поддержка того или иного диалекта регулярных выражений. Регулярные выражения используются для поиска в текстах подтекстов. Здесь мы поговорим о той части синтаксиса регулярных выражений, которая встречается почти во всех их реализациях.

Сперва отметим главную особенность регулярных выражений в большинстве языков программирования: поиск в тексте T по регулярному выражению R ищет какое-нибудь разбиение текста T=AXB, в котором X распознаётся выражением R. Выбрать конкретное разбиение в случае, если их несколько, нельзя (компромисс в целях скорости поиска), но можно ограниченным образом контроллировать искомое разбиение. Основные способы контроля следующие:

1. выражения ^R, R$ и ^R$ ищут разбиения вида XB, AX и X соответственно
2. есть два вида звёздочки * и *?: жадная и ленивая; выражение (S)*Q выбирает тот среди распознаваемых текстов, в котором часть, распознанная (S)*, распознаётся наибольшим возможным количеством повторений S; ленивая же звёздочка соответствует наименьшему возможному количеству повторений S
3. есть глобальный режим, позволяющий найти несколько непересекающихся разбиений (то есть таких, части которых, распознаваемые выражением, не пересекаются по положению)

Кратко опишем особенности синтаксиса регулярных выражений по сравнению с математической моделью:

1. обычные скобки — это пара (?: и ); пара же ( и ) — это т.н. захватывающие скобки; исполнитель выражения с захватывающими скобками запоминает ту часть текста, которая была распознана подвыражением, заключённым в эти скобки

2. есть целое семейство унарных операторов, называемых кванторами: {m} -- ровно m вхождений, {m,n} -- от m до n вхождений, {m,} -- хотя бы m вхождений; в их терминах определяются *, +, ? как {0,}, {1,} и {0,1} соответственно

3. точка . распознаёт любую одну букву

4. т.н. классы символов, заключаемые в квадратные скобки, задают выражение, распознающее одну букву из некоторого подмножества алфавита

5. есть обратные ссылки (back references), распознающие участки, совпадающие с участками, захваченными скобками

Про последний пункт стоит сказать отдельно. Регулярные выражения не предназначены для разбора рекурсивных грамматик! Разбирать рекурсивные грамматики регулярными выражениями сложно и неэффективно! Если требуется разбор рекурсивных грамматик, следует прибегнуть к чему-то другому (например, к комбинаторам парсеров). Ни при каких обстоятельствах при разборе выражений не нужно использовать обратные ссылки! (А вот при поиске и замене они вполне полезны.)

В заключение дадим рекомендации по увеличению скорости поиска:

1. по возможности использовать незахватывающие скобки
2. в зависимости от конкретной реализации регулярных выражений, иногда имеет смысл заменить все жадные кванторы на ленивые (ленивые кванторы соответствуют стандартной семантике пошагового исполнения НДКА)
3. не пользоваться обратными ссылками: регулярные выражения не предназначены для разбора рекурсивных грамматик!

Примеры выражений

Для выделения имени сервера из интернет-адреса (кроме почтовых адресов) можно использовать любое из следующих выражений:

^http(?:|s):/+(.*?)(?:$|/)
^http(?:|s):/+([^/]*)

С некоторой осторожностью можно использовать выражение

^http(?:|s):/+([a-zA-Z0-9\-.]*)

Нечто подобное используют браузеры от Microsoft, в результате чего некоторые не удовлетворяющие стандарту имена серверов (например, использующие подчёркивание), воспринимаются некорректно.

Для распознания некоторого строгого надмножества почтовых адресов вида foobar@baz можно использовать выражение вида

^(.*)@([a-zA-Z0-9\-.]*)

Важно заметить, что первый квантор здесь жадный: внутри локальной части foobar вполне допустим символ @.

К сожалению, совсем корректное распознание почтовых адресов представляет огромные сложности из-за очень неудачного стандарта RFC 822. Вот — пример более правильного регулярного выражения (для удобства чтения оно разбито на строчки):

(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ 
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\0
31]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\
](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

Следует отметить, что даже оно не удовлетворяет стандарту. В частности, оно не умеет обрабатывать вложенные комментарии.

Регулярные выражения в Python

Для работы с регулярными выражениями используется модуль re, который можно импортировать командой

import re

Регулярное выражение можно использовать двумя способами:

1. скомпилировав его функцией re.compile
2. используя функции re.search, re.match, re.fullmatch

Само регулярное выражение для этих функций рекомендуется задавать сырым текстовым литералом (например, r'foo\.' вместо 'foo\\.'). Сырые литералы отключают питоновское экранирование, которое легко перепутать с экранированием в рамках языка регулярных выражений.

Если выражение было скомпилировано, у результата компиляции есть методы search, match и fullmatch, аналогичные функциям re.search, re.match и re.fullmatch. Эти функции работают так:

1. search ищет разбиение вида AXB, где X удовлетворяет выражению
2. match ищет разбиение вида XB, где X удовлетовряет выражению
3. fullmatch просто распознаёт текст при помощи выражения

Результат этих функций — либо None, либо специальный объект, по которому можно получить информацию о результате распознавания. Например, у этого объекта есть метод groups, возвращающий иммутабельный список захваченных скобками подтекстов.

Практическое задание по анализу файла

В архиве по ссылке находится фрагмент реального журнала запросов к веб-серверу и файл с текстом задания.

Напомним, что считать файл построчно можно выражением вида

with open(имя_файла, 'r') as f:    
    for line in f:                   
        ...