Очередь реального времени: расписание ленивой работы

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Очередь обслуживает запросы с жёстким ограничением времени. За тысячу операций средняя стоимость прекрасная, но одна из них разворачивает длинный список и опаздывает. Можно ли начать подготовку нового переднего списка заранее? Простой ответ «сделаем лениво» неполон: если накопить слишком много ленивых обещаний, одна операция вычислит их все.

На что это похоже

Представь кухню с двумя стопками тарелок. Новые кладут в заднюю стопку, выдача идёт из передней. Когда передняя кончается, нужно перевернуть заднюю. Вместо большого переворота в последний момент повар готовит новую стопку понемногу при каждом заказе. Расписание следит, чтобы подготовка закончилась до последней доступной тарелки. Сохранённые версии очереди разделяют уже выполненную подготовку.

Механизм: от определения к алгоритму

Представление очереди - тройка (f,r,s): передний ленивый поток, задний строгий список в обратном порядке и поток расписания. Поддерживается соотношение |s|=|f|-|r|. Добавление увеличивает задний список, удаление сокращает передний; обе операции уменьшают запас расписания на один и затем исполняют один его шаг.

Если расписание непусто, возьми его хвост. Получение этого хвоста вынуждает ограниченную часть отложенной работы. Если расписание пусто, после текущего изменения задняя часть стала длиннее передней ровно на один. Начни ленивое вращение rotate(f,r,empty) и назначь новый передний поток одновременно новым расписанием. Заднюю часть очисти. Вращение выдаёт один передний элемент и рекурсивное обещание продолжения, постепенно перенося элементы заднего списка в аккумулятор.

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

Почему худший случай постоянный? Само тело одной операции делает постоянное число манипуляций со списками и вынуждает лишь постоянное число задержек. Расписание гарантирует, что зависимости очередной задержки уже подготовлены: она не запускает длинную цепочку ещё не выполненных вращений. Это доказательство опирается на структуру rotate и соотношение длин, а не на эксперимент с хорошим средним числом шагов.

Термин «реального времени» здесь относится к числу элементарных действий структуры. Сборщик мусора, выделение памяти, аппаратные промахи и планировщик могут дать паузу в реальной программе на Python. Такой код не даёт сам по себе инженерной гарантии максимальной задержки в микросекундах. Модель стоимости и требование приложения нужно различать, даже когда в обоих встречается одинаковое словосочетание.

Правило

Разбивай вращение на мемоизированные шаги и исполняй расписание при каждой операции; ленивость без контроля зависимостей не доказывает O(1) в худшем случае.

Разбор: проследим вычисление

Ниже связные строгие списки представлены парами, а потоки - объектами Lazy. Создание новой версии не копирует весь хвост. Считаем только впервые вычисленные задержки, не время Python; проверим сохранённую старую версию после множества новых операций. Отсутствие дополнительных потоков исполнения подчёркивает, что «подготовка заранее» делается самими операциями очереди, а не фоновой задачей.

class Lazy:
    forced = 0
    def __init__(self, thunk):
        self.thunk, self.done, self.value = thunk, False, None
    def force(self):
        if not self.done:
            Lazy.forced += 1
            self.value = self.thunk()
            self.done, self.thunk = True, None
        return self.value

empty = Lazy(lambda: None)
empty.force()

def cons(x, tail):
    return Lazy(lambda: (x, tail))

def rotate(f, r, a):
    def step():
        front = f.force()
        if front is None:
            assert r is not None and r[1] is None
            return r[0], a
        x, xs = front
        y, ys = r
        return x, rotate(xs, ys, cons(y, a))
    return Lazy(step)

def execute(f, r, schedule):
    cell = schedule.force()
    if cell is not None:
        return f, r, cell[1]
    new = rotate(f, r, empty)
    return new, None, new

def push(q, value):
    f, r, s = q
    return execute(f, (value, r), s)

def pop(q):
    f, r, s = q
    value, tail = f.force()
    return value, execute(tail, r, s)

q = (empty, None, empty)
peak = 0
for i in range(100):
    before = Lazy.forced
    q = push(q, i)
    peak = max(peak, Lazy.forced - before)
old = q
for i in range(50):
    before = Lazy.forced
    value, q = pop(q)
    assert value == i
    peak = max(peak, Lazy.forced - before)
assert pop(old)[0] == 0
assert pop(q)[0] == 50
print('старая версия', pop(old)[0], 'новая', pop(q)[0])
print('максимум новых задержек за операцию', peak)
assert peak <= 3

старая версия 0 новая 50
максимум новых задержек за операцию 1

Разбор: где проходит граница

У обычной двухсписочной очереди серия добавлений длины n без удалений накапливает задний список. Первое удаление способно оплатить весь его разворот за Θ(n). У расписания работа начинается раньше и распределяется по операциям. Если же отключить мемоизацию, несколько обращений к одной старой версии снова вычислят одинаковый участок. Оценка по одной линейной истории перестанет описывать стоимость разветвлённого использования.

Что ломается без этого

Срез списка Python копирует хвост и делает якобы постоянную операцию линейной. Ленивый rotate, который сразу строит весь результат внутри thunk, лишь откладывает большой платёж. Расписание с неверным соотношением длин может потребовать заднюю часть неподходящей длины и нарушить базовый случай. Измерение wall-clock на коротком запуске не доказывает ограничение стоимости: нужен инвариант зависимостей.

Зачем это в работе

Такая структура полезна для функциональных симуляторов и поисков с сохранением версий, где нельзя допустить один большой алгоритмический платёж при удалении. Для обычного изменяемого FIFO в Python стандартный deque проще. Выбор персистентной очереди оправдывают совместное использование старых состояний и требование к худшему случаю, а не только желание иметь ещё одну реализацию очереди.

Теперь сам

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