スキップしてメイン コンテンツに移動

大規模なデータをそれなりに効率良く計数できる Algorithm::LossyCount を書いた

ラベル:

要旨

Algorithm::LossyCount というモジュールを書きました。これを使うとそこそこメモリ効率良く大規模なデータの計数ができます。アクセスランキング集計とかに使えるんじゃないでしょうか。

動機

例えばブログホスティングサービスで HTTP サーバのアクセスログを集計して人気のあるブログ記事ランキングを出したいとします。
Perl でデータの出現頻度を計数するのはハッシュを使うのが鉄板なので、適当に書くとだいたいこんな感じのコードになると思います:
#!/usr/bin/env perl

use v5.18;

my %access_counts;
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    ++$access_counts{$access_log->{requested_article}};
}

my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}

sub is_article_request { ... }

sub parse_access_log { ... }
シンプルですね。
しかしブログの記事数はサービス全体で数千万から数億のオーダになります。一定期間に全記事にアクセスがあるわけではないにしろ、逐次計数していくとハッシュのキーが数千万件になってメモリが貧弱なマシンだと残念なことになります。
ところで Web ページのアクセス傾向に関しては Zipf の法則1が当てはまることが知られています。要するにアクセス数でソートしたグラフはロングテールで、超人気記事がごく少数あり、急激に坂を下ってほとんどアクセスのない記事がズラーッと並ぶグラフになります。 つまり計数ハッシュの中には低頻度で同順位のデータが大量に存在していることになります。集計したところで下位の順位なんか誰も見ないので無駄です。
こういうロングテールな大規模なデータが対象で、低頻度データの計数結果が多少不正確でも構わないような場合にメモリ効率良く計数するための近似アルゴリズムが Lossy-Counting2 です。 このアルゴリズムは入力が一定数追加される毎に低頻度データの計数結果を捨てていきます。高頻度データの計数結果はパラメータによりますが確率的にまず捨てられないので上位の結果は信頼でき、下位の低頻度データはナンヤカヤ・ウヤムヤにされます。

使い方

上記の例でハッシュを使っている箇所を Algorithm::LossyCount に置き換えるだけ。
#!/usr/bin/env perl

use v5.18;
use Algorithm::LossyCount;

my $counter = Algorithm::LossyCount->new(max_error_ratio => 0.005);
while (<>) {
    chomp;
    my $access_log = parse_access_log($_);
    next if is_article_request($access_log);
    $counter->add_sample($access_log->{requested_article});
}

my $access_counts = $counter->frequencies;
my @popular_articles = (
  sort { $b->[1] <=> $a->[1] }
  map { [ $_ => $access_counts{$_} ] } keys %$access_counts
)[0 .. 49];

say "Rank\tURL\tFreq.";
for my $i (0 .. $#popular_articles) {
  say join "\t", $i + 1, @{ $popular_articles[$i] };
}
add_sample メソッドにデータを渡すと対応するカウンタに1加算したことになります。frequencies メソッドで計数の結果がハッシュリファレンスとして返ります。 詳細は例によって perldoc 参照。

感想

状態を持ったオブジェクトは面倒くさかったです (小並感)。
Algorithm::LossyCount 0.02 で依存関係に Smart::Args が入っていますが消し忘れです。他に変更が無ければ来週にでも 0.03 をリリースします。
  1. ジップの法則 - Wikipedia ↩
  2. Manku, Gurmeet Singh, and Rajeev Motwani. "Approximate frequency counts over data streams." Proceedings of the 28th international conference on Very Large Data Bases. VLDB Endowment, 2002. ↩

コメント

コメントを投稿

このブログの人気の投稿

Perl の新 class 構文を使ってみる

Perl 5 のオブジェクト指向機能は基本的には Python の影響を受けたものだが、データを名前空間 (package) に bless する機構だけで Perl 4 以来の名前空間とサブルーチンをそのままクラスとメソッドに転換し第一級のオブジェクト指向システムとした言語設計は驚嘆に価する。 実際この言語のオブジェクトシステムは動的型付言語のオブジェクト指向プログラミングに要求されるおよそあらゆる機能を暗にサポートしており、CPAN には Moose を筆頭とした屋下屋オブジェクトシステムが複数存在しているがその多くは Pure Perl ライブラリである。つまり「やろうと思えば全部手書きで実現できる」わけである。 そういうわけで Perl のオブジェクト指向プログラミングサポートは機能面では (静的型検査の不在という現代的には極めて重大な欠如を除けば) 申し分ないのだが、しかし Moose その他の存在が示しているように一つ明らかな欠点がある。記述の冗長さだ。 コンストラクタを含むあらゆるメソッドは第一引数としてレシーバを受ける単なるサブルーチンとして明示的に書く必要があるし、オブジェクトのインスタンス変数 (a.k.a. プロパティ / データメンバ) は bless されたデータに直接的ないし間接的に プログラマ定義の方法 で格納されるためアクセス手段は実装依存である。これはカプセル化の観点からは望ましい性質だが、他者の書いたクラスを継承するときに問題となる。ある日データ表現を変更した親クラスがリリースされると突然自分の書いた子クラスが実行時エラーを起こすようになるわけだ。 そうならないためにはインスタンス変数へのアクセスに (protected な) アクセサを使う必要があるのだが、そのためには親クラスが明示的にそれらを提供している必要があるし、そもそも Perl にはメソッドのアクセス修飾子というものがないので完全な制御を与えるならばオブジェクトの内部状態がすべて public になってしまう。 そのような事情もあり、特にパフォーマンスが問題にならないようなアプリケーションコードでは Moose のようなリッチな語彙を提供するオブジェクトシステムを使うことが 公式のチュートリアルでも推奨 されてきた。Perl コアのオブジェクトシステムの改良は...
コメントを投稿
続きを読む

去る6月に Perl 5.32.0 がリリースされたので差分を把握するために perldelta を読んだ件

要旨 Perl 5 メジャーバージョンアップの季節がやって来たのでまともな Perl プログラマの嗜みとして perldelta を読んだ。 今回は有り体に言えばルーティン的なリリースで、言語コアの拡張は他言語にも見られる構文が実験的に入ったくらいで大きな変化はない。新機能は RegExp の拡充が主である。 比較的重要と思われる変更点を抜粋する。 新機能 isa 演算子 実験的機能。Python とか Java における isinstance とか instanceof 。 これまでも UNIVERSAL::isa があったが、これはメソッドなのでレシーバにオブジェクトでもクラスでもない値 (i.e., 未定義値 / bless されていないリファレンス) を置くと実行時エラーが起きるのが問題だった: package Foo { use Moo; } package Bar { use Moo; extends ' Foo ' ; } package Baz { use Moo; } use feature qw/ say / ; sub do_something_with_foo_or_return_undef { my ( $foo ) = @_ ; # Returns safely if the argument isn't an expected instance, in mind. return unless $foo -> isa ( ' Foo ' ); ...; } # OK. do_something_with_foo(Bar->new); # |undef| is expected in mind, but actually error will be thrown. do_something_with_foo( undef ); これを避けるために今までは Scalar::Util::blessed を併用したりしていたわけだが、 isa 演算子は左辺が何であっても意味のある値を返すのでよりシンプルになる: # True +( bless +{} ...
コメントを投稿
続きを読む

Project Euler - Problem 35

問題 原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答 回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。 追記 匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。 いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。 もっと追記 前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...
4 件のコメント
続きを読む

LIBLINEAR 2.41 で One-class SVM が使えるようになったので Perl から触ってみよう

改訂 (Sep 15, 2020): 必要のない手順を含んでいたのでサンプルコードと記述を修正しました。 CPAN に Algorithm::LibLinear 0.22 がリリースされました (しました。) 高速な線形 SVM およびロジスティック回帰による複数の機械学習アルゴリズムを実装したライブラリである LIBLINEAR への Perl バインディングです。 利用している LIBLINEAR のバージョンが LIBLINEAR 2.30 から LIBLINEAR 2.41 に上がったことで新しいソルバが追加され、One-class SVM (OC-SVM) による一値分類が利用可能になっています (しました。) OC-SVM って何 一値分類を SVM でやること。 一値分類って何 ある値が学習したクラスに含まれるか否かを決定する問題。 HBO の「シリコンバレー」に出てきた「ホットドッグ」と「ホットドッグ以外」を識別するアプリが典型。「ホットドッグ以外」の方は犬でも神でも一つの指輪でも何でも含まれるのがミソ。 二値分類の場合正反両者のデータを集める必要があるのに対して、一値分類の学習器は正例データのみしか要求しない (ものが多い。) 主な用途は外れ値検出で、もちろんホットドッグやホットドッグ様のものを検出したりもできる。 使い方 手順自体は他の二値ないし多値分類問題と同じです。つまり、 訓練パラメータを決めて 訓練データセットで訓練して テストデータセットで確度を検証して 十分良くなったらモデルを保存する といういつもの流れ。 訓練パラメータ use 5.032 ; use Algorithm::LibLinear ; my $learner = Algorithm::LibLinear ->new( epsilon => 0.01 , nu => 0.75 , solver => ' ONECLASS_SVM ' , ); solver => 'ONECLASS_SVM' が一値分類用のソルバです。LIBLINEAR の train コマンドで言うところの -s 21 。 OC-SVM の良いところは (ハイパー)...
コメントを投稿
続きを読む

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月 のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定 である。 現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。 そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文 見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。 もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。 昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である： 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる...
1 件のコメント
続きを読む