Подсчет уникальных элементов
В мире больших данных одна из частых задач — подсчет уникальных элементов (distinct elements counting). Например, сколько уникальных пользователей зашло на сайт, сколько разных IP-адресов обратилось к серверу или сколько уникальных поисковых запросов было введено.
SELECT count(DISTINCT ip)
FROM web_events;В общем, точные методы (например, хэш-таблицы) требуют много памяти, особенно при огромных объемах данных. Здесь на помощь приходят вероятностные алгоритмы, такие как LogLog, которые позволяют оценить количество уникальных элементов с высокой точностью, но с минимальными вычислительными ресурсами.
Пример использования
Допустим, у нас потоковые данные, и мы хотим оценить, сколько в нём уникальных элементов.
Шаг 1: Хеширование элементов
Каждый элемент преобразуется в хеш (ну например, с помощью хеш-функции SHA-1). Хеш выглядит как длинная строка из 0 и 1.
Логично, что хеш элементов A и B повторяется, потому что элементы повторяются.
Шаг 2: Подсчёт ведущих нулей
чем больше ведущих нулей, тем «уникальнее» элемент
Шаг 3: Разбиение на «корзины» (buckets)
Чтобы улучшить точность уникальных элементов, LogLog разбивает хеши на несколько групп (корзин). Пусть, у нас для простоты будет 4 корзинки. Как распределить элементы по корзинам?
log₂(4 корзины) = 2 , значит берем первые 2 бита хеша каждого элемента и переводим их в десятичное число — это и будет номер корзины.
Шаг 4: Запоминаем максимум нулей в каждой корзине
Теперь для каждой корзинки сохраняем максимальное число ведущих нулей среди её элементов, взяв эту информацию из Шага 2. Естественно, если корзина пустая, то считаем 0
Шаг 5: Вычисляем оценку уникальных элементов
Оценка = число корзинок × 2среднее значение максимумов
Среднее значение максимумов = (0 + 0 + 0 + 5) / 4 =1,25
Оценка = 4 × 21,25 ≈ 9.52
Но у нас всего 4 уникальных элемента, а LogLog дал ~9.52 — это ❗️большая погрешность ❗️
А если попробовать увеличить количество корзин ❓
Плюсы алгоритма
- Экономия памяти – Вместо хранения всех уникальных элементов LogLog использует фиксированное число счетчиков (например, 256 байт).
- Масштабируемость – Точность зависит от числа «корзин», но не от размера данных.
- Быстрая обработка – Каждый элемент обрабатывается за O(1), что критично для потоковых данных.
LogLog – это интересный подход для приблизительного подсчета уникальных элементов с минимальными затратами памяти. Но если нужно еще более точное решение, можно рассмотреть его улучшенные версии –HyperLogLog.