NSSetとライフゲーム（その3、ハッシュ）

さらにこないだの続き。

前回の下準備をして、生きたセルを表すGoLAliveCellを

#import "GoLPoint.h"

@interface GoLAliveCell : NSObject {
    GoLPoint        pos;
    int             age;
    unsigned int    hash;
}
- (id)initAt:(GoLPoint)position;
...

としよう。GoLAliveCellはその位置と何世代生き残っているかをインスタンス変数に持つ。位置は生まれたときに決まり、その後動かないとする。hashについては後でまとめて説明する。こうしておけばセルの領域は2^32x2^32（32ビットアーキテクチャで）の広さとなる。はじっこがどうなるかは命令セットの詳細やコンパイラに依存するが普通、整数演算の桁溢れは無視するので、上の実装で端の処理に特別なことをしなければ領域はトーラスになる。

GoLAliveCellには周囲との関係を表す

- (BOOL)isNeighbouringOf:(GoLAliveCell *)neib;
- (int)countNeighbouringOf:(NSSet *)neibs;
- (NSSet *)neighbours;

のメソッドを実装しよう。isNeighbouringOf:は引数のセルの隣（座標値がそれぞれ±1の範囲の周囲の8つのセルをこう呼ぶことにする）であるかどうかを返す。
countNeighbouringOf:は引数のNSSetの中のうち自分の隣にあるセルの数を返す。neighboursは隣全部の8個のセルをテンポラルに生成してそれをNSSetの中に入れて返す。

その他のメソッドとして

- (GoLPoint)position;
- (int)age;
- (void)setSurvive;

を実装しよう。Positionは位置を、ageは世代数を返し、setSurviveは1世代分生き残ったことをセルに知らせる。

これだけあれば基本的な動作は可能である。ただし、NSSetの要素としての動作をさせるためにもう二つのメソッドの追加が必要で

- (BOOL)isEqual:(id)otherCell;
- (unsigned int)hash;

を実装しなければならない。isEqual:は引数のセルと同じかどうか、つまり同じ座標値を持っているかどうかを返す。NSSetはこれを呼んで重複が無いように制御する。hashはいわゆるハッシュ値で、
1.同じ座標値を持つセルは同じ値を返さなければならない
2.座標値が違っているセルは同じでも違っていても良い
3.ハッシュ値は偏りの無い方が良い
という特徴を持つunsigned intであればなんでもよい。NSSetはこれを使って要素の比較の高速化を行う。従ってisEqual:よりもhashの方が速くなければ意味が無い。3番目の特徴は、同じハッシュ値を持つものは実際に同じであるかどうかを確認する必要があるが、それをなるべく速く行うための要請である。この他にももう少し微妙な要請がある場合もある。NSSetは比較的単純な実装になっているようである。

ハッシュ値の特性のうち2番目を厳しくして座標値が違っていれば必ず異なる値を返すようなハッシュのことを完全ハッシュと言う。完全ハッシュではハッシュ値を比較するだけで要素比較が可能になるが、NSSetは完全ハッシュを利用できるようにはなっていないようである。同時に存在し得る要素すべての個数がハッシュ値の取り得る数よりも大きければ完全ハッシュは存在しない。上のGoLAliveCellの実装では2次元の整数（座標値）の方が一つの符号無し整数（ハッシュ値）より多いので完全ハッシュにはならない。同時に存在し得る要素の個数がN個のときに1からNまで（C風に言えば0からN-1まで）の整数を割り当てるハッシュを最小完全ハッシュという。

ちなみに、今回のGoLAliveCellは構造が単純なので、単に領域のサイズを小さくすれば簡単に完全ハッシュであることを保証することができる。例えばこうである。
まず、GoLPointを

typedef struct GoLphPoint {
    short	x;
    short	y;
} GoLphPoint;

としてビット幅を半分にする。名前の間に挟んだ「ph」は「perfect hash」のつもり。
それを使って

@interface GoLphAliveCell : NSObject {
    union {
        GoLphPoint      pos;
        unsigned int    hash;
    }   ph;
    int age;
}

としてやる。

Cのunionでposとhashは同じものを別の方法で解釈することになる。ただしこの実装はコンパイラに依存する（shortがintの半分の幅でshort二つの構造体は詰まって保存されないといけない）。

インスタンス変数のhashはこのハッシュ値を保持してメソッドhashが呼ばれたときに返すためのものである。このGoLAliveCellでは死ぬまで位置は変わらないので、メソッドが呼ばれるたびに計算し直す必要は無い。

NSSetはどうやらハッシュ値の順に要素を並べておくらしい。すなわちハッシュテーブルで要素を保持しているようだ。NSNumberをNSMutableSetに持たせてNSEnumeratorで順に書かせると追加した順番に関係なく値の順に並ぶ。ハッシュテーブルの大きさをどうやって決めているかは良くわからなかった。ハッシュの話は奥が深くて面白そうだけどNSSetを使う上ではこれ以上突っ込んでもしょうがないので止めておく。
ハッシュ値の重複の大きさを変えたときNSSetの効率がどうなるかを調べたので全部の実装がすんだ後に紹介する。

今回はとりあえずここまで。なかなか進まんなあ。