キー毎に値を集計する方法

irofさんとdaiksyさんがTwitter上でキーブレイク処理について話していました。
（リストを項目ごとに集計する→「ブレイク処理」を定形のアルゴリズムとして習いました→こんな解りにくいの、なんで好んで書くんだろう）

キーブレイク処理というのは、データをキーでソートしておいて順番に読み込み、キーが同じ値の間に処理（よくあるのが集計）を続ける。キーが違う値になったら（キーがブレイクしたら）集計値を出力し、集計用変数をクリアしてまた処理を続ける。というアルゴリズムです。
ひとつ前のキーの値を保持しておく変数が必要で、最初はそれをどういう値にしておくか、また、ループを抜けた後に最後のキーの集計値を出力する必要があるか、といった辺りも考慮しないといけないので、慣れないと分かりづらいかもしれませんし面倒でもあります。

Javaだとキーブレイク処理はあまり見かけません。Javaでキー毎の集計処理を書くなら、irofさんのページに書かれているようにMapを使った方法が一般的だと思います。
（ただ、自分が書く場合はcontainsKeyは使わず、getした結果がnullかどうかで判定します。containsKeyとgetはMap内部で同じような探索を行うので、2回やるのは無駄に思えるからです）
（ScalaだとgetOrElseUpdateがあるのでもっと楽ですｗ
「val data = map.getOrElseUpdate(code, new Data(code))」という感じです。第2引数は関数で渡しているので、キーが存在しないときしかnewは実行されません）

ただし、irofさんが書いてらっしゃる通り、元がRDBならSELECT時に集計する（内部構造に詳しいRDBMSに任せる）のが一番だと思います！
“RDBMSが重くて遅いから、複雑なSELECTは書かずにJava側で集計する”なんて話も聞かなくはないですが…。

---

キーブレイク処理は、汎用機（メインフレーム）（COBOLやPL/Iが活躍している）のバッチ処理では常識的な手法です。（COBOLやPL/IでMap等のコレクションライブラリーがあるなんて話は聞いたことが無いですねー）

汎用機のバッチ処理は、ファイルを読み込んでファイルへ出力します。
ファイルをソートするユーティリティーも当たり前のように存在しています。
そこで、ファイルをキーでソートし、キーブレイク処理のバッチプログラムで集計する、というパターンが定型化しています。

それと、汎用機で扱うデータ件数はかなり多いという事に着目しておく必要があります。汎用機はJavaバッチでよく使われるハードウェアより高速なはずですが、それでも夜間バッチに数時間かかるというのはざらです。（少なくとも自分が担当していた頃は）

---

キーブレイク処理は面倒そうなアルゴリズムですが、コレクションに保持する方法と比べてメモリー使用量が圧倒的に少ないという利点があります。
なにせ必要なのは、古いキーを保持する変数と、集計をする変数だけ。

JavaでMapを使う場合、キーが1000万件もあったら、たぶんOutOfMemoryですね。（以前JRE1.4でやったときは200万件も持てませんでした）
コレクションを使って処理するときは、件数に気をつけましょう。大抵はテストでそんな大量データは試さないので、「出来ました！」って喜んで本番で動かしたら「落ちました！」って事になりかねません(汗)

---

さて、キー毎に集計すると言えば、それを専門に行うフレームワークがHadoopです。
（そういえば、このブログはhadoopアドベントカレンダー2011の5日目として書いています(爆)）（adventって、一定時間経ったら強制的に終了させられる事…とは違うんだなｗ）

HadoopはMapReduceというアルゴリズムで処理を行いますが（このMapは、Javaのjava.util.Mapとは全く関係ありません）、
Map（抽出・変換）→Shuffle（ソート）→Reduce（集計）
というフェーズで処理が進んでいきます。

もうちょっと具体的に言うと、Mapフェーズで集計に必要な項目だけ出力し、Shuffleフェーズで「キーでソート」し、Reudceフェーズで「キー毎に集計」を行います。
Reduceのプログラムは、JavaのReducerクラスのreduceメソッドをオーバーライドして記述しますが、このメソッドの引数はキーと値一覧です。キーの値ごとにreduceメソッドが1回ずつ呼ばれるので、値一覧を使って集計を行うのです。

つまりHadoopは、Shuffleフェーズでソートしたデータに対し、キーが同じ間だけ値を収集し、キーがブレイクしたらreduceメソッドを呼び出すという、キーブレイク処理をしている訳ですね。
（実際には、新たなキーになったらreduceメソッドが呼ばれ、キーがブレイクするまでreduceメソッド内で値を取得できる、という実装だと思いますけど）

---

汎用機やCOBOLは古いというんでよくネタにされ（自分もネタにして）ますが、キーブレイク処理のような古いかもしれないけど基本的なアルゴリズムは知っておいてもいいんじゃないかなーと思って、今回書いてみました。

（複数のファイルをソートしてから別々に読み込み、同一キーのレコードをマッチングさせる（片方のキーと他方のキーを比べ、小さい間はスキップし、同じ間だけ読み進める）とかも常套手段ですね。（これは何と呼ばれているんだろう？））

という訳で、キーブレイク処理をJavaで書こうと思ったら、Hadoopのソースを参考として見てみるといいかもしれませんね。
というか、キー毎に集計するなら、Hadoopを使うといいんじゃないですかね(笑)