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

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

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

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

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

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

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

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

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

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

Не смог отказать себе в удовольствии и попрактиковаться в «Гоу», написал и выложил на Гитхаб реализацию алгоритма линейного счётчика на Гугл Гоу. Значения, которые надо подсчитать поступают на стандартный вход, есть один параметр командной строки — «size», позволяющий задать размер вектора в битах (по-умолчанию — 10000).

Подсчёт на моём ноуте одного миллиона уникальных значений занимает примерно 6,5 секунд. Погрешность с вектором длиной 100 тысяч бит (≈3КиБ) — 7,6%.

Чтобы скомпилировать программу новым (версии 1 и выше) компилятором «Гоу», нужно запустить следующую команду:

go build linear-counter.go

Отличная иллюстрация того как важны мелочи в документации…

Читал чужой исходный код на «Гоу» и обнаружил необычную конструкцию:

v &^= 1 >> n

Почесал голову, не понял что это и пошёл читать документацию. Выяснилось, что эту конструкцию я когда-то упустил при чтении документации и означает она «bit clear (and not)», то есть является противополжностью „|=“, не ставит бит, а очищает его. Более того, есть ещё унарная операция «^», которая инвертирует все биты в числе (соблюдая размер его типа), вот как они работают:

package main

func main() {
    var test byte = 250

    println(test) // 250 (11111010)
    
    test = ^test
    println(test) // 5 (00000101)

    test &^= 4   //    (00000100)
    println(test) // 1 (00000001)
}