#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 на какие-то юзкейсы.

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