NSSetとライフゲーム（その9、計算時間）：腰も砕けよ膝も折れよ：So-net blog

	ブログをはじめるログイン

NSSetとライフゲーム（その9、計算時間）　[プログラミング - NSSetとライフゲーム] [編集]

NSSetとライフゲームに関するメモはこれでおしまいにしよう。
IntefaceBuilderで必要最小限のUIを作る。
データやカラーテーブルをロードし、世代交替の制御をして、表示する。表示にはNSImageView使うのが簡単。

それで

こんなのにして、ビルド。

まず、Sharkでどこが律速してるか確認。あれ？Sharkの集計方法って変わった？
自分のメソッドで言うと-[GoLAliveCell isEqual:]が5.5%、-[GoLAliveCell position]が3.8%でこのへんが一番重い。呼ばれる回数が多いからで、結局隣のセルを探す、その数を数えるというのが一番時間がかかってる。これは要素数をNとするとN^2のオーダーになる。

おっと、Xcode3.0にしてから初めてSharkを使ったが、知らないFoundationのクラスがある。__NSFastEnumerationEnumeratorとか、例のやつですかい。まあ、これはまたこんどにして、何をやりたいかと言うと、Hashの値の重複（Hash値が同じでisEqual:ではNOのもの）がどのくらい実行速度に効くかと言うこと。Hashは

#define	foldingLength   16
static unsigned int     adoptingBits = ((1 << foldingLength) - 1);
....
    hash = ((pos.x & adoptingBits) << foldingLength) | (pos.y & adoptingBits);

としている。ちなみにisEqual:は

- (BOOL)isEqual:(id)otherCell
{
    GoLPoint    otherPos = [otherCell position];
    return (pos.x == otherPos.x) && (pos.y == otherPos.y);
}

で、そのまんまの比較をしている。

Hashはつまり、座標値の下位何ビットかを取り出して、x、yの二つをunsigned intに詰め込んでいるだけ。ビットバイトしてると言われそうだが、Hashはこんなもんでしょう。定数のfoldingLendthの値を大きくすれば重複は少なくなる。foldingLengthを0にすれば、hashメソッドはすべて同じ値0を返すことになり、hashが効かなくなる。このfoldingLengthの値に対して、所要時間を測定してみる。

初期データはF-ペントミノで200世代までの秒数を測る。NSSetの要素数（生きているセルの数）の最大は220くらいになる。その他の条件はMacOSX 10.5、PowerBookG4 1.33GHz 1.3GBメモリ、Xcode3.0、ビルド構成はreleaseのデフォルト。3回測って

ビット長さ  1回目   2回目   3回目
 0        40.3    39.9    40.0
 1        25.0    25.3    25.2
 2        21.1    21.0    22.7
 3        19.6    19.6    19.4
 4        18.9    18.9    18.9
 6        18.8    18.6    18.5
 8        18.7    18.4    18.6
16        18.7    18.8    18.5　（単位秒）

その平均を取ってグラフにすると、

おお、ほれほれ、Hashが効いてんじゃん！200世代ぐらいまでは座標値はどちらも±200に収まっていて、9ビットあればHash値は重複がないのでこの辺に漸近するのはもっともらしい。

こんな単純なデータでもHashの有無で倍半分と言う結果。最初からもっと要素数が多ければもっと差がついただろうし、さらに、一意性のチェックが難しい複雑なデータでは目の覚めるような効果が期待できるな。考えた人は偉い。必要に迫られてかもしれんけど。

今回のやり方では生きているセルの数が増えると急速に遅くなる。隣を探すために毎回総当たりをしているからで、これをやめれば早くなる。簡単で有効なやり方として隣のセルへのポインタを保持する、と言う方法がある。
自分に関係無いほとんどのセルを無視できて早くなるが、死んだセルへのポインタを持っていてもしょうがないので、世代交代ごとにそのポインタを更新しなければならない。これには一工夫が必要。ひとつのアイデアとして、「隣」と言う概念が対称（自分の隣のセルにとって自分は彼の隣）なのを利用してdeallocをオーバーライドして隣に知らせると言う手が考えられる。まあ、あまり汎用性のあるアルゴリズムじゃなさそうなので、またその気になったらやることに。

さて、当初の目標はF-ペントミノの最後を知ることだった。ということで、こんなんなりました。6機のグライダーが三方に飛び去って、真ん中辺にブロックや蜂の巣やブリンカーが散らばっている。