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

Алгоритм линейного счётчика на Google Go (golang)

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

Подсчёт 1 000 000 значений (8.81КиБ)

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

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

go build linear-counter.go
1 комментарий
hshhhhh (hshhhhh.name) 2013

% seq 1 1000000 | time ./linear-counter -size 100000
Vector size: 100000 bits
Estimated result: 972116
./linear-counter -size 100000 5.93s user 0.02s system 99% cpu 6.003 total

Железо у меня явно послабее будет :)