#algo

Деревья в алгоритмах 1/2.

В алгоритмах часто используются различные деревья (как графовый термин) в виде различных структур данных. Стандартный пример это деревья поиска или кучи. Однако разновидностей структур данных, которые решают те или иные задачи, и в качестве базы (или хотя бы в названии) содержат в себе дерево очень много. Давайте на них и посмотрим.
Опустим подробные описания чего-то дефолтного вроде avl-деревьев, красно-чёрных, или бора (trie). Может только увидим их какие-то прокачаные версии. И не будем особо рассматривать персистентные сд. Там конечно всё очень круто, но для обзорного поста по многообразию ту мач.

Мне идейно очень нравится декартово дерево (пусть оно и довольно известно). Тут и все свойства обычного bst, и это в некотором роде вероятностная структура данных. А если писать неявное, то появляется возможность делать много разных операций как у дерева отрезков, но с большей вариативностью: перемещать части массива данных, менять местами чёт/нечёт и при желании даже копировать отрезки (с персистентной версией).
Splay-деревья тоже bst но обладают замечательным свойством: элементы, которые ищут чаще, со временем оказываются выше, что позволяет тратить меньше времени на их поиск в будущем. Хз, как часто они используются, но в вакууме свойство очень приятное.
Scapegoat tree в отличие от других bst старается не хранить в нодах ничего кроме key-value и указателей на детей и вместо небольшой перебалансировки на каждую операцию делает большие перебалансировки поддеревьев, но редко.

Рядом с обычными bst есть различные версии B-деревьев, которые активно используются в базах данных и файловых системах. Стандартное B-дерево это просто обобщение bst, где разрешается иметь более двух детей/элементов в ноде, что позволяет лучше работать с кешами + ускорить операции работы с большими блоками данных. Следующая версия B-дерева это B+-дерево, которое имеет немного другую структуру и быстрее работает при последовательном обходе. Тут же можно найти B*-tree (которое пытается плотнее упаковывать данные) и B*+-tree (которое, неожиданно, комбинирует фичи двух прошлых). Известными частными случаями B+-tree являются 2-3 и 2-3-4 деревья. Есть ещё какие-то чуть-чуть апдейченные версии вроде counted b-tree.

Далее идут различные боры (или префиксные деревья). Из интересного тут есть цифровые боры, которые позволяют работать с множеством чисел асимптотически эффективнее, чем со стандартными bst (в основном используя факт о максимально значении в множестве). Например это Van Emde Boas tree, X-fast trie и Y-fast trie (эти три умеют делать стандартные операции bst с лучшей асимптотикой, хотя может с памятью похуже), Fusion tree (а это в несколько новых операций). А есть вообще упоротые штуки вроде Hash Array Mapped Trie. Видел ещё ternary search tree, которое бор с не более чем тремя детьми. Это достигается введением нод разного типа и особых правил с ними. При использовании вы иногда просто юзаете ноды как ребро, опуская символ из неё. Ещё есть сжатые боры вроде Radix trie/Patricia tree.

Ещё есть всякие сд, позволяющие эффективно работать со строками Например стандартное суффиксное дерево. Идея у него очень простая: выписываем в бор все суффиксы строк вашего множества, после чего можно очень быстро искать различные подстроки. Даже можно искать строки с опечатками, правда с некоторыми ограничениями (если опечатка в начале, всё ломается). Потому есть специализированные структуры данных вроде BK-tree. Ещё довольно частым кейсом является код Хаффмана.

#algo

Деревья в алгоритмах 2/2.

Очень часто деревья используются во всяких геометрических штучках. Самым простым примером кмк является binary space partitioning: вся плоскость это корень; по мере разделения областей к вершине, представляющей какую-то часть плоскости, добавляется два ребёнка (т.е. дерево всегда полное). Примерно таким же, но в терминах множеств объектов в мультиразмерном пространстве, занимаются ball trees.

Ещё сд:
- Rope -- это сд, позволяющая эффективно (ну +-) работать со строками; хотя олимпиадники любят использовать не по назначению, когда надо уметь обращаться по индексам во множестве;
- Zipper -- идиома из функционального программирования. Тут рядом есть Finger tree;
- дерево интервалов (не путать с деревом отрезков);
- или совсем молодое дерево палиндромов.

Пачка фактов:
1. Дерево отрезков можно писать за 2n памяти просто перенумеровав вершины.
2. Есть упрощённая версия реализации красно-чёрных деревьев — left-leaning reb-black trees (левое или может левацкое кчд). Аналогично есть левацкая куча. Ещё как вариация кчд есть AA-tree.
3. Слышал, что в STL любят кчд, потому что у тебя не более двух поворотов на каждую операцию, в то время как условное авл-дерево может сильно измениться.
4. Большинство индексов в базах данных построены на той или иной структуре данных. Тут можно посмотреть на небольшой лес.
5. По факту кучи тоже деревья (в графовой терминологии), но писать ещё миллион букав не хотелось, потому можете сами глянуть тут.

Если вы знаете ещё что-нибудь из этой оперы, смело накидывайте в комментарии.

#common #algo

Сегодня немножко математики.

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

Предположим у нас есть следующее дп (не будем расписывать в общем виде):

dp[i] = 2dp[i-1] + 3dp[i-2] - dp[i-3]

с какой-то базой. Например

dp[0, 1, 2] = {1, 2, 3}

Предположим, мы хотим вычислить несколько конкретных значений (dp[10^3], dp[10^15], то есть значения с очень большими номером), а не все (обычно так и бывает).

Давайте посмотрим на это в виде матриц. Базовая матрица у нас имеет вид (это не определитель, я просто скобки не умею нормально рисовать):

| 1 |
a = | 2 |
| 3 |

где a_i это соответственно dp_i, i \in [0; 2].

Если мы перемножим матрицу ниже на столбец выше

| 0 1 0|
M = | 0 0 1|
|-1 3 2|

мы получим вектор

| 2 |
| 3 |
| 11 |

в котором мы по факту получили сдвиг в нашей дп-шной последовательности на 1 вперёд (то есть вычислили dp[2], dp[3] и dp[4]).

А теперь предположим, мы хотим найти dp[n]. Конечно, эту последовательность умножений можно повторять раз за разом n - 3 раза, пока мы не получим нужный элемент. Но в чём тогда был смысл подобных движений? Давайте сначала нашу матрицу перехода бинарно возведём в (n-3)-ю степень и только потом умножим вектор a. Чтобы получить ответ, достаточно будет взять последний элемент получившегося столбца:

ans = (bin_pow(M, n - 3) * a)[2];

То есть по факту вы можете считать любую подобную “линейную” последовательность быстро для любого адекватного значения n. Я когда-то, например, писал нахождение n-ого числа Фибоначчи на компиляции. Тут правда надо быть аккуратным с глубиной рекурсии и возможно подкрутить флаг -ftemplate-depth.

#algo #cpp #highload

0. Продолжаю отсматривать CppCon 2023. Пока закину один доклад, про который вы наверняка знаете от самого автора: A Long Journey of Changing std::sort Implementation at Scale - Danila Kutenin.

1. My favourite memory leak.
Короткий видос (всего 4 минуты), но какая красота..

2. Интересная статья про succinct data structures.

3. Architecture antipatterns.

4. Scrambling Eggs for Spotify with Knuth's Fibonacci Hashing.
Прикольный пост про перемешивание треков и разные подходы к этому.

#cpp #algo #pub

Написал пост про разреженные структуры данных в дополнение к инфе про sparse set.

https://habr.com/ru/articles/790844/

#algo #cpp

Узнал про bimap. Написал про него три слова.
https://telegra.ph/Bimap-02-11

#cpp #algo #pub

Когда-то (ещё в августе 2023) я хотел написать про одну из возможных реализаций связного списка, а потом как-то разошёлся и написал про все мне известные. Ну как-то вот так и получилось.

https://habr.com/ru/articles/814955/

[неожиданно] #math #algo

Делюсь небольшой задачей из начала универа. Сильно мне тогда понравилась.

https://telegra.ph/Zadacha-iz-molodosti-05-30

Единственное что пришлось приложить немалые усилия (и попросить помощь у друзей), чтобы восстановить картинку в голове, потому что математик из меня так себе.

#algo

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

Поиск подстроки в строке.

Есть такой чувак Андрей Гейн. У него есть канал на youtube и канал в тг: @andgein_notes. В конце декабря он написал про 2 текстовые версии о поиске подстроки в строке, которые он выложил в свой блог.

В первой он рассказывает о поиске конкретного паттерна в тексте:
- наивном подходе
- префикс функции и алгоритме Knuth–Morris–Pratt
- далее про Boyer–Moore алгоритм
- и в конце про Two-Way

Сначала прочитайте это замечательное полотно, а потом давайте посмотрим, как использовать продвинутые сёрчеры строк в C++.

В <functional> есть 3 сёрчера, которые вы можете использовать для поиска строк. Первый -- std::default_searcher. Этот сёрчер, как и все другие, должен передаваться третьим аргументом в алгоритм std::search. Сам сёрчер принимает себе pattern, который ищется в тексте:

auto it = std::search(text.begin(), text.end(), std::default_searcher(pattern.begin(), pattern.end()));

Такой сёрчер будет использовать стандартный алгоритм поиска подстроки в строке.

Не дефолтными сёрчерами могут быть:
- std::boyer_moor_searcher
- std::boyer_moore_horspool_searcher
Пользуемся ими точно так же, как и стандартным.

Если посмотреть на реализацию, например, boyer_moor_search, то можно увидеть ровно описанные Андреем вещи (например, прекомпьют разных табличек).

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

Если приглядеться на дефолтный сёрчер, то можно понять, что там много не надо и при желании можно и свой реализовать. Можно писать и общего вида алгоритмы, которые будут пробрасывать сёрчеры в std::search.

И пока и всё. Двигаемся ко второй лекции, где освещены продвинутые способы:
- Ахо-Корасик
- суффиксный бор
- суффиксное дерево
- суффиксный автомат

Читается конечно не за секунду. Информации много. Иногда надо вдумываться. Но зато есть вопросы на подумать с подсказками и ответами. Или вопросы, где можно себя проверить.

Прям качественный обучающий материал. Кайфуйте.