ГиперЛогЛог и HDR-гистограмма Недавно узнал о двух структурах данных, и связанных с ними алгоритмах: HyperLogLog и HdrHistogram: https://github.com/clarkduvall/hyperloglog https://hdrhistogram.github.io/HdrHistogram/ Обе структуры нужны для примерных вычислений, когда нам досаточно точности в несколько значащих десятичных знаков (то есть, практически любое применение в жизни, за исключением чистой математики). ГиперЛогЛог считает размер множества за константное время и память. Из наиболее частых применений — в Редисе, в командах PFADD, PFCOUNT. Базово — график уникальных посетителей сайта, например, или загруженность перекрёстков трафиком. Есть более навороченный вариант — ГиперЛогЛог++. Более точен для небольших множеств (до 10 тысяч элементов), и более стабилен (в терминах стандартной ошибки от точного значения) для больших. HDR-гистограмма считает процентили (в общем случае — любые квантили) на больших наборах данных так же за фиксированное время-память. Часто применяется для метрик производительности систем: функция approx_percentile. В обоих случаях можно управлять точностью результата: например, 10%, 1%, 0,1%. Соответственно, вырастает память-время расчёта. Оба применяются в QuestDB — пожалуй, лучшей базе данных для метрик и временных рядов, рекомендую.