いらっしゃいませ。Programming SHOT BARへようこそ。
プログラムはアルゴリズムがよく語られますが、もうひとつ主要な材料があります。
それは、データ構造です。
適切なデータ構造を選べば、アルゴリズムはシンプルにすっきりします。
マッチしないデータ構造ではフォローのためにアルゴリズムが複雑になりますし、
性能も劣化してしまいます。
まさにプログラムはアルゴリズムとデータ構造のカクテルと言えましょう。
集計処理
業務で実績データを元に集計することはありませんか？
表示形式としては2次元の表になることが多いと思います。
2次元のデータを表現するときに、真っ先に思いつくのは2次元配列でしょう。*
配列の最大の弱点は配列長が不変であることです。
この点は可変長配列、というかいわゆるコレクションAPIのjava.util.Listを使えば解決できますが、
2次元のListではインデックスが分かっていないと該当のオブジェクトにアクセスできません。
インデックスよりjava.util.Mapのような、いわゆるハッシュテーブルの方が勝手がよい場合も多いです。
そこで、Map型を格納したMapを考えることにいたるわけですが、
この最大の弱点は外側のMapのキー → 内側のMapのキーという順序でしかアクセスできないところです。
配列やListの場合はインデックスでのアクセスなので逆順でもアクセスできるのですけどね。
Mapの2次元化
Mapを2次元にする場合、キーの順序が固定化される問題を解決しなければなりません。
ここはひとつ、原始的に冗長化して解決してみましょう。
ソースが200行ほどになったので別途ダウンロードしてください。
TableMap.java
部分的にだけ解説します。
* @param <XT> X方向のキーの型
* @param <YT> Y方向のキーの型
* @param <V> 値の型
*/
public class TableMap<XT, YT, V> {
/** Xキーのソートに用いるComparator */
Comparator<XT> xComparator;
/** Yキーのソートに用いるComparator */
Comparator<YT> yComparator;
/** X → Y の順で値に到達する木 */
TreeMap<XT, TreeMap<YT, V>> xTree;
/** X → Y の順で値に到達する木 */
TreeMap<YT, TreeMap<XT, V>> yTree;
ジェネリクスの型パラメータはキーキーはX方向とY方向の２つ、それから格納するデータ型とで3つとなります。
内部情報として保持するのはソート用のComparatorが2種、X方向のキーのものと、Y方向のキーのもの。
それから、X→Y順でエントリにアクセスするための2段TreeMap、Y→X順のTreeMapとなります。
冗長化して状態をもつので、不整合が起こると早期に検出してExceptionをthrowするようにしてあります。
変わったところというと142行目からの
// 2段目ツリーが空になった場合
// エントリを削除
if (xEntry.isEmpty() ^ yEntry.isEmpty()) {
throw new IllegalStateException("内部状態の不整合");
}
ここで、if文でXOR演算子を使っています。こんなときでもないと使いませんからねぇ…。
作成秘話
実はこのクラス、3代目です。
最初に2次元のMapを思いついたのは1年以上前に業務で集計処理を書いているときだったのですが、
当初は2次元配列を作って自前でObject#hashCode()でインデックスを決めて～とガリガリ作っていました。
リハッシュとかもあってえらく難しい作りになってしまったのですが、
Mapの実装をjava.util.HashMap式ではなく、2分木にしたらどうかと思ったのです。
それで、自前で2分木を作ってたんですが、エントリのクラスを作ってVisitorパターンで
エントリを走査するようになってコード量も多いし難しいものになってしまいました。
しかし、単にjava.util.TreeMapを重ねるだけの作りにしたら偉くすっきりしてしまったというわけです。
2分木方式だとアクセスコストが高いので、ハッシュ式も綺麗に作り直したいところですね。
* Javaには厳密には2次元配列はなく、正確には配列型の配列となりますが、
実際には非矩形配列として使うことはレアケースですね。
投稿日時 : 2007年8月25日 14:40