人気ブログランキング | 話題のタグを見る
インデックス法
同一チェックを、インデックス法を採用して工夫しました。
考え方は単純で、3種の場合はそのうちの2種について、それぞれの数をインデックスとします。2種の数が一致する範囲では、全探索します。

たとえばこんなパターンとします。
 ABB
 AAA
 AAC
3種の数をそれぞれ数えると、Aが6個、Bが2個、Cが1個です。この場合はa=6,b=2をインデックスとします。AとBの数が決まればCの数が決まるので、これで十分です。

これだけですが、かなり時間は短くなりました。
2種4x4の場合3分以上かかっていたのが、30秒ほどになりました。
3種3x3の場合は13秒ほどだったのが1秒ほどです。
しかし3種4x3では、メモリ不足で失敗しました。あらためて、メモリの使用許可サイズを増やしてやってみることにします。
by sokoban | 2007-01-12 01:36 | 同一チェック


<< プログラミング 重複排除までのコスト >>