Список с пропусками

Список с пропусками (skip list) — вероятностная структура данных, построенная на основе связного списка. Позволяет добавлять, удалять и искать элементы за время $O(\log n)$ .

Список с пропусками состоит из слоев. Нижний слой — обычный упорядоченный связный список. Каждый более высокий уровень действует как экспресс-полоса для списков ниже.

Элемент появляется в слое выше с фиксированной вероятностью $p$ . В среднем каждый элемент появляется в $1/(1-p)$ слоях, а ожидаемое общее количество слоев равно $\log_{1/p} n + \Theta(1)$ .

Докажем, что ожидаемое количество уровней в списке с пропусками равно $\log_{1/p} n + \Theta(1)$ .

Пусть случайная величина $L(k)$ — высота $k$ -го элемента, и $H = \max\limits \{ L(1), L(2), \dotsc, L(n)\}$ — максимальная высота элементов aka высота списка.

Вероятность того, что высота элемента $k$ будет превышать $h$ равна

\prob \bigl( L(k) > h \bigr) = \sum\limits_{j=h+1}^\oo (1-p) \cdot p^{j-1} = p^h

Тогда можно оценить $\prob (H > h)$ и $\prob(H \le h)$ при фиксированном $h$ :

\prob (H \le h) = \prob \left( \bigsect_{k=1}^n \bigl\{ L(k) \;\! \le \;\! h \bigr\} \right) = \prod\limits_{k=1}^n \prob \bigl( L(k) \le h \bigr) = \bigl( 1 - p^h \bigr)^n

\prob (H > h) = 1 - \prob (H \le h) = 1 - \bigl( 1 - p^h \bigr)^n

Интересующее нас математическое ожидание равно

\expect H = \sum\limits_{h=0}^\oo \prob (H > h)

Разобьём формулу вычисления математического ожидания на две суммы: первая от $0$ до $\lfloor \log_{1/p} n \rfloor$ и вторая от $\lfloor \log_{1/p} n \rfloor + 1$ до $\oo$ .

Первая сумма легко оценивается сверху

\sum\limits_{h=0}^{\lfloor \log_{1/p} n \rfloor} \prob(H > h) \;\! \le \;\! \sum\limits_{h=0}^{\lfloor \log_{1/p} n \rfloor} 1 = \lfloor \log_{1/p} n \rfloor + 1

Со второй посложнее. Если $h \ge \lfloor \log_{1/p} n \rfloor + 1$ , то $p^h \le p^{\lfloor \log_{1/p} n \rfloor + 1} < 1/n$ . Также используем то, что при $0 \le x \le 1$ выражение $1 - (1 - x)^n \le nx$ .

\sum\limits_{h = \lfloor \log_{1/p} n \rfloor + 1}^\oo \prob(H > h) = \sum\limits_{h = \lfloor \log_{1/p} n \rfloor + 1}^\oo \Bigl( 1 - \bigl( 1 - p^h \bigr)^n \Bigr) \;\! \le \;\! \sum\limits_{h = \lfloor \log_{1/p} n \rfloor + 1}^\oo n p^h = \frac{n p^{\lfloor \log_{1/p} n \rfloor + 1}}{1-p} < \frac{n / n}{1-p} = \frac{1}{1-p}

Получили оценку сверху

\expect H < \lfloor \log_{1/p} n \rfloor + 1 + \frac{1}{1-p}

Теперь оценим снизу. Выберем константу $\lfloor \log_{1/p} n \rfloor - 2$ и будем все считать от неё.

Начнём с того, что $p^{\lfloor \log_{1/p} n \rfloor - 2} \;\! \ge \;\! p^{\log_{1/p} n - 2} = 1 / np^2$ . Используем следующий факт: при $x \ge 0$ выражение $(1-x)^n \le e^{-nx}$ . Теперь можно посчитать вероятности

\prob \bigl( H \le \lfloor \log_{1/p} n \rfloor - 2 \bigr) = \bigl( 1 - p^{\lfloor \log_{1/p} n \rfloor - 2} \bigr)^n \;\! \le \;\! \exp \Bigl( -np^{\lfloor \log_{1/p} n \rfloor - 2} \Bigr) \le e^{-n/np^2} = e^{-1/p^2}

\prob \bigl( H \ge \lfloor \log_{1/p} n \rfloor - 2 \bigr) \;\! \ge \;\! 1 - \prob \bigl( H \le \lfloor \log_{1/p} n \rfloor - 2 \bigr) = 1 - e^{-1/p^2}

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

\expect H \ge \sum\limits_{h=0}^{\lfloor \log_{1/p} n \rfloor - 2} \prob (H > h) \;\! \ge \;\! \bigl( \lfloor \log_{1/p} n \rfloor - 1 \bigr) \cdot \bigl( 1 - e^{-1/p^2} \bigr)

В итоге мы получили, что

\bigl( \lfloor \log_{1/p} n \rfloor - 1 \bigr) \cdot \bigl( 1 - e^{-1/p^2} \bigr) \;\! \le \;\! \expect H \le \lfloor \log_{1/p} n \rfloor + 1 + \frac{p}{1-p}

или, в асимптотическом виде,

\expect H = \log_{1/p} n + \Theta(1)

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

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

struct node:
    array[node*] next
    value

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

type skiplist:
    node head

    constructor(self):
        self.head = none

Поиск

Нужно найти первый элемент, значение которого не меньше данного value.

Алгоритм поиска элемента.

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

method find(skiplist self, value):
    current = self.first
    height = length of current.next

    for level = height, level >= 0, level--:
        while level < length of current.next and current.next[level].value < value:
            current = current.next[level]

    return current.next[0]

Во время поиска мы на каждом уровне нашли узел, который не превосходит value. Эту информацию можно запомнить и использовать в дальнейшем.

method find_path(skiplist self, value):
    current = self.first
    height = length of current.next
    array path[height] = [none, ..., none]

    for level = height, level >= 0, level--:
        while level < length of current.next and current.next[level].value < value:
            current = current.next[level]
        
        path[level] = current

    return path

Вставка

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

Алгоритм вставки элемента.

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

method insert(skiplist self, value):
    path = self.find_path(value)
    level = 0

    while level == 0 or random(true, false):
        if level >= length of self.head.next:
            self.head.next.append(none)
        if level >= length of path:
            path.append(self.head)
        what.next.append(none)
        path[level].next[level], what.next[level] = what, path[level].next[level]

Упражнения

Самоорганизующийся список с пропусками. Вероятность $p$ пропихнуть элемент наверх фиксирована и никогда не меняется. Получается, что структура списка не зависит от частот элементов.

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

Как избежать постоянного роста высоты? Нужно ли вводить пропихивание вниз для редких элементов?

Мы знаем, что в списке с пропусками средняя высота равна $\expect H = \log_{1/p} n + \Theta(1)$ . Насколько вероятны значительные отклонения? Оцените хвост распределения. Получите верхнюю оценку вероятности того, что относительное отклонение будет превышать константу $\varepsilon > 0$ .

\prob \bigl( H > (1+\varepsilon) \cdot \log_{1/p} n \bigr)