[Programming][Algorithm]1行1ラベル形式で、1万種類のラベルを持つ、100万行のデータがあるとします(ラベルの頻度分布はジップの法則にだいたい準拠するとします)。各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。(1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。)しかし、カウント後に高頻度のものしか使わないということも多いと思います。頻度5000以上のもののみ取り出してあとはいらない、とか。なると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。低頻度のものを途中で適宜捨てていくことで必要なメモリ領域を小さくする方法なのです。簡単に言うと、入力データをブロック単位に分け、各ブロックの読み込み後に低頻度のハッシュエントリを捨てる感じです。「現ブロックでは頻度ゼロだけど過去の実績があるから捨てない」などの要素もあります。」[2010-05-11-1]の第6章をご参照ください。数理技法編)以下、サンプルプログラムで実演解説していきます。サンプルデータまずは実演で使うサンプルデータを準備します。1行1ラベル形式で、1万種類のラベルを持つ、100万行のデータで、ジップの法則に従うものを用意します。32210533358611924247単純カウントまずは単純な方法でカウントしてみます。10000出力フォーマットは、第1カラムがラベルで第2カラムがそのラベルの出現頻度です。プログラム内で使用する最大ハッシュエントリ数で、実行時のメモリ使用量の目安となります。ラベルは1万種類なので当然10000になります。method)」によるカウントプログラムです。203出力フォーマットは、第1カラムがラベル、第2カラムがそのラベルの出現頻度、第3カラムがバケット番号($b_current)です。バケット番号が0ではないやつは頻度に若干の誤差があるかもしれないことを意味します(番号が小さい場合は誤差はないです)。この辺は本を読んでください。比べかなり小さくなっていることが分かります。少ないメモリ容量で実行できるということです。最大ハッシュサイズの比較です。前述の例では50倍ほどの差があります(実際は各ハッシュエントリが持つデータ量が違うのですがそれでも25倍の差)。203カウント結果の比較です。LCM側でバケット番号が0じゃないものは太字にしています。ホゲホゲ!」とか「クラウドで5万円!」とかいろいろ心配になりがちです。高頻度のものを取り出したいだけならば、貧弱なマシン環境でもなんとかなる場合があります。ウェブサーバのログ解析もこういう高頻度チェック用途ならサクッと行けそうです。ブログ運営者宛のメッセージをこっそり送信できます(非公開)このブログ内の関連コンテンツ:。