究極の最高速、ペントミノ全解数、出力プログラムとベンチマーク考                

　本当は、もったいぶって実行ファイルのみ公開したい所なのだけれど、、、、まあ、ソースを見てください。計算プログラムではなく、出力プログラムというのがミソです。これの応用で、全解のパターン表示等、それらしいプログラムに拡張していかにも計算しているように見せかけることは簡単にできます。このネタは、昔々8bitの時代に「最速、円周率出力プログラム」として見た記憶があります。

　手法自体は、インチキでもなんでもなく、頻度が高く、負荷のかかる計算の代わりにLookupテーブルを用いるのは、当たり前に使われているものです。

　この対極にあるのは、人工知能プログラムに、ペントミノの概念のみを入力して、解法からプログラムにやらせることでしょうか？

　なんでこんな話をするかというと、高速化をやっていくと、どこかでこの問題に行き着き、自分なりの目的を明確にし、それに合わせた判断基準がないと、なにを目的にやっているか訳がわからなくなってしまうということを、自戒を込めて書いています。

　たとえば、以前私がやった bin09.c において、各ピースを回転した場合の情報は、事前に計算してデータとして書き込んでしまっていますが、片や中村さんの　pen2002jun20.c (2002.6月版) においては、実行時に計算し、その時間も処理時間に含めています。（その上で早い！！）

　同様に、X型ピースの特異性や探索領域の深度の決定などをソースに落とし込んでしまうか、実行時に探索させるかで、処理時間に大きく影響を与えます。

　今、なんとか　pen2002jun20.c より早いものを作って見ようと考えているわけですが、条件設定をクリアにしておかないと、上記究極のプログラムに行き着いてしまいそうだと、思い至ったわけです。

　と、つらつら書いてきましたが、もう一度整理すると、

　１．私の目的は、ヘキソミノの全解であり、ペントミノの高速化はその手段である。
　２．ペントミノとヘキソミノの最大の違いは、全解がわかっているか、いないかであり、当然ヘキソミノには、上記究極技は使えない。
　３．ペントミノは全解がたかだか、数千通りであり、事前計算（＆解析）の投資効果を十分チューニングしないと、逆にトータルの処理時間は遅くなってしまう。
　４．しかしながら、ヘキソミノの場合は、かりに事前計算に１年分の実CPU時間をかけたとしても十分ペイするはずであり、逆にIndexの高速化、Lookupテーブルの使用、アセンブラレベルのチューニング等思いつくものすべてを入れても、現状では現実的な時間では求まらなさそう。

　ということで、表面的なペントミノの速度比較だけでなく（それはそれでチャレンジしたいが）、その中で使われる高速化手法についてヘキソミノでの有効性を見ていこうと思います。

　現在、興味があるのは、

　１．ポインタによるIndexの高速化。
　２．変数の持ち方（？）。　＜−３２Bitマシンにおいて、不用意なビット演算や1バイトcharの整数としての使用は逆効果になる為、各部それぞれの処理に対しての比較ベンチマークかアセンブラレベルでの検討（？）。ペンティアムのパイプライン等の話は手がでないなぁ。。。
　３．最後が、ヘキソミノでやりかけて進んでいない、複数ピースの集合を事前計算し、それらの組み合わせで求める方法のペントミノへの適用。（今、これをやり始めていて、最左一列を埋める組み合わせは、0.01秒で901通りと求まっており、この結果を最右一列に左右（＆上下）反転して組み合わせ、残りを通常通り埋めていく部分を作っています。）

　P.S. 速度比較に関して、どなたか比較用ガイドライン、条件設定を作りませんか？場合によっては、いくつかのカテゴリ分けなども必要ではないかと考えています。