Я так не думаю. Или ты можешь?
Случаи использования
- Подсчитайте количество уникальных просмотров видео TikTok.
- Получите уникальное количество подписчиков для профиля Instagram.
- Показать общее количество уникальных подписчиков канала YouTube.
Все в постоянное время и в режиме реального времени без использования многих ресурсов.
Гиперлоглог
Гипер что теперь?
Именно этот алгоритм мы и обсудим в этой статье. Это используется для получения количества уникальных значений примерно за постоянное время.
Хотя вам не нужно реализовывать этот алгоритм для использования в своем продукте (существует множество инструментов, обеспечивающих эту реализацию, например Redis HyperLogLog), знание того, как он работает, было бы полезно для вас в некоторых других случаях использования. .
Прежде чем мы двинемся дальше, это приблизительный подсчет, и он будет работать отлично, когда у вас большой набор данных (не 10, а 1000 пользователей).
Теперь давайте построим это шаг за шагом.
Алгоритм Флажоле-Мартина
Теперь этот алгоритм позволяет подсчитывать миллионы уникальных просмотров в режиме реального времени, просто используя палец.
Для удобства предположим, что все идентификаторы пользователей являются целыми числами (используя некоторую хеш-функцию).
Алгоритм — отслеживайте самую длинную последовательность начальных нулей, которую вы видели до сих пор в идентификаторах пользователей.
Например, если вы получаете идентификатор пользователя как 187292, то самая длинная последовательность нулей равна 0 (это уникальные пользователи).
Когда вы получите 002102, самая длинная последовательность и результат будут 2.
Как это работает?
Когда вы получаете более 10 идентификаторов пользователей, самая длинная последовательность нулей, скорее всего, будет равна 1. (Поскольку 10 идентификаторов пользователей будут уникальными и, по крайней мере, они должны быть от 1 до 10)
Точно так же, когда вы получаете более 100 идентификаторов пользователей, самая длинная последовательность нулей, скорее всего, будет равна 2.
Точно так же, когда вы расширяете его, в среднем последовательность из k нулей будет встречаться один раз на каждые 10ᴷ элементов.
Теперь это имеет огромный процент ошибок.
Например, если вы получите первый идентификатор пользователя как 000003, то вас разорят.
Улучшение — ЛогЛог
Алгоритм. Разбейте идентификаторы пользователей (значение хеш-функции) на сегменты, а затем возьмите среднее число начальных нулей для всех сегментов.
Допустим, мы берем 4 корзины, тогда мы можем использовать первые два бита вывода хеш-значения в качестве индекса корзин и остальных битов для вычисления начальных нулей. Предположим, что у нас есть четыре элемента и мы получаем их хеш-значения:
Hash(x1) = 100101: 2-е (10) ведро прямо сейчас с самой длинной последовательностью ведущих нулей = 1 (0101)
Hash(x2) = 010011: 1-е (01) ведро прямо сейчас с самой длинной последовательностью ведущих нулей = 2 (0011)
Hash(x3) = 001111: 0-е (00) ведро прямо сейчас с самой длинной последовательностью ведущих нулей = 0 (1111)
Hash(x4) = 110101: 3-е (11) ведро прямо сейчас с самой длинной последовательностью ведущих нулей = 1 (0101)
Теперь среднее значение самых длинных начальных нулей всех сегментов равно (0+2+1+1)/4 = 1. Следовательно, наша оценка здесь равна 4 * ²¹.
Хотя это немного снизило количество ошибок, мы все еще можем улучшить.
Допустим, мы получаем самый длинный начальный нуль из ведра как 100, а затем снова разоряемся.
Снова лучше — SuperLogLog
Алгоритм: вместо усреднения по каждому сегменту берется среднее из 70 нижних значений сегмента.
Делая этот простой трюк, точность улучшилась (они сказали)
Конечный пункт назначения — HyperLogLog
Алгоритм — вместо обычного среднего/среднего вычислить гармоническое среднее, которое является обратной величиной (это просто означает 1/значение) средней величины обратных величин.
Почему среднее гармоническое?
Он хорошо справляется с большими выбросами.
Рассмотрим 1,2,4, среднее из которых равно 2,3, а для 2,4,6,100 это 28, что не очень хорошо. Это произошло из-за выброса 100.
Теперь среднее гармоническое 1, 2, 4 равно
3 / (1/1 + 1/2 + 1/4) = 3 / (1.75) = 1.714.
Теперь рассмотрим 2, 4, 6, 100:
4 / (1/2 + 1/4 + 1/6 + 1/100) = 4,32, что хорошо (не так далеко, как 28), поскольку среднее гармоническое хорошо справляется с большими выбросами.
Здесь большой выброс 100 игнорируется, потому что мы используем его обратную величину. Таким образом, мы получили среднее значение, на которое меньше влияют большие выбросы.
В заключение…
Теперь вы знаете способ подсчета уникальных значений в реальном времени с помощью HyperLogLog, который вам не нужно реализовывать. Как я уже сказал, есть инструменты, обеспечивающие это.
Дайте мне знать, что вы думаете.
Вот и все! Пожалуйста, дайте мне знать о ваших взглядах и комментарии ниже для любых разъяснений.
Если вы нашли для себя ценность в чтении этого, рассмотрите возможность поделиться им с друзьями, а также в социальных сетях 🙏
Кроме того, чтобы получать уведомления о моих будущих статьях, подпишитесь на мою рассылку ниже.
Блог кодов
Статьи об облачной архитектуре и программировании. Нажмите, чтобы прочитать «Блог кодов Рахула, публикация Substack…blogofcodes.substack.com»
