18.01.2023 14:03
UngiftedPoet 38 3700 Источник


Привет, Хабр! Меня зовут Максим, я учусь на третьем курсе МФТИ. Этим летом я участвовал в студенческой программе, которую проводила команда Tarantool. Если кратко, суть программы в том, чтобы самостоятельно или в команде решить исследовательскую задачу в определенный срок. 

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

Когда полезен HyperLogLog?


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

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

У алгоритма есть несколько особенностей:

  • Точность оценки не снижается при увеличении размера множества
  • Потребляемая память постоянна. Она зависит только от параметра точности и сравнительно мала
  • Не требуется хранить элементы оцениваемого множества
  • Алгоритм работает с потоком данных

Идея алгоритма на пальцах


Разберемся с базовой идеей работы HyperLogLog. Как я говорил ранее, алгоритм работает с потоком данных. Это значит, что HyperLogLog последовательно получает и обрабатывает элементы из потока. 

Суть обработки следующая: мы получаем очередной элемент, считаем его хеш и рассчитываем в нем количество нулей, идущих подряд. 1/2 всех возможных хешей начинается с 1, 1/4 c 01, 1/8 с 001 и так далее. 


Назовем количество нулей, идущих подряд + 1 рангом хеша: $rank(hash) = clz(hash) + 1$. Ранг характеризует редкость хеша. Логично предположить, что если мы встретили «редкий» хеш, то наше множество — «большое». Для оценки мощности множества нам достаточно знать лишь максимальный ранг в потоке.

А насколько наше множество большое? В среднем, на $2^n$ хешей встретится один хеш с рангом $n+1$. Поэтому $estimate = 2^{max \: rank}$. Понятно, что это довольно грубая оценка. Потому что один редкий хеш в потоке может существенно исказить оценку. Однако базовая идея такая, ее осознание поможет лучше понять работу алгоритма.

Посчитаем объем памяти, необходимый для оценки множества размером $2^{64}$ или меньше. Для представления такого множества значения хеш-функции должны быть не меньше $log_{2}2^{64} = 64 $ бит. Чтобы получить оценку нам нужет только максимальный ранг, для хранения которого потребуется $log_{2}64 = 6$ бит. В общем случае для оценки множества размером $N$ потребуется $log_{2}(log_{2}(N))$ бит, этим и объясняется название алгоритма.

HyperLogLog


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

В алгоритме HyperLogLog применяется следующая стратегия разбиения на подпотоки:

  • Номер подпотока определяется последними $p$ битами хеша. Это число мы будем называть индексом.
  • Чем больше бит мы отдадим под индекс — тем точнее будет оценка, поэтому число $p$ мы будем называть параметром точности алгоритма, или просто точностью.
  • Регистром будем называть пару из индекса и максимального полученного им ранга.


При такой стратегии алгоритм будет описываться следующими формулами:

$m = 2^{precision}$


$standard \: error < \frac{1,04}{\sqrt{m}}$


$memory \: usage = m \times 6bit$


$estimate = \alpha \times \left ( \sum_{0}^{m-1} 2^{-rank_{i}}\right )^{-1}$


$\alpha \simeq 0,7m^{2} $



standard error — выводится с помощью нетривиальной математики. Для точности оценки в $1 \%$ достаточно отдать $14$ бит под индекс, $2^{14}=16384$ регистров.

memory usage — храним массив из $m$ регистров, индекс регистра определяется индексом в массиве, для хранения значения ранга достаточно $log_{2}(64 — precision) < 6$ бит. Для точности оценки $1 \%$ потребуется $12 288$ байт. 

estimate — опять сложная математика, но по сути, среднее гармоническое с нормировочным коэффициентом.

До этого мы предполагали, что примерно 1/2 всех возможных хешей начинается с 1, 1/4 c 01, 1/8 с 001 и так далее. Но чтобы это выполнялось, значения нашей хеш функции должны быть равномерно распределены, то есть вероятность получения любого значения хеша от $0$ до $2^{64} — 1$ должна быть одинаковой. Если это условие не будет выполнено, формула для оценки станет неверной.

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

Приведу пример. Допустим мы будем раскладывать наши хеши по очереди — первый хеш идет в первый подпоток, второй во второй и так далее. Подобное разбиение решает проблему с появлением одного редкого хеша в потоке. А если он будет повторятся? Тогда в какой-то момент он может попасть во все подпотоки и испортить статистику вообще везде. 

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

Познакомившись с базовой теорией алгоритма, приступим к реализации.

Bias correction


В практической плоскости меньше всего вопросов вызывает формула $memory \: usage$. Но формулы $estimate$ и $standard \: error$ уже не кажутся такими очевидными. Мы никак не можем проверить формулу $standard \: error$ до реализации самого алгоритма, а вот формулу оценки легко прощупать заранее.

Давайте проверим формулу оценки, как это делают физики: рассмотрим граничный случай с очевидным ответом. В нашем случае это будет пустое множество и очевидный ответ — $0$. 

Еще ни один хеш не был добавлен, значит значения всех рангов равны $0$, а значит в знаменателе формулы оценки имеем просто сумму $1$ от $0$ до $m — 1$.

$estimate \approx {\frac{0,7 m^2}{m}}=0,7m = 183500$, если $precision = 18$. Очевидно, оценка даже не близка к действительности. Не теряя надежды, давайте посмотрим как ведёт себя оценка в зависимости от фактической мощности множества: 


Из графика видно, что при малых мощностях, действительно, наблюдается стабильное отклонение, но при больших мощностях ($\approx1250000$ для $precision = 18$) оценка начинает сходиться к мощности множества. Точка, после которой оценка начинает сходится, на графике обозначена как bias threshold и на практике всегда меньше $5m$.

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

Что мы можем сделать?

Как видно из графика, кривая смещения гладкая. Значит можно аппроксимировать зависимость $bias(raw \: estimate)$ каким-нибудь полиномом. Но на практике проще аппроксимировать $cardinality(raw \: estimate$), а затем найти кривую смещения как $bias(raw \: estimate) = raw \: estimate — cardinality(raw \: estimate)$. В самом алгоритме будем считать сырую оценку согласно формуле из теории и вычитать смещение, если сырая оценка не превышает $bias \: threshold$.


Применив коррекцию смещения получим следующий график:


Выглядит неплохо, мы избавились от смещения при малых мощностях, но давайте посмотрим как ведет себя погрешность:


Из графика видно, что при малых мощностях погрешность выше заявленной, но граница сходимости оценки сместилась влево и стала порядка $500000 \approx 2m$. Это, определенно, улучшение. Но мы не решили главную проблему алгоритма, нам все еще нужно знать границу сходимости и минимальный размер множества.

Неплохая попытка, но это всё ещё выглядит, как решение для узкого круга задач.

LinearCounting


Решить проблему с небольшими мощностями нам поможет еще один вероятностный алгоритм: LinearCounting. Кратко опишу принцип его работы. Алгоритм также работает с потоком данных и применяет хеширование для рандомизации данных. Пусть имеется m возможных значений хеш функции, получив очередной элемент, вычисляем от него хеш и запоминаем, что полученный хеш появился в потоке. Пусть $m_{1}$ — число различных хешей, появившихся в потоке, тогда оценка получается согласно следующей формуле:

$estimate = m \times ln\left ( \frac{m}{(m - m_{1})} \right )$


В отличии от алгоритма HyperLogLog, алгоритм LinearCounting имеет наибольшую точность для небольших множеств, при этом эта точность выше теоретической точности алгоритма HyperLogLog. А это именно то что нам и нужно! Но при увеличении мощности множества растет и погрешность, так как возрастает вероятность коллизий.

Теперь нам нужно понять, как мы можем применить LinearCounting. Для применения алгоритма нам нужно знать число возможных значений хеш-функции, и число различных хешей, появившихся в потоке. В качестве значений хеш-функции возьмем значения индексов (их у нас $m$), а чтобы понять, появился ли хеш с данным индексом в потоке, достаточно посмотреть на ранг соответствующего регистра. Если мы не получали такой индекс, то ранг будет равен начальному значению 0, но если получили, его ранг будет не меньше 1, так как $rank = clz(hash) + 1 \geq 0 + 1$.

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

Отлично, мы теперь мы можем оценивать небольшие множества, но когда нам стоит применять LinearCouning, а когда HyperLogLog? Наиболее естественный ответ — пока LinearCouning точнее. К сожалению, алгоритм LinearCouning не имеет простой формулы для погрешности, поэтому исследуем ее эмпирически: посчитаем погрешности оценки для большого количества множеств. Аппроксимируем кривую, описывающую погрешность алгоритма. Для определенности будем фиттировать полиномом 4 степени. Определим, в какой точке $E$ его погрешность начинает превышать погрешность алгоритма HyperLogLog. Тогда для оценок меньше $E$, будем применять алгоритм LinearCouning, а для больших — HyperLogLog.

Измерив эти границы для различных параметров точности, могу сказать, что, границу можно оценить грубо как $2m$, это эмпирический факт, который нам понадобится в будущем.

Получим следующий график для погрешностей:


После применения вышеизложенных техник получим следующую зависимость погрешности от оценки для нашего алгоритма:


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

Но это нас не остановит и мы будем дальше улучшать алгоритм.

Sparse representation


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

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

Вместо того, чтобы хранить 64-битный хеш, мы можем хранить пару из ранга и соответствующего хешу индекса. Для ранга нам нужно 6 бит, а для индекса мы можем взять даже больше бит, чем того требует алгоритм, но не меньше. Для удобства под индекс отдадим 26 бит. Тогда пару будет удобно хранить в 32-битном числе, и она будет иметь следующую структуру: в первых 26 битах будет храниться индекс, а в последних 6 — ранг. Используя пары, мы добьемся большей точности оценки и станем экономнее расходовать память.

При этом, хранение хешей может быть не такой уже и плохой идеей. Хотя размер хеша и в два раза больше размера пары, точность такой оценки при хранении хешей будет не меньше точности алгоритма HyperLogLog с параметром точности равным 64, $error < \frac{1,04}{\sqrt{2^{64}}} \approx 2,4 \times 10^{-10}$, точность оценки при использовании пар будет равна $\frac{1,04}{\sqrt{2^{26}}} \approx 1,27 \times 10^{-4}$, что не так уж и плохо.

Фактическая же погрешность будет меньше, так как при при использовании разреженного представления мы можем хранить не больше $m \times \frac{bitsize(register)}{bitsize(pair)} = m \times \frac{6}{32} < m$ пар, при этом граница алгоритма LinearCouning порядка $2m$, а значит в разреженном представлении для оценки мы всегда используем LinearCouning.

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

Условие перехода — размер массива пар превышает размер массива регистров. Для перехода нужно уметь восстанавливать индекс соответствующего регистра и его ранг. Ранг уже хранится в паре, осталось восстановить индекс.

Напомню, что для расчета индекса, мы просто берем последние $precision$ бит в хеше. В разреженном представлении $precision = 26$, значит в паре хранятся последние 26 бит оригинального хеша. Если бы мы получили этот же хеш, используя плотное представление, мы бы взяли уже последние 18 бит этого хеша. Очевидно, последние 18 бит хеша содержатся в последних 26 битах хеша. Для получения индекса регистра достаточно отбросить первые $26 — precision$ бит из индекса пары.


Применив разреженное представление, получим следующих график для погрешности алгоритма. 


Как и ожидалось, оценки малых множеств оказались наиболее точными. Потом наблюдается  резкий скачок, при переходе от разреженного представления к плотному, и начинается область применения алгоритма LinearCounting.Точность оценки все еще выше точности алгоритма HyperLogLog, но она растет и, достигнув погрешности алгоритма HyperLogLog, мы начинаем использовать алгоритм HyperLogLog c коррекцией, а дальше и в чистом виде.

Желающие могут ознакомиться с моей реализацией: github.com/KaitmazianMO/TSoC-HyperLogLog.

Неожиданно, операции над множествами


Алгоритм позволяет оценивать мощности не только множеств, но также и объединения множеств, не теряя при этом точности. Чтобы посчитать мощность объединения множеств A и B, нужно сопоставить каждому множеству соответствующую HyperLogLog структуру $HLL(A)$ и $HLL(B)$. Используя эти структуры мы можем построить новую структуру $HLL(A + B)$, содержащую объединение этих множеств. Для этого давайте рассмотрим как будет вести себя ранг одного из регистров, при добавлении элементов. 

Если мы добавим все элементы из множества A, тогда ранг будет равен максимальному рангу в этом множестве, соответствующему рассматриваемому регистру, аналогично для множества B. Если же мы добавим все элементы из A и все элементы из B, тогда в регистре уже будет содержаться максимальный ранг для объединения множеств, который равен максимуму из соответствующих максимумов для множеств A и B. То есть $rank_i(A + B) = max(rank_i(A), rank_i(B))$.

Значит при построении $HLL(A + B)$ нам нужно записать в его регистры максимальные ранги из множеств A и B. При этом погрешность оценки не изменится, так как полученная структура будет идентична структуре, в которую добавили все элементы из множеств A и B.

Умея оценивать мощность $A + B$, мы можем оценить мощность $A \: and \: B$. В этом нам поможет школьная формула: $\left|A \: and \: B\right| = \left|A\right| + \left|B\right| — \left|A + B\right|$. Но погрешность при этому уже будет больше теоретической, она будет складываться согласно формуле: $err(\left|A \: and \: B\right|) = err(\left|A\right|) + err(\left|B\right|) + err(\left|A + B\right|)$.

Аналогично можно оценить мощность разности множеств: $\left|A \setminus B\right| = \left|A + B\right| — \left|B\right|$. Погрешности снова будут складываться: $err(\left|A \setminus B\right|) = err(\left|A + B\right|) + err(\left|B\right|)$.

Для чего это может быть полезно? Мы можем быстро оценивать число элементов, удовлетворяющих сложным условиям поиска. Например, торговая площадка может оценить для пользователя, сколько ноутбуков обладает 4 или 6 или 8 ядрами, и при этом в них установлена IPS матрица и SSD диск. Если для всех условий будет заранее построена структура HLL, это оценку можно сделать почти моментально, за $O(m) = O(1)$.

Для углубления в тему рекомендую несколько материалов, на которые я опирался при подготовке статьи и реализации алгоритма: 

Скачать Tarantool можно на официальном сайте, а получить помощь — в Telegram-чате.

Комментарии (38)


  1. sergeyns
    18.01.2023 14:31
    #25128050
    +4

    Всё равно не понял как вы

    Оцениваем мощность множества за O(1)

    если вы сначала пропускаете весь поток чтобы посчитать хэши и их частоту..


    1. vadimr
      18.01.2023 14:44
      #25128108
      +5

      O(n), конечно, должно быть


    1. UngiftedPoet Автор
      18.01.2023 16:33
      #25128644
      +1

      Правильнее будет O(n), O(1) это стоимость оценки уже добавленного множества. Мне почему-то казалось, что это выдающееся свойство алгоритма, хотя обычное множество умеет также. Но зато у HyperLogLog'a все операции имеют сложность O(1) и потребляемая память O(1), что его выгодно выделяет при работе с большими объемами данных.


      1. ris58h
        18.01.2023 18:59
        #25129244

        и потребляемая память O(1)

        Что-то не верится. Где об этом почитать?


        1. UngiftedPoet Автор
          18.01.2023 19:13
          #25129302

          В самой статье есть формула для потребляемой памяти: m * 6bit, где m — константа алгоритма, если быть более точным, потребляемая память будет O(m), что есть O-большое от константы.


          1. klyusba
            18.01.2023 19:32
            #25129346
            +1

            m оценивается исходя из размера множества и требуемой точности оценки. То есть не является константой. Реальная потребляемая память будет O(log n) при фиксированной точности. Подробнее на википедии


            1. UngiftedPoet Автор
              18.01.2023 20:25
              #25129512
              +3

              m не оценивается, а определяется параметром точности алгоритма как 2^precision. В некоторых реализация, например от Redis, пользователь не может задавать точность алгоритма, а значит и определять m при инициализации.

              m остается неизменным во время работы алгоритма и не зависит от мощности оцениваемого множества, поэтому я считаю что это константа. Требуемая для алгоритма память определяется m, а значит она тоже постоянна.

              В моих тестах, при фиксированном параметре m, а значит и потребляемой памяти, точность оценки не превышала теоретическое значение для мощностей в диапазоне от 0 до 2^28, большие мощности я не исследовал. Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.

              Если вы со мной не согласны, то, объясните, пожалуйста, при каких условиях потребляемая алгоритмом память может начать превышать m * 6bit.


              1. vadimr
                20.01.2023 10:07
                #25134956
                -1

                Поэтому я придерживаюсь мнения, что точность оценки скорее не зависит от мощности множества, если, конечно, мощность не порядка 2^64.

                Вопрос оценки логарифмической сложности O (log n) вообще не имеет особого смысла на маленьких числах вроде 64. Надо устремлять размер множества ближе к бесконечности :) и там смотреть.

                Совершенно очевидно, что память в данном случае не может иметь оценку O(1), так как при общем времени работы алгоритма O(n) нужна работающая на каждом шаге за O(1) по времени хеш-функция, а такая (не итеративная) хеш-функция должна иметь хеш-таблицу, размер которой зависит от n. При хеш-функции недостаточной разрядности вы просто в самом начале обработки множества переберёте все возможные значения хеш-функции, и дальнейшие элементы множества не будут никак влиять на оценку. Таким образом, на самом деле память расходуется на хеш-таблицу, а не на ваш массив m*6.

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


                1. UngiftedPoet Автор
                  20.01.2023 11:29
                  #25135682
                  +1

                  Я не понимаю зачем вам хеш-таблица. Алгоритм работает с хешами. Хранить элементы или хеши не нужно. Поясните, если не согласны.

                  В чем вообще смысл такого алгоритма, если мы параллельно строим хеш-таблицу с добавляемыми элементами?


                  1. vadimr
                    20.01.2023 11:33
                    #25135700
                    -1

                    Посмотрите, как внутри устроена хеш-функция, с помощью которой вы вычисляете хеш-значение от данного элемента. Там либо таблица, либо цикл (на практике всегда таблица, так как небольшое количество памяти дешевле времени). Это не добавляемые элементы, а просто набор констант, представляющих собой, например, коэффициенты полинома n-й степени.


                    1. mayorovp
                      20.01.2023 11:54
                      #25135784

                      Но ведь ни размер этой таблицы, ни количество итераций этого цикла от количества элементов на входе не зависит.


                      1. vadimr
                        20.01.2023 12:04
                        #25135824

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

                        Например, если у нас на входе множество из 2^64 различных значений, то нам понадобится не менее чем 64-разрядная хеш-функция, чтобы значительно не потерять в точности оценки. Если у нас множество из 2^64000 значений, то понадобится 64000-разрядная хеш-функция.

                        64000-разрядная хеш-функция будет сложнее 64-разрядной либо по времени, либо по памяти.

                        Это несколько умозрительные цифры для реальных задач, но такова уж оценка O(log n).


                      1. UngiftedPoet Автор
                        20.01.2023 12:13
                        #25135870

                        Если у нас множество из 2^64000 значений, то понадобится 64000-разрядная хеш-функция.

                        Во вселенной атомов меньше.

                        На практике вам вряд ли придется оценивать множество размером больше 2^64, но если вдруг придется, то для оценки множества разменом меньше 2^128 нам придется просто добавить 1 бит к регистру.


                      1. vadimr
                        20.01.2023 12:15
                        #25135888

                        Мы говорим о теоретической оценке.


                      1. UngiftedPoet Автор
                        20.01.2023 12:22
                        #25135912
                        +2

                        В теории оно может и так, но на практике очень сложно найти задачу задачу подсчета масштаба 2^64. Но если вдруг придется, то HyperLogLog справится с этой и большими задачами лучше всех известным мне алгоритмов.


                      1. mayorovp
                        20.01.2023 12:29
                        #25135938

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


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


                      1. UngiftedPoet Автор
                        20.01.2023 12:38
                        #25135976

                        ИМХО, хеш-функция переменной разрядности это слишком. Все известные мне реализации используют 32, 64 или 128 битные хеш-функции и я не вижу в этом проблемы.

                        Не ужели так сложно гарантировать, что оцениваемое множество будет меньше 2^64 или даже 2^128?

                        при больших n оценка сильно теряет в точности

                        Только если мы приближаемся к верхней границе множества, тогда оценку придется скорректировать, как это делают в 32-битной реализации, в 64 битной считают что мы никогда не приблизимся верхней границы и забивают.


                      1. vadimr
                        20.01.2023 13:08
                        #25136140
                        +1

                        Если вы гарантируете, что множество будет меньше 2^128, то разговоры о сложности O (log n) вообще не имеют смысла, так как 128 – маленькое число.


                      1. UngiftedPoet Автор
                        20.01.2023 14:01
                        #25136346

                        Не понимаю, почему вы оцениваете как O(log n).
                        Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).

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


                      1. vadimr
                        20.01.2023 14:15
                        #25136398

                        Не понимаю, почему вы оцениваете как O(log n)

                        Потому что значение хеш-фунции, имеющей мощность N, записывается в виде двоичного числа длиной log2 (N) разрядов, для вычисления которого необходимо выполнить не менее чем порядка log2 (N) операций или сохранить в таблице порядка log2 (N) предвычисленных значений. А log2 (N) равен log (N) с точностью до константы, поэтому двойка в оценке сложности опускается.

                        Давайте сойдемся на том

                        Я бы не против, но мы не на рынке ;) Это строгая математика.

                        Точная формула требуемой памяти для оценки множества размером не больше чем n следующая: m * log2(log2(n)).

                        Выше вам приводили ссылку на точную оценку в википедии, по объёму памяти получается O (eps^-2 * log (log (n)) + log (n)), где первое слагаемое связано с самим алгоритмом HyperLogLog, а второе – как раз с вычислением хеша.


                      1. UngiftedPoet Автор
                        20.01.2023 15:27
                        #25136766

                        Если мы все-таки согласимся на ограничение размера множества множества, замечу, допустимое для всех практических задач. То даже O (eps^-2 * log (log (n)) + log (n)) будет константой.

                        Я хочу сказать, что все известные мне реализации работают с ограниченными множествами, и поэтому задействуют постоянные объемы памяти.
                        Математически, возможно, вы правы. Но на практике потребляемая память всегда постоянна и определяется формулой m * log2(log2(n)). Это просто удобнее и почти ни в чем нас не ограничивает.


                      1. vadimr
                        20.01.2023 13:06
                        #25136130

                        Не понял, почему это нужно выбрать до начала алгоритма.

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


                    1. UngiftedPoet Автор
                      20.01.2023 11:58
                      #25135804

                      Хеш-функция преобразует поток байт в чиселки, обычно, используя цикл. Объясните, пожалуйста, как таблица может помочь в вычислении хеш-функции.


                      1. vadimr
                        20.01.2023 12:08
                        #25135846

                        С циклом – это упрощённая реализация, для понимания сути алгоритма хеширования. На практике цикл никто не запускает, так как некоторые получаемые в цикле значения можно предвычислить и записать в массив в виде констант.

                        Посмотрите, например, для начала реализацию CRC16 в виде цикла и в виде таблицы. Это один из самых простых алгоритмов.

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

                        Если же вы будете для вычисления хеш-функции запускать цикл, то не уложитесь в O(n) по времени, так как каждый из n шагов займёт больше О(1).


                      1. UngiftedPoet Автор
                        20.01.2023 12:28
                        #25135936

                        Поделитесь, пожалуйста, реализацией CRC16, в которой не будет цикла.


                      1. vadimr
                        20.01.2023 13:26
                        #25136206

                        Циклический, табличный.

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


                      1. UngiftedPoet Автор
                        20.01.2023 13:42
                        #25136268

                        Но тут же есть цикл

                        uint16_t // Returns Calculated CRC value
CalculateCRC16(
    uint16_t crc,      // Seed for CRC calculation
    const void *c_ptr, // Pointer to byte array to perform CRC on
    size_t len)        // Number of bytes to CRC
{
    const uint8_t *c = c_ptr;

    while (len--)
        crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];

    return crc;
}

                        Есть отличные хеш-функции, не использующие таблицы. Например, Murmurhash, который я применял.


                      1. vadimr
                        20.01.2023 13:55
                        #25136326
                        -1

                        Тут цикл, потому что таблица у вас побайтная, а считается crc для len байтов.

                        Есть отличные хеш-функции, не использующие таблицы. Например, Murmurhash, который я применял.

                        В murmurhash таблица из 4 элементов прописана в самом коде, в однотипных группах по 4 логические операции с разными коэффициентами. Если бы значение murmurhash было не 4-байтовым, а 400-байтовым, там было бы по 400 присваиваний в группе, или массив на 400 элементов, или цикл на 400 итераций.

                        Вот, кстати, прекрасное практическое упражнение: написать 64-разрядный murmurhash.


                      1. UngiftedPoet Автор
                        20.01.2023 14:02
                        #25136360

                        А как это влияет на асимптотику алгоритма?

                        И что вы имели в виду, когда говорили?

                        На практике цикл никто не запускает


                      1. vadimr
                        20.01.2023 14:19
                        #25136414
                        -1

                        А как это влияет на асимптотику алгоритма?

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

                        И что вы имели в виду, когда говорили?

                        На практике цикл никто не запускает

                        Что цикла по разрядам числа в практически используемых алгоритмах нет.


              1. alexeibs
                20.01.2023 12:30
                #25135942
                +1

                У вас в статье есть формула для подсчета estimate. Очевидно, что у этой функции есть максимум, который достигается, когда во всех потоках мы видим max(rank), т.е. нулевой хэш. Выше этого значения при фиксированном m оценку мы не увидим. Можно провести мысленный эксперимент: перебирать натуральные числа до бесконечности. В какой-то момент, перебрав N натуральных чисел, мы достигнем максимальной оценки. Поскольку числа мы перебираем до бесконечности, то для любого фиксированного m найдется некое N, при котором максимальная оценка будет достигнута. Соответственно m надо подбирать исходя из максимального числа уникальных элементов множества, которое мы ожидаем. Понятно, что на практике 64-битного хэша может быть достаточно в большинстве случаев, но мы же тут про асимптотику говорим.


                1. UngiftedPoet Автор
                  20.01.2023 12:47
                  #25136028

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


  1. begemot_sun
    18.01.2023 20:05
    #25129448
    +1

    Вот тут мой топик на тостере про вероятностные алгоритмы. Достаточно много интересного можно найти по ссылкам.

    https://qna.habr.com/q/91971

    Добавляйте еще туда, если что-то знаете.


  1. svpcom
    18.01.2023 20:24
    #25129510
    +1

    https://github.com/svpcom/hyperloglog


  1. Stefanio
    19.01.2023 17:28
    #25133124

    https://twitter.github.io/algebird/datatypes/approx/hyperloglog.html


  1. ryad0m
    19.01.2023 20:16
    #25133586

    https://neerc.ifmo.ru/wiki/index.php?title=Участник:Warmte


  1. vadimr
    20.01.2023 10:49
    #25135102
    +3

    Для чего это может быть полезно? Мы можем быстро оценивать число элементов, удовлетворяющих сложным условиям поиска. Например, торговая площадка может оценить для пользователя, сколько ноутбуков обладает 4 или 6 или 8 ядрами, и при этом в них установлена IPS матрица и SSD диск. Если для всех условий будет заранее построена структура HLL, это оценку можно сделать почти моментально

    Так не покатит. В данном случае для пользователя очень существенной будет разница между ответами 0 или 1, а для алгоритма это допустимая погрешность.


    1. UngiftedPoet Автор
      20.01.2023 12:51
      #25136054
      -1

      Да, вы правы, есть такая проблема, если результирующее множество порядка погрешности. Магазину такую ситуацию обнаружить не сложно. Лично для меня подобный обман на 1 не был бы ОЧЕНЬ существенным, я бы просто упростил условия поиска.

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

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