ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 9. 残りピース管理をリスト化

9. 残りピース管理をリスト化

ピースをボード上にはめ込んでいくとき、残っているピースはどれだか分かるようにしておかないといけない。今までは、この残りピース管理を図9-1のようにピースの数である12個分の配列で行っていた。つまり使ったピース番号の場所に「使用済み」であることのフラグを立てておき、それ以外のピースは未使用であることが分かる。 (図の配列indexは実際には0から始まるが説明の便宜上、1〜12にしてある)

この方法だと、はめ込むピースをどれにするか探すときに最大12回のループを回ることになる(Xピースは最初に配置しているので、正確には11回)。1千万回規模の探索を行う際に、探索1回あたり平均で5,6回のループを回すのは計算の無駄である。

図9-1 残りピースを配列で管理

そこで図9-2のように残りピース管理をポインタで行うことにした。C言語でポインタは難しいと言われているので使いたくなかったが、仕方なく使ってみた。

ピースを使ったときにリンクから外し、使用しなくなったらリンクに戻している。これにより、リストには残りのピースのみをリンクしているので、残りのピースを探す必要はなく、先頭からリンクされるピースを使えばよく、探す時間分が削減される。

図9-2 残りピースをリスト構造で管理

今回の改善も探索の枝刈りではなく、探索時の計算量を削減するものである。よって探索数は減っていないが時間は15%ほど短縮できた。

【↑高速化インデックスへ】