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

Если ты знаешь, почему «в начало» 2-конкурентно (через число инверсий), на каком входе «с соседом» проигрывает во сколько угодно раз и почему отношение 2 нельзя улучшить, листай до «Теперь сам».

Как думаешь, какое правило осторожнее

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

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

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

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

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

Механизм: инверсии как потенциал

Модель. Доступ к элементу на позиции i стоит i. Передвинуть найденный элемент ближе к началу - бесплатно. Оптимуму разрешено всё: знать запросы заранее и переставлять соседей за 1.

Потенциал. Φ - число инверсий: пар элементов, которые в списке MTF и в списке оптимума стоят в разном порядке. Вначале списки одинаковы, Φ = 0, и Φ никогда не отрицателен - как в амортизационном анализе из раздела о рекуррентностях.

Запрос к x. У MTF он на позиции k, у оптимума на позиции i. Пусть перед x у MTF стоят v элементов, которые и у оптимума перед x, и k − 1 − v - которые у оптимума после x.

MTF платит k и переносит x в начало:
    исчезают инверсии с теми, кто у оптимума после x:  −(k − 1 − v)
    появляются с теми, кто у оптимума перед x:          +v
амортизированная цена  k + v − (k − 1 − v) = 2v + 1 <= 2i − 1
(v <= i − 1: перед x у оптимума всего i − 1 элемент)
перестановка соседей оптимумом меняет Φ не больше чем на 1 - за его счёт
итого: MTF <= 2 · OPT

Нижняя граница. Противник каждый раз просит последний элемент списка MTF. MTF платит n за запрос; неподвижный список в среднем платит (n + 1) / 2. Отношение 2n / (n + 1) стремится к двум - лучше двойки «в начало» не бывает; для любого детерминированного правила известна та же граница, но её довод сложнее.

Правило

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

Разбор: запросы с меняющейся локальностью

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

import random

def stoimost(spisok, zaprosy, pravilo):
    spisok = spisok[:]
    chastota = {}
    for x in spisok:
        chastota[x] = 0
    vsego = 0
    for x in zaprosy:
        i = spisok.index(x)
        vsego = vsego + i + 1
        chastota[x] = chastota[x] + 1
        if pravilo == "в начало":
            spisok.pop(i)
            spisok.insert(0, x)
        elif pravilo == "с соседом" and i > 0:
            spisok[i] = spisok[i - 1]
            spisok[i - 1] = x
        elif pravilo == "по частоте":
            while i > 0 and chastota[spisok[i - 1]] < chastota[x]:
                spisok[i] = spisok[i - 1]
                spisok[i - 1] = x
                i = i - 1
    return vsego

def luchshij_nepodvizhnyj(spisok, zaprosy):
    schet = []
    for x in spisok:
        schet.append([-zaprosy.count(x), x])
    schet.sort()
    poryadok = []
    for para in schet:
        poryadok.append(para[1])
    return stoimost(poryadok, zaprosy, "стоять")

random.seed(17)
spisok = list(range(10))
zaprosy = []
for blok in range(8):
    goryachie = [random.randrange(10), random.randrange(10)]
    for i in range(25):
        zaprosy.append(random.choice(goryachie + [random.randrange(10)]))
for pravilo in ["в начало", "с соседом", "по частоте"]:
    print(pravilo, stoimost(spisok, zaprosy, pravilo))
print("лучший неподвижный", luchshij_nepodvizhnyj(spisok, zaprosy))

в начало 629
с соседом 870
по частоте 977
лучший неподвижный 904

«В начало» - 629, лучше неподвижного списка, который знал все запросы заранее (904). Он подстраивается под каждый блок: два-три запроса - и горячие элементы впереди. «С соседом» продвигает их на шаг за запрос и не успевает к смене блока. «По частоте» хуже всех: горячие элементы прошлых блоков набрали обращений и стоят впереди новых.

Разбор: качели и круг

Первые запросы - «качели»: пятьдесят раз подряд элементы 9 и 8, последние в списке. Потом «круг»: десять раз элементы от 9 до 0 - так, что у MTF каждый запрос к последнему элементу.

def stoimost(spisok, zaprosy, pravilo):
    spisok = spisok[:]
    chastota = {}
    for x in spisok:
        chastota[x] = 0
    vsego = 0
    for x in zaprosy:
        i = spisok.index(x)
        vsego = vsego + i + 1
        chastota[x] = chastota[x] + 1
        if pravilo == "в начало":
            spisok.pop(i)
            spisok.insert(0, x)
        elif pravilo == "с соседом" and i > 0:
            spisok[i] = spisok[i - 1]
            spisok[i - 1] = x
        elif pravilo == "по частоте":
            while i > 0 and chastota[spisok[i - 1]] < chastota[x]:
                spisok[i] = spisok[i - 1]
                spisok[i - 1] = x
                i = i - 1
    return vsego

spisok = list(range(10))
kacheli = []
for i in range(50):
    kacheli = kacheli + [9, 8]
print(stoimost(spisok, kacheli, "в начало"),
      stoimost(spisok, kacheli, "с соседом"),
      stoimost(spisok, kacheli, "стоять"))
po_krugu = []
for povtor in range(10):
    po_krugu = po_krugu + list(range(9, -1, -1))
print(stoimost(spisok, po_krugu, "в начало"),
      stoimost(spisok, po_krugu, "стоять"))

216 1000 950
1000 550

Качели: «в начало» - 216, по два с небольшим за запрос: после первых двух обращений оба элемента впереди. «С соседом» - 1000: элементы 9 и 8 меняются местами друг с другом в самом конце списка, и каждый запрос стоит 10. Неподвижный список - 950. Удлини список до тысячи - и «с соседом» станет хуже «в начало» в сотни раз.

Круг - противник для MTF: каждый запрос к последнему элементу, 1000 против 550 у неподвижного списка. Отношение 1000 / 550 = 1,82 = 2 · 10 / 11 - ровно нижняя граница 2n / (n + 1). MTF здесь проигрывает, но не больше чем вдвое, и это предел для любого детерминированного правила.

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

Выбирают «осторожное» правило. «С соседом» на качелях платит по n за запрос - бесконечно хуже.

Считают частоту за всю жизнь. Как LFU в кеше: прошлые горячие элементы занимают начало навсегда.

Сравнивают только с неподвижным порядком. Неподвижный оптимум на меняющихся запросах хуже MTF (904 против 629); гарантия MTF - против оптимума, который тоже может двигаться.

Забывают про цену перестановки. В массиве перенос в начало стоит i сдвигов. В связном списке - O(1), поэтому эвристика естественна для списков, а в массиве её делают переносом на позицию раньше или на несколько.

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

Переупорядочивание списков по обращениям - в таблицах символов компиляторов, в цепочках хеш-таблиц (найденный элемент цепочки переносят в её начало), в кешах небольших справочников. И та же операция «в начало» стоит в сжатии: в разделе о строках преобразование MTF после BWT превращало повторы в нули. Гарантия 2 объясняет, почему эта простая эвристика не подводит на неудачных данных.

Теперь сам

1. Список a, b, c, d. Запросы d, d, c, d. Сколько заплатит «в начало»?
2. Сколько инверсий между списками a, b, c, d и b, a, d, c?
3. Почему амортизированная цена запроса у MTF не больше 2i − 1, где i - позиция у оптимума?