Логарифмическая память: что можно сделать с несколькими указателями

Если ты скажешь, что разрешено алгоритму с логарифмической памятью, проверишь палиндром двумя указателями и объяснишь, почему достижимость лежит в NL и сколько памяти нужно случайному блужданию, - листай до «Теперь сам».

Как думаешь, что можно узнать о файле, не загружая его

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

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

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

Читатель в архиве. Документы нельзя выносить, копировать и подчёркивать; с собой - только несколько закладок и умение считать в уме. Закладка - это номер страницы.

С закладками можно сравнить первую страницу с последней, вторую с предпоследней, посчитать страницы с печатью. Нельзя составить конспект: записывать негде. Всё, что читатель знает в данный момент, - где лежат его закладки и одно-два числа.

Механизм: что разрешено и что из этого выходит

Машина с логарифмической памятью имеет ленту со входом, доступную только для чтения, и рабочую ленту длиной порядка log n. Номер позиции во входе длины n занимает log₂ n бит; значит, рабочая память - это постоянное число таких номеров и счётчиков. Длинный ответ, например сумму двух чисел, машина пишет на отдельную ленту, доступную только для записи; в счёт памяти она не идёт.

можно                                    нельзя
держать несколько указателей на вход     скопировать вход
                                         или его заметную часть
считать до многочлена от n: счётчик из   пометить посещённые элементы
c · log n бит считает до n в степени c   (это n бит)
перечитывать вход сколько угодно раз     держать стек или очередь
                                         длиной порядка n
вызывать такую же экономную              запоминать промежуточный
подпрограмму                             результат длиной n

Класс L - задачи, решаемые такой детерминированной машиной. Время при этом полиномиально: конфигураций - многочлен от n.

Класс NL - то же с угадыванием. Главный пример - достижимость в ориентированном графе: есть ли путь из a в b. Недетерминированная машина держит номер текущей вершины и счётчик шагов; на каждом шаге угадывает следующую вершину и проверяет по входу, что такое ребро есть. Дошла до b - принять; счётчик превысил n - отвергнуть. Память - два числа. Достижимость полна для NL: всё из этого класса к ней сводится, причём переводом, который сам работает в логарифмической памяти.

Что известно:

L ⊆ NL ⊆ P           достижимость решается обходом
                     за полиномиальное время
NL в памяти log² n   рекурсия по серединам из прошлого урока
NL = co-NL           «пути нет» тоже проверяется с угадыванием
                     в логарифмической памяти (1987)
L = NL ?             неизвестно

Класс co-NL - дополнения задач из NL. Идея равенства: считать, сколько вершин достижимо за 1, 2, …, n шагов; каждое следующее число получают из предыдущего, заново угадывая пути и не храня ничего, кроме счётчиков. Зная точное число достижимых, можно угадать их все по очереди и убедиться, что цели среди них нет. Пропустить вершину при этом не выйдет: если угадано меньше достижимых, чем их есть, счёт не сойдётся с известным числом, и такая попытка отвергается.

Для неориентированных графов достижимость лежит в L - это доказано в 2004 году. А раньше был известен вероятностный способ: случайное блуждание из прошлого раздела. Идти по случайному ребру, помня только текущую вершину; если цель в той же компоненте, блуждание на неё наткнётся.

Правило

Класс L - задачи, решаемые с входом только для чтения и рабочей памятью порядка log n: несколько указателей и счётчиков. NL - то же с угадыванием; достижимость в ориентированном графе полна для NL. L ⊆ NL ⊆ P, NL замкнут относительно дополнения; совпадают ли L и NL, неизвестно.

Разбор: палиндром на двух указателях

Функция palindrom_ukazatelyami не копирует строку и не переворачивает её: она держит два номера позиций и сдвигает их навстречу. В выводе - длина строки, ответ с числом сравнений, число бит под два указателя и число бит, которое заняла бы копия строки по байту на символ.

def palindrom_ukazatelyami(stroka):
    levyj = 0
    pravyj = len(stroka) - 1
    sravnenij = 0
    while levyj < pravyj:
        sravnenij = sravnenij + 1
        if stroka[levyj] != stroka[pravyj]:
            return [False, sravnenij]
        levyj = levyj + 1
        pravyj = pravyj - 1
    return [True, sravnenij]

def bit_na_chislo(n):
    bit = 0
    while n > 0:
        bit = bit + 1
        n = n // 2
    return bit

for dlina in [8, 64, 512, 4096]:
    stroka = "ab" * (dlina // 4) + "ba" * (dlina // 4)
    print(dlina, palindrom_ukazatelyami(stroka),
          2 * bit_na_chislo(dlina - 1), dlina * 8)

8 [True, 4] 6 64
64 [True, 32] 12 512
512 [True, 256] 18 4096
4096 [True, 2048] 24 32768

Строка выросла в 512 раз - с 8 до 4096 символов. Копия выросла во столько же: с 64 до 32 768 бит. Два указателя - с 6 до 24 бит (наибольший номер позиции на единицу меньше длины): по шесть бит на каждое увеличение строки в восемь раз, по три на указатель. Время при этом осталось линейным: n / 2 сравнений.

Привычная запись «строка равна себе перевёрнутой» создаёт вторую строку и в логарифмическую память не укладывается. Различие не видно на строках в килобайт и становится решающим, когда «строка» - файл или поток с диска.

Сравни с машиной Тьюринга из главы о моделях: на одной ленте палиндром стоил n² шагов, потому что головке приходилось бегать. Программа обращается к символу по номеру за одно действие, и беготни нет; ленточная машина дошла бы до той же позиции, отсчитывая шаги. В обоих случаях хранить нужно сами номера - те самые log n бит.

Разбор: блуждание помнит одну вершину

Неориентированный граф из двенадцати вершин и двух частей: вершины 0-7 связаны между собой, вершины 8-11 - отдельно. Функция bluzhdanie идёт из start по случайным рёбрам, пока не попадёт в cel или не исчерпает предел шагов. Предел - 2 · m · (n − 1): в прошлом разделе показано, что среднее время обхода связного графа случайным блужданием не больше этого числа.

import random

def bluzhdanie(sosedi, start, cel, predel):
    v = start
    shagov = 0
    while v != cel and shagov < predel:
        v = sosedi[v][random.randrange(len(sosedi[v]))]
        shagov = shagov + 1
    return [v == cel, shagov]

n = 12
sosedi = []
for v in range(n):
    sosedi.append([])
ryobra = [[0, 1], [1, 2], [2, 3], [3, 0], [3, 4],
          [4, 5], [5, 6], [6, 7], [7, 4]]
ryobra = ryobra + [[8, 9], [9, 10], [10, 11], [11, 8]]
for r in ryobra:
    sosedi[r[0]].append(r[1])
    sosedi[r[1]].append(r[0])
predel = 2 * len(ryobra) * (n - 1)
random.seed(21)
itogi = []
for popytka in range(6):
    itogi.append(bluzhdanie(sosedi, 0, 6, predel))
print(predel)
print(itogi)
print(bluzhdanie(sosedi, 0, 9, predel), bluzhdanie(sosedi, 0, 9, predel))

286
[[True, 6], [True, 18], [True, 38], [True, 4], [True, 88], [True, 40]]
[False, 286] [False, 286]

Шесть блужданий из вершины 0 в вершину 6 дошли за 6, 18, 38, 4, 88 и 40 шагов - все в пределах 286. До вершины 9 блуждание не доходит: она в другой части графа.

Память алгоритма - номер текущей вершины и счётчик шагов: два числа, порядка log n бит каждое. Список sosedi - это вход: его только читают, в рабочую память он не входит. Никаких пометок. Плата двойная. Время - до m · n шагов вместо m у обхода. И ответ «не дошёл» не окончателен: блужданию могло не повезти. Ответ «дошёл» верен всегда. Ошибка односторонняя, и её вероятность уменьшается повторением. Число 2m(n − 1) - граница среднего времени; по неравенству Маркова за удвоенное среднее блуждание не доходит до достижимой цели с вероятностью не больше одной второй, за двадцать таких попыток подряд - не больше одной миллионной. Программа берёт одинарный предел, посчитанный по всему графу, и такой гарантии не даёт; здесь он показывает только порядок величины.

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

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

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

Рекурсия по всему входу. Рекурсивный обход списка или дерева глубиной n держит стек длиной n. Логарифмической памяти он не соответствует, даже если локальных переменных две.

«Мало памяти - значит быстро». Экономия памяти оплачивается повторным чтением входа. Алгоритм с логарифмической памятью полиномиален, но его показатель степени бывает больше, чем у алгоритма с пометками.

Ответ «не найдено» у случайного алгоритма читают как «нет». У блуждания ошибка возможна только в эту сторону; её вероятность нужно назвать и уменьшить повторением.

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

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

Приём двух указателей. Палиндром, слияние отсортированных последовательностей, поиск пары с заданной суммой в отсортированном массиве, сравнение версий - решения, в которых вместо вспомогательных структур стоят два индекса.

Запросы к базам данных. Простые запросы на выборку и соединение вычисляются в логарифмической памяти, а для задач этого класса известны быстрые параллельные алгоритмы; запрос с достижимостью - «все подчинённые сотрудника на любом уровне» - уже выходит за эти рамки и требует рекурсии.

Теперь сам

1. Сколько бит нужно под указатель на позицию в строке длиной миллион символов?
2. Можно ли в логарифмической памяти проверить, что в строке поровну букв a и b?
3. Почему проверка скобок трёх видов обычным способом не укладывается в логарифмическую память?
4. Что хранит недетерминированная машина, решающая достижимость?
5. Блуждание из a не дошло до b за отведённое число шагов. Что можно утверждать?