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

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

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

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

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

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

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

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

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

Отсюда, если взять битовый вектор достаточной длины, хешировать входные значения какой-то функцией, которая даёт равномерное распределение, из результата выбирать бит в нашем векторе и устанавливать его в единицу, а в конце подсчитать сколько единиц получилось, можно выяснить с хорошей вероятностью сколько уникальных значений было подано на вход (погрешность порядка 1% получается!). Демо алгоритма линейного счётчика (10.68КиБ) Хорошо это работает только на больших числах, я для наглядности сделал небольшое демо работы алгоритма линейного счётчика, там пятьдесят входных значений и вектор размером в 30 бит. Так как чисел немного, то и результаты иногда скачут сильно, но на миллионах значений погрешность выравнивается.
12 января 2013 15:45

http://gplus.to/shedar (инкогнито)
12 января 2013, 19:21

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

bolk (bolknote.ru)
12 января 2013, 19:50, ответ предназначен http://gplus.to/shedar

Проблема в некоторой непредсказуемости точности
Да, например если сильно не повезёт, всегда может устанавливаться только один бит :)
и в выборе количества бит
К сожалению, да. Иногда что-то известно о природе входных данных, тогда можно попробовать грубо сверху прикинуть.
Я в задаче приблизительного подсчета количества уникальных выбрал HyperLogLog
Спасибо, посмотрю его!

bolk (bolknote.ru)
12 января 2013, 19:51, ответ предназначен http://gplus.to/shedar

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

<wj4 (hayk.livejournal.com)
12 января 2013, 20:20, ответ предназначен bolk (bolknote.ru):

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

bolk (bolknote.ru)
12 января 2013, 21:26, ответ предназначен <wj4 (hayk.livejournal.com):

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

Дрюха (andrei-mishchenko.ya.ru)
13 января 2013, 00:58

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

pozadi.github.com (инкогнито)
13 января 2013, 03:56, ответ предназначен Дрюха (andrei-mishchenko.ya.ru):

http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5

bolk (bolknote.ru)
13 января 2013, 10:25, ответ предназначен Дрюха (andrei-mishchenko.ya.ru):

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

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)