Привлекательные структуры данных +60


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

Skiplist

Скиплист на уровне идеи очень интересный субъект мироздания: тут и объекты упорядочены, и вероятности прикрутили, и всё это делает его аналогом бинарного дерева поиска.

Построим его. Изначально имеем обычный односвязный отсортированный список. Пройдёмся по этому списку и выберем каждый элемент с некоторой вероятностью (обычно 0.5) во второй список. Крайние для удобства можно брать всегда. Проведём связи между соседями во втором списке и между выбранными копиями и оригинальными объектами. Получим что-то такое:

Повторим такую операцию, пока не решим, что достаточно. Ограничением можем считать конкретное ограничение на кол-во элементов в самом верхнем списке или просто закончить на log(n)ом уровне. Теперь у нас вот такая картина:

Что мы получили? Во-первых, умеем легко обходить все элементы скиплиста в отсортированном порядке. Во-вторых, умеем искать примерно за O(log(n))нужный элемент: начинаем с самого верхнего уровня и спускаемся по мере необходимости (смотрим на следующий элемент; если он больше искомого, двигаемся на уровень вниз):

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

Теперь мы можем обходить все элементы за O(n)(и не как в bst с хранением предков и разбором случаев, а просто и понятно) + поиск элемента и его вставка/удаление за O(log(n))в среднем. Только что памяти больше тратится, и эти вероятности нет-нет да и могут в какой-то вырожденный случай привести, но бог с ними.

Говорят, что скиплисты — очень хорошее решение, когда нужно что-то вроде thread-safe ordered set/map. Есть вот реализации для java и плюсов в folly.

Sideways heap

Sideways heap (кособокая куча?) – неявная куча, которая задаётся от самого левого листа:

Потом добавляется родитель и брат вершины (или сестра; no sexism):

Развивая эту идею, получим что-то подобное:

Если сделать проекцию кучи на числовую прямую, получим последовательность натуральных чисел.

Заметим, что все листья – это нечётные числа. Все числа на втором уровне – произведение двойки на нечётные числа. Все числа на третьем уровне – четвёрки на нечётные. И т.д. Ещё у этой кучи нет корня и бесконечно много листьев.

Попробуем по номеру вершины узнать всё её окружение. Пусть номер вершины k. Для начала научимся получать соседнюю вершину (для 1 (1 в бинарном виде) это 3 (11) и наоборот, для 2 (10) – 6 (110), для 4 (100) – 12 (1100), …, 2018 (11111100010) – 2022 (11111100110)). То есть нам нужно получить младший бит числа (k & -k), сдвинуть его влево и сделать xor c самим собой, i.e. получается как-то так:

int Sibling(int k) {
	return k ^ ((k & -k) << 1);
}

Для родителя и детей можно вывести следующие формулки:

int Parent(int k) {
	int j = k & -k;
	return (k - j) | (j << 1);
}
pair<int, int> Childrens(int k) {
	int j = k & -k;
	return ( k - (j >> 1), k + (j >> 1) ); // если j == 1, то получаем обратно k
}

Конечно это очень специфическая структура данных, которая тем не менее позволяет делать какие-то интересные вещи. Например такие кучи используются как основа для других (имхо не сильно более полезных) структур данных. Но как по мне гораздо интереснее алгоритм нахождения наименьшего общего предка для вершин в дереве с O(n)на препроцессинг и честным O(1)на запрос. Чуть подробнее о кучах и самом алгоритме можно посмотреть в лекции Кнута.

XOR-фильтр

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

XOR-фильтр есть множество ячеек по L бит (в отличие от фильтра Блума, в котором каждый отдельный бит независим). Например он может выглядеть так:

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

11011 \oplus 10000 \oplus 00101 = 01110

Число 01110 называется кодом (table code) x. Тут ещё вводится четвёртая функция f, которая вычисляет f(x) – L-битный fingerprint числа x. Чтобы проверить, находится ли x в нашем множестве, мы сравниваем его код c его фингерпринтом. Если они равны, можем утверждать, что x почти наверняка в нашем множестве. Если не равны – точно не в нём.

Меняя значение L, мы можем повлиять на вероятность ошибки. Утверждается, что вероятность совпадения кода и фингерпринта примерно равна 2^{-L}, потому если вы хотите допускать ошибку в \varepsilon случаях, то можно брать L=\log_2{\varepsilon^{-1}}.

Самая интересная часть – это заполнить такую структуру. Процедура довольно крупная (в среднем занимает 100+ строк), потому опишем её в общих чертах. 

Для хранения nэлементов создадим структуру объёмом 1.23n + 32 ячейки и будем следовать следующему алгоритму:

  1. Если во множестве значений никого не осталось, мы закончили.

  2. Выберем такой ключ x, что он хешируется в такую ячейку (ячейка X) в которую не хешируется никакой другой ключ.

  3. Удаляем xиз множества необработанных ключей и рекурсивно переходим к шагу 1.

  4. Ячейке Xнужно подобрать такое значение, чтобы f(x) совпадал с результатом xor всех значений для x(используем факт, что h3(x) = f(x) \oplus h1(x) \oplus h2(x)).

Есть некоторая вероятность потерпеть неудачу на шаге 2, но авторы запруфали, что при указанном выше размере xor-фильтра она не очень большая. Если же у вас всё-таки не получилось найти подходящую ячейку, меняем seed у наших хеш-функций и начинаем заново. Хороший пример с картиночками есть вот тут.

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

Сообщество накодило репозиторий с реализациями для разных языков.

Sparse set

Sparse set это некоторый аналог std::vector<bool>/std::bitset за тем исключением, что в нём можно делать очистку всего множества за O(1). Вся структура – это два массива и одна переменная:

template <int R>
struct SparseSet {
		int n = 0;
		int dense[R];
		int sparse[R];
};

dense это массив значений. sparse же хранит индекс значения в dense, т.е. если dense[i] = v, то sparse[v] = i (вместо индекса можно хранить указатель). Тогда добавление выглядит так:

void Add(int val) {
		dense[n] = val;
		sparse[val] = n;
		n++;
}

и проверка на наличие:

bool Has(int val) {
	return sparse[val] < n && dense[sparse[val]] == val;
}

И тут мы умеем в  “зануление”  всей структуры: просто n = 0.

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

Из самого популярного есть вот этот репозиторий. В folly есть реализация, но она почему-то insert-only. Тут можно почитать чуть подробнее.

Пополняемый массив

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

Давайте будем решать следующую задачу (да, баян; да, не стыдно): в сортированном массиве требуется отвечать на запрос “сколько значений существует в массиве между l и r”. Примерно вот так:

class ReplArr {
    vector<int> a;
    ReplArr(vector<int> data) : a(data) {
        sort(a);
    }
    int get(int l, r) {
        return upper_bound(a, r) - lower_bound(a, l);
    }
}

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

class ReplArr {
    vector<int> a, b;
    ReplArr(vector<int> data) : a(data) { sort(a); }
    int get(int l, r) {
        int rr = upper_bound(a, r);
        int ll = lower_bound(a, l);
        int res = rr - ll;
        for (auto x: b) {
            if (l <= i <= r) { res++; }
        }
        return res;
    }
    void add(int x) {
        b.push_back(x);
    }
}

Работает! Только если у нас очень много добавлений, мы станем долго отвечать на запрос get. Давайте тогда время от времени докидывать все элементы b в a и сортировать заново. Время от времени это когда размер b примерно равен корню a (хотим, чтобы get и модифицированный add работали примерно одинаково, а раз их время работы это в интересующих нас случаях O(size(b)) и O\left(\frac{size(a)}{size(b)}\right), можно взять \sqrt{size(a)}; формально асимптотики тут неверны, как минимум не хватает логарифма, но ради proof of concept мы им пренебрегли). Модифицированный add:

void add(int x) {
  	b.push_back(x);
  	if (sqr(size(b)) >= size(a)) {
       	a += b;
       	sort(a);
       	b = vector<int>();
	  }
}

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

LSM

LSM - Log Structured Merge (key-value хранилище специфического вида). Здесь используется примерно та же идея, что и в предыдущей структуре. Суть в том, чтобы хранить данные на нескольких уровнях фиксированного размера (и, например, размеры растут в геометрической прогрессии). Как только первый уровень будет полностью заполнен, смержить его в следующий. Т.е. структуру следующего вида в целом можно назвать LSMом:

struct lsm {
	vector<pair<K, V>> unsorted; // max 256
	vector<pair<K, V>> sorted_c0; // ровно 256
	vector<pair<K, V>> sorted_c1; // ровно 512
	…
	vector<pair<K, V>> sorted_ck; // ровно 65536
	on_disk_storage* storage;
};

Изначально вставляем в unsorted и производим по нему поиск втупую. Как только unsorted заполняется, скидываем все данные в sorted_c0 (очевидно, предварительно отсортировав). В следующий раз, при необходимости такой же операции, применяем условный mergesort и пихаем данные в sorted_c1. И т.д. При необходимости найти элемент, делаем линейный поиск по unsorted (небольшой размер и локальность данных помогут не очень сильно замедлиться) и бинпоиск по всем остальным векторам. Чтобы не делать поиск на больших медленных уровнях, можно рядом держать какой-нибудь фильтр Блума.

Чаще все структуры начиная с sorted_c0 являются каким-то хранилищем на диске, в то время как unsorted это какой-то in-memory контейнер (может даже скиплист). Также роль промежуточных структур вместо векторов может выполнять что угодно (например в LSM-tree, неожиданно, используются деревья).

Реализации можно найти у facebook и google.

Вместо заключения

Пока черновик статьи хранился на задворках гуглодоков, я обнаружил доклад Андрея Аксёнова про необычные структуры данных, которые ещё и используются на практике. Где-то мы пересеклись, где-то нет. В любом случае доклад посмотрите. Он хорош.

Реклама

Можно подписаться на мой канал про C++ и программирование в тг: t.me/thisnotes.




Комментарии (12):

  1. cadovvl
    /#24479176 / +2

    Восхитительная статья.
    За ссылки на разные репозитории - отдельное спасибо: даже нашел новые для себя.

  2. saluev
    /#24479268

    В sparse set ещё можно быстро случайный элемент генерировать.

    • Dasfex
      /#24479368 / +1

      Вы про получение случайного из множества? Там что-то более умное чем взять рандомный элемент на отрезке [0; n)?

      • saluev
        /#24479922 / +1

        Нет, не более умное, ровно так) Просто в традиционном хешсете это за О(1) вообще нельзя сделать.

        • Siper
          /#24487448

          Смотря какие требования к распределению вероятностей. Но вообще, даже для юниформ, мне кажется все же разумнее будет мейнтейнить дополнительный неупорядоченный список, чем связываться со sparse set.

  3. wataru
    /#24479320 / +1

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


    Это двумерная структура данных, позволяющая делать всякие запросы в прямоугольных областях За O(log^2 n). При этом потребляющая O(n log n) памяти.


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

  4. Alexandroppolus
    /#24479482

    В "пополняемом массиве" интересная общая идея, но, по моему, для задачи, которая приводится в пример, лучше подойдет сбалансированное дерево поиска.

    • Dasfex
      /#24479596 / +1

      Держите задачу, где такая концепция является решением: https://codeforces.com/problemset/problem/342/E?locale=ru : )

      • wataru
        /#24481102

        Жесть какая-то. Я кроме ужаса за O(n log^2 n) ничего придумать не могу: там обработка всех запросов оффлайн и персистентные балансированные деревья с минимумом в поддереве (для каждого направленного ребра найти множество красных вершин в поддереве, отсортированных по времени добавления. При запросе взять любое соседнее ребро и ему обратное, сделать запрос в деревьях. Построение снизу вверх со слиянием меньшего персистентного дервева в большее соседнее).


        Дайте, что ли подсказку — в какую сторону копать и как применять концепцию накапливания изменений?

        • Dasfex
          /#24481162 / +1

          Можно попробовать каждые \sqrt{n}операций пересчитывать ответ, чтобы отвечать на запрос за единицу, а неучтённые новые запросы (которых до корня) обрабатывать втупую.

          • wataru
            /#24481230

            Вы имеете ввиду, каждые sqrt(n) новых вершин пересчитать bfs-ом по всему дереву каратчайшие расстояния, и оставшиеся добавленные вершины проверять отдельно?


            Мало того, что надо научиться за O(1) отвечать на запросы о расстоянии между двумя вершинами в дереве (это надо online LCM за константу делать — весьма экзотический алгоритм), так еще и работать это все счастье будет за O(n sqrt(n)), что для 10^5 как-то совсем медленно. В мое время такие ограничения подразумевали O(n log n) решение.

          • wataru
            /#24481234

            Хм… однако там есть разбор задач и именно такой метод и предполагается. Хотя, если учесть что там time limit 5 секунд, то вроде как и должно влезть. А я то думал там что-то хитрое и O(n log n) решение в итоге.