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

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

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

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

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

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

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

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

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

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

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