Shipped Algorithm::HyperLogLog 0.01!

Perl

HyperLogLogアルゴリズムをPerlから使用するためのモジュール、
Algorithm::HyperLogLogをCPANにリリースしました。
XSモジュールですが、XSが使えない場合はPure Perlでも使えるように作ってあります。

HyperLogLog とは？

HyperLogLogは、ある集合の異なり数(カーディナリティ/cardinality)を少ないメモリ消費で推定するアルゴリズムです。
詳しくは以下の論文を読んで下さい。

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

なお、並列計算用に改善されたHyperLogLog++というアルゴリズムがGoogleによって開発されています。
http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/40671.pdf

使い方

use strict;
use warnings;
use Algorithm::HyperLogLog;
 
my $hll = Algorithm::HyperLogLog->new(14);
 
while(<>){
    $hll->add($_);
}

my $cardinality = $hll->estimate();

上記が典型的な使い方です。
new()の引数はレジスタのサイズを決定するパラメータ(4〜16の範囲で指定)で、14と指定するとレジスタのサイズは2^14 = 16384 byte となります。レジスタのサイズが大きいほうが推定の精度は高くなります。