#algo and some #math
https://hbfs.wordpress.com/2021/07/20/binary-trees-are-optimal-except-when-theyre-not/

#algo
Довольно приятный плейлист про не очень стандартные алгоритмы, которые ещё и хорошо поясняются.
www.youtube.com/playlist?list=PLc82OEDeni8SGp5CX8Ey1PdUcoi8Jh1Q_

#cpp #common и может #algo

Вроде как знание о векторах в плюсах довольно тривиальное, но тем не менее.

Общеизвестный факт, что вектор это по факту такая структурка:

template <typename T>
struct vector {
T* data;
int size, capacity;
}

Кажется, сделать динамический массив меньшими усилиями ну никак нельзя. В самописных версиях иногда вместо двух чиселок также хранят указатели, а size/capacity вычисляют каждый раз. Можно упороться и хранить их в одной int64 переменной: первые 4 байта на размер, вторые на вместимость. А можно вообще не хранить размер, а сделать ваш вектор нуль-терминированным и считать длину ручками каждый раз. Раз в k случаев такое тоже работает хорошо.

Стандартная библиотека предлагает для кастомизации своего вектора подсунуть свой аллокатор вторым шаблонным аргументом. И всё. Больше пользователю ничего не надо. Но ведь есть ещё такая важная характеристика как resize policy -- то, как ваш вектор изменяет свой размер. Как много выделить в первой аллокации? 1, 2, 8? С единицы начинать плохо: после первого push_back почти наверняка придёт второй. С восьми тоже плохо: может у нас вектор объектов, каждый из которых 3Мб, а юзать мы хотим всего для трёх элементов. Да и для двойки свой кейс можно придумать.

Теперь про изменение этого размера. В clang довольно дефолтная схема с умножением на 2 (с оговорками). Но есть ощущение, что умножение на 2 оч плохое решение. Точнее, умножение на любую константу плохо. Когда речь идёт о расширении 8->16, это вполне себе хорошее решение (или нет?🧐без знания размера объектов непонятно). Но когда у вас уже 1кк элементов и вы хотите положить ещё пару штук, расширение 1кк->2кк выглядит как из пушки по воробьям.

И что делать?

Как вариант не расти всегда с одинаковой скоростью. Можно смотреть на текущее кол-во элементов. Можно на занимаемую память. И после выбора какой-то границы, расти в 2 раза до неё и в 1.2 после (понятно что тут стоит покрутить и найти компромисс между занимаемой памятью и временем работы в зависимости от ваших данных и паттерна работы с ними). В go в этом плане примерно так и сделано.

Ещё есть вопрос, уменьшаться ли, если размер стал слишком маленький: если у меня capacity на 1кк, а размер 10, то наверное можно было бы пожаться до этих самых 10, а потом расти по обычным правилам. Вроде как так почти никто не делает. Правда слышал, что в каком-то языке реализовано сжатие, если размер в 4 раза меньше вместимости (сходу не вспомнил где).

В студвекторе из подобного есть метод shrink_to_fit, который уменьшает вместимость до размера. Прошу заметить, что метод этот non-binding, i.e. необязательный. Тут авторы вольны делать что хотят. В clang честно пытаются уменьшиться.

Учитывая, что resize policy это что-то, что нельзя описать одним числом, интересно попробовать придумать, как это могло бы выглядеть в стандартной библиотеке. Что-то такое:

template <
typename T,
typename Allocator = ... ,
template <typename T> Recap = std::twice>
class vector;

где Recap может выглядеть как что-то вроде

template <typename T>
size_t MyRecap(size_t sz, size_t cp) {
if (sz * 4 < cp) { return sz; }
if (cp * sizeof(T) > 10 * kBytesInMB) {
return cp * 1.2;
}
return cp * 2;
}

Понятно, что всё это можно делать и сейчас, вычисляя новый размер/капасити снаружи и используя resize/reserve, но менеджерить размеры не изнутри как неестественно.

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

Можно ещё писать контейнеры кусками (вроде дека), чтобы немножко получше жить с аллокациями. Или пробовать хранить мало данных на стеке, прям как sso.

Зачем это всё? А хер его знает. Почти наверняка на практике это вам не пригодится, потому что если вам не хватает std::vector, то у вас уже либо все остальные проблемы с производительностью решены, либо очень специфическая задача. Но знать полезно.

Такие дела.

#algo

Хеш-таблицы 1/2.

1. load factor.
Часто говорят, что важно следить за ним. Ведутся жоские споры (у агрошкольников) о том, какие значения норм, а какие нет. В умных книжках часто пишут, что норм 0.5-0.7. В жизни вам может зайти и 0.99, и может больше единицы, и в районе 0.005. Важно понимать, что важен не сам LF, а средняя глубина поиска. Потому что у вас есть коллизии, которые в одном бакете делают 10 элементов, когда вся таблица на 100. Вроде LF 0.1, а работает медленно. И есть удаления. Которые например при открытой адресации просто помечают элементы удалёнными, не ускоряя поиск. Короче за этим надо следить (в случае открытой адресации видимо вас ждут k костылей, в случае закрытой можно считать LF как максимальное кол-во элементов в бакете делить на размер таблицы).

2. Хеш-функция.
Легко можно выбрать хеш-функцию, посмотрев на её бенчмарки (которые где-то там делали авторы и она всё и вся разносит). Но очевидно, что не будет понятно норм/нет, пока вы не померяете на ваших данных. Ну это ладно. Это известный тезис.
А вот какую выбрать? Может я коллизий поменьше хочу. Тогда может что-то из sha-2 или md5? У них, говорят, коллизий мало. Вон они по 128+ бит хеши выдают. ... А ключи же у нас в районе 64х. Получается надо обрезать. И тут уже ничего не понятно, норм оно будет или нет. Ещё и считается долго. Долго это плохо. Надо помнить, что хеш-функция это на каждую операцию. Потому может лучше "плохо" и быстро с помощью crc32, DJB или fnv (главное чтобы не LoseLose). Хотя можно что-то среднее: SuperFastHash, Murmur, CityHash или Robin-hood (или Hopscotch). Вообще про тему скорости хеш-функций можно вспомнить SMHasher, который считает, сколько функция умеет хешировать в секунду и ещё какие-то характеристики. Но тут тоже стоит помнить, что неважно, сколько она хеширует в секунду, если вы собираетесь её юзать для восьмисимвольных строк (надо мерять).
Бывают ли идеальные хеши? Да! Но надо бы знать ключи заранее и делать предпосчёт, зато юзается быстро и без коллизий :) Тут можно взглянуть на gperf и cmph.
Можно вообще выбрать какое-то семейство функций, и время от времени брать функцию из него.

3. Размер.
Можно зафиксировать вашу таблицу на всю жизнь (и жить с открытой адресацией):

std::pair<K, V> data[1024];

Но что-то подсказывает, что такого хватит ненадолго (хотя мб и хватит). Стандартный путь это как вектор (просто элементов для открытой адресации или например листов для закрытой): реаллокация в k раз, чтобы LF получше стал. Как выбирать k смотрите два поста назад. Можно размеры только степенями двойки. Или можно делать статику снаружи и динамику внутри:

std::vector<std::pair<K, V>> data[1024];

Может быть полезно в случае параллельной таблички или если вы локальность цепочки при закрытой адресации хотите.

4. Ключи.
Иногда нужно хранить какую-то мету, само значение (для сравнений каких-нибудь) или значение хеша. В зависимости от того, насколько много занимает ваша структурка, можно выбирать, хранить например всё в одном массивчике или может ключи/значения отдельно, чтобы в кеши хорошо попадало что надо. Тут конечно всё зависит от вашего паттерна доступа.
Кстати забавно, что если объект жирный, можно попробовать хранить первые k байт его представления и сравнивать их. Или можно вообще не сравнивать изначальные ключи с одинаковыми значениями хеша, если вы уверены в хеш-функции или готовы иногда ошибаться.

#algo

Хеш-таблицы 2/2.

5. Пробинг при открытой адресации.
Пробинг -- то, как вы двигаетесь по таблице в поиске свободного места. Очевидно можно линейный: offset[i] = i или i*k. Можно квадратический: offset[i] = i*i или даже alpha*i + beta*i*i. Или double hashing: offset[i] = i*hash2(key). Или cuckoo hashing (ну придумали конечно): для любого ключа проверяем две точки от двух хеш-функций; если есть место, вставляем, иначе выбираем одного из этих двух оккупантов и выселяем его, а на его место наш элемент; аналогично делаем с выселенным элементом; если такое повторяется некоторое количество раз, меняем хеш-функцию и рехеш. Прикольно, что такой приём гарантирует O(1) на поиск.

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

7. И немного читов.
-- можно как в LRU-кеше при закрытой адресации найденный где-то в глубине листа элемент перемещать в самое начало, чтобы в следующий раз его поиск прошёл быстрее. В открытой адресации наверное тоже можно посвапать аккуратно с удалённым элементом например, но звучит как что-то, где легко споткнуться.
-- хешировать можно не просто пришедший элемент, а что угодно. Можете хешировать хеш от хеша от хеша. Или первые 8 байт объекта. Или для чисел сначала 228 добавить. Короче вертеть как хочешь, абы хорошо было.
-- вместо листа/вектора при закрытой адресации можете хранить что-то другое. В java например с какого-то момента лист превращается в bst.

[1]. Hash map analysis.
[2]. Extendible hashing.
[3]. Я написал самую быструю хеш-таблицу.
[4]. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step [видео].
[5]. О хеш-таблицах в Clickhouse [видео].

#algo

Вероятностные структуры данных 1/2.

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

1. Фильтр Блума решает задачу проверки значения во множестве. Изначально это какой-то битсет размера m и рядом k хеш-функций. При добавлении элемента во множество с помощью хеш-функций определяется k битов, которые устанавливаются в 1. Теперь при необходимости проверить, находится ли элемент во множестве, считаем от него все хеш-функции и проверяем, правда ли, что все интересующие нас биты установлены в 1. Проблемы: иногда могут возникать ложноположительные срабатывания (элемента нет, а мы ответили, что есть); нельзя удалять элементы (один и тот же бит может быть установлен различными элементами). В таком виде два фильтра легко объединять/пересекать (побитовое ИЛИ/И множеств). В отличие от хеш-таблиц (или чего-то подобного) фильтр блума может являться универсальным множеством (все биты == 1).
Есть разные вариации: вместо 0/1 можно хранить числа и при добавлении инкрементить соответствующие значения, а при удалении декрементить (counting bf); вместо одного counting bf можно хранить n независимых (bitwise почему-то); spectral bf — оптимизированный counting; aging bf, который поддерживает операцию удаления и не хранит старые данные; stable bf, в котором мы рандомно декрементим несколько значений, после чего k значениям устанавливаем максимальные значения (утверждается, что рано или поздно получится достичь какого-то константного кол-ва нулей, магия); A^2 bf — теп memory efficient implementation; ну и конечно более менее умеющий в удаление bf (если кратко, разрешается некоторые участки помечаются как collision-unsafe, и удаление из них не происходит).
Тут ещё можно считать конкретные размеры битсета и кол-во хеш-функций исходя из допустимой пропорции ошибок.
Иногда юзается в кешах или как вспомогательная структура для других сд.
Ещё можно строить key-value хранилище на bf. Если вам нужно что-то вроде k->v \in [0; 10], давайте держать 11 bf, и по значению v решать, в какой bf добавить ключ. При получении значения пройдёмся по всем bf и в котором нашли ключ, такое и значение.
Ещё давайте такой пример. Нам нужно на устройстве пользователя (допотопный мобильный телефон == мало памяти) понимать, звонит нам спамер или нет. Давайте все телефоны из базы спамерских закинем в bf. Чтобы избежать false-positive срабатываний, пройдёмся по всему множеству телефонов (для 10циферных вполне реально) и выпишем рядом с bf номера, на которых мы ошибаемся (их не будет много, порядка единиц при хорошем bf). Теперь если bf говорит, что номер спамерский, проверим, есть ли он в отдельно выписаных. И теперь мы умеем точно отвечать при очень маленьких затратах памяти. Тут можно почитать реальные кейсы.
А ещё можно на них bst строить. А ещё можно в борах юзать. Ух короче.
Основной link.

2. Count-min sketch помогает насчитать частотность различных объектов (например у нас есть бесконечный поток данных, и хочется уметь выдавать примерную частоту появления объектов, причём с очень маленькими затратами на время/память).
Структура очень простая: k хеш-таблиц фиксированного размера (можно одного, можно разных). Изначально все они заполнены нулями. Как только нужно добавить объект, инкрементим соответствующую этому объекту ячейку в каждой хеш-таблице. При запросе узнать частоту объекта, берём значения объекта из каждой хеш-таблицы и считаем минимум. Собственно всё. Понятно, что чем больше хеш-табличек вы берёте, тем ближе ответ будет к реальному, иначе из-за коллизий может получится завышенным.
Ещё если знаем, что элемент есть во множестве, можно удалять.
Только пишется это обычно не как несколько хеш-таблиц, а матрицей + хеш-функцию на каждую строку.
Ещё их легко объединять и (если одно множество строго подмножество второго) вычитать.
Тут (осторожно, скачается пдфка) есть про применение в безопасности, базах данных и даже биоинформатике.

#algo

Вероятностные структуры данных 2/2.

3. HyperLogLog используют, чтобы узнать примерное количество уникальных элементов в мультимножестве.
Тут у нас опять есть k хеш-функций, каждая из которых выдаёт значения от 0 до 2^64-1. Значение хеш-функции это какая-то последовательность из 64 нулей и единиц. Теперь немного помахаем руками. Будем считать, что наши хеш-функции "хорошие", i.e. плюс-минус равномерно распределены (хотя вообще-то мы хотим этого для всех структур). Тогда хеш равновероятно может начаться с нуля и единицы (с p=1/2). Аналогично с 01 с p=1/4, с 001 с p=1/8, 0001 — 1/16 и т.д. Т.е. если мы встретили хеш с префиксом 0000001 (а такое могло произойти только с p=1/128), то мы можем сказать, что в мультимножестве примерно 128 элементов (на больших числах конечно же). Конечно же такая оценка может легко сломаться, если нам попадётся один случайный хеш с длинным префиксом нулей. Для обхода все элементы потока делят на несколько подпотоков (например по очереди отправляют сначала в 1й, потом во 2й, в 3й и в 4й), считают максимальную длину префикса в каждом подпотоке среди всех хеш-функций (например 1, 5, 8, 3) и считают среднее гармоническое на страшные коэффициенты из тервера:

k*(2^(-1) + 2^(-5) + 2^(-8) + 2^(-3))^(-1)

Примерно столько элементов в нашем мультимножестве.
Сейчас есть следующая проблема: если неаккуратно делить на подпотоки, то какой-нибудь частый элемент, дающий маленький хеш, испортит нам все подпотоки. Потому давайте номер подпотока определять по первым k битам хеша. Т.е. если у нас пришёл объект с хешом 0010|0010...01, то по первым например 4 битам мы определим, что его подпоток номер 2, а считать позицию первой единицы будем начиная с 5ого бита (в этом примере она равна 3). Если в этом подпотоке уже был элемент с единицей дальше, то просто забываем эту тройку, иначе, если это дальше, чем было до текущего момента, считаем, что 3 у нас самая далёкая. Таким образом частые элементы будут портить один и тот же подпоток.
Такая структура легко мержится. Предположим у нас есть посчитанный HLL для мультимножества A (массив из n чисел, где n — кол-во подпотоков, а i-е число в нём — позиция самой правой единицы в этом подпотоке) и HLL для B, то смержить их это за O(n) посчитать максимум из двух для каждой ячейки. Соответственно HLL легко параллелится (каждый чанк мультимножества считаем независимо, а потом мержим).
Если немного покумекать-покрутить включения-исключения, можно научиться пересекать/вычитать несколько HLL.
HLL юзается в redis (или статья), или например под капотом для approx_count_distinct в других бд.

4. MinHash используется для оценки мощности пересечения множеств (например будем считать два текста похожими, если множества их слов похожи; можем не храня эти огромные тексты таким примитивным методом задетектить плагиат). Тут вводится коэффициент Жаккара:

J(A, B) = |пересечения|/|объединения|

Как это работает.
Берём k хеш-функций. Считаем значения всех хеш-функций для каждого элемента множества A. Среди значений каждой хеш-функции берём минимум. Получаем массив из k элементов, каждый из которых равен минимальному значению некоторой хеш-функции на этом множестве. Повторяем то же для множества B. И теперь считаем коэффициент Жаккара двух векторов с хешами. Утверждается, что он очень хорошо приближает J(A, B). Тут можно считать пересечение двух векторов не как множеств, а совпадение по позициям.
Иногда вместо k хеш-функций берут одну, но считают k её минимальных значений. Или одну по разным простым модулям.
Ну и тут link на какие-то юзкейсы.

Вот такую магию люди придумывают, а у нас до сих пор горячую воду отключают на две недели. Мир контрастов.

#pub #algo
Пиу-пау.
Если вам так же как и мне нравится узнавать интересные (пусть и бесполезные) идеи, которые вы никогда на практике не заюзаете, предлагаю почитать мою новую статью про нестандартные (но простые) структуры данных.
https://habr.com/ru/post/673776/

#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.

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

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

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