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

Алгоритм линейного счётчика: десять бит в одном бите

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

Упомянул его в разговоре знакомый математик К.Н., за что ему большое спасибо! По этому алгоритму нашлась замечательная статья «Линейный счётчик», с понятным объяснением, добавить к которому нечего, но я всё-таки приведу у себя его краткое описание.

Сначала для чего алгоритм применяется и чем он замечателен.

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

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

Но есть способ лучше! Алгоритм линейного счётчика.

Оказывается, если взять вектор в 1000 бит и 1000 раз установливать в нём в единицу случайный (с равномерным распределением) бит (некоторые биты будут установлены в единицу несколько раз), то нулей останется примерно около 370. Эта оценка получается из 1/e ≈ 0,36787944117… ≈ 0,37, подробнее есть в другой статье на том же сайте.

Таким образом, если мы встречаем битовый вектор длины n, в котором примерно 63% (100 − 0,37 × 100 = 63) единиц, то над этим вектором было произведено n операций установки бита в единицу, при условии, что биты выбирались случайно и равномерно.

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

Демо алгоритма линейного счётчика (10.68КиБ)

Хорошо это работает только на больших числах, я для наглядности сделал небольшое демо работы алгоритма линейного счётчика, там пятьдесят входных значений и вектор размером в 30 бит. Так как чисел немного, то и результаты иногда скачут сильно, но на миллионах значений погрешность выравнивается.

8 комментариев
gplus.to/shedar 2013

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

Евгений Степанищев (bolknote.ru) 2013

Комментарий для http://gplus.to/shedar:

Проблема в некоторой непредсказуемости точности

Да, например если сильно не повезёт, всегда может устанавливаться только один бит :)

и в выборе количества бит

К сожалению, да. Иногда что-то известно о природе входных данных, тогда можно попробовать грубо сверху прикинуть.

Я в задаче приблизительного подсчета количества уникальных выбрал HyperLogLog

Спасибо, посмотрю его!

Евгений Степанищев (bolknote.ru) 2013

Комментарий для http://gplus.to/shedar:

Это позволяет не вести два счетчика

У меня точный счётчик ведётся, чтобы показать в конце насколько сильно алгоритм отклонился от реального значения, в алгоритме его нет на самом деле.

<wj4 (hayk.livejournal.com) 2013

Комментарий для Евгения Степанищева:

Очепятка: всретили.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для hayk.livejournal.com:

Спасибо, поправил!

Дрюха (andrei-mishchenko.ya.ru) 2013

функцией, которая даёт нормальное распределение

равномерное же

Евгений Степанищев (bolknote.ru) 2013

Комментарий для andrei-mishchenko.ya.ru:

Ваша правда! Непонятно почему я в этом месте про нормальное написал.