Пояснение к алгоритму HyperLogLog
Прежде всего позвольте мне начать с того, что я прочитал этот вопрос.
Так что, прогуливаясь по Интернету, я наткнулся на этот алгоритм, и мне стало интересно, как он работает. Прочитав об этом, я понял, как он подсчитывает количество просмотров, используя хеширование и использование битов.
Что я еще не совсем понял, так это как можно избежать повторного подсчета того же представления. Сохраняем ли мы каждое хэшированное значение, с которым сталкиваемся, и перед увеличением счетчика проверяем, существует ли оно в нашем массиве или что-то еще?
Разве это не делает его намного менее эффективным, если у нас более 1000 000 предметов?
1 ответ
Крутая вещь в HyperLogLog заключается в том, что вам не нужно хранить весь массив, который вы видели, что было бы O(n)и даже не уникальные ценности. То, что вам нужно хранить, это от oreder O(log(log(n)) что намного ниже.
По сути, если два объекта имеют одинаковое значение, их хэш будет одинаковым. Это означает, что начальные биты также будут одинаковыми. Таким образом, наличие нескольких объектов с одинаковым значением никак не повлияет на вычисления.
Этот факт также позволяет легко распараллеливать - вы можете разделить население и рассчитать максимум отдельно, комбинируя их позже, вычисляя максимум ваших отдельных максимумов.