整数の力まかせ探索(説明)
整数の力まかせ探索(ソースコード)(mask-src.html)
●目次
●目的(ꃬꄿꀂꌒꇰ)
整数の計算プログラムの開発をするときに、
ある整数を適当な整数(マスク、ビット列)でＡＮＤ、ＯＲ、ＸＯＲすると
上手くいく場合があります。
３２ビットの上手くいくマスクを探索するときに、
0 ～ 0xffffffff を全て調べると
４０億回以上確認する必要があります。
１つのマスクを確認するのに時間がかかる場合、
全てを確認するのは実用的ではありません。
さらに探索するマスクの幅が６４ビットの場合は、
全てを確認するとほぼ無限となり不可能になります。
目的はマスクを様々な条件で制限して数を減らし、
実用的な時間内でマスクを探索できるようにすることです。
●どういうタイプのプログラムを高速化するのか
以下のプログラムは全ての１６ビット整数を列挙し、
その中から 20001 の約数を表示する単純なものです。
目的が約数を求めるのであれば、専用のアルゴリズムの方が優れています。
例題として約数を取り上げたのは、プログラムの感覚をつかむのに適しているからです。
この例では do-while ループで divisor は
0～0xffff までの値を取ります。
繰り返し回数は 65536 回です。
mask.hpp の目的はこのループの繰り返し数を少なくすることです。
●制限のできる７種類の値
ビット列において連続する１のブロックをランと呼びます。
例えば 0110111011101100 ではランの数は４となります。
制限のできる７種類の値は以下です。
(括弧内の数字は 0110111011101100 の場合の例)
MaxWidth ビット幅(１６)
MaxBitCount ビット数の最大値(１０)
MinBitCount ビット数の最小値(１０)
MaxNumOfRun ランの数の最大値(４)
MinNumOfRun ランの数の最小値(４)
MaxLenOfRun ランの長さの最大値(３)
MinLenOfRUn ランの長さの最小値(２)
条件を付ることで列挙するマスク数を減らします。
●byte型(unsigned char)の単純な例と結果
この例のように mc で条件を何も付けずにそのまま使用すると、 byte ならば
２５６種類の全てのマスクが昇順に列挙されます。
● mconf_t について
mconf_t mc; と宣言された mc は条件を加えたり。
実行の結果を得たりするのに使用します。
入力メンバー変数
mconf_t のコンストラクタは入力メンバー変数を全て 0 に設定します。
- long long Limit : NextMask が true を返し続ける最大数。0 の場合 1<<62 に置き換わる。
- int MaxWidth : ビットの幅。0 以下の場合 sizeof(T)*8 が足される。
- int MinBitCount : ビット数の最小値。
- int MaxBitCount : ビット数の最大値。0 以下の場合 MaxWidth が足される。
- int MinLenOfRun : ランの長さの最小値。0 の場合は 1 に置き換わる。
- int MaxLenOfRun : ランの長さの最大値。0 以下の場合 MaxWidth が足される。
- int MinNumOfRun : ランの数の最小値。
- int MaxNumOfRun : ランの数の最大値。0 の場合は (MaxWidth+1)/(MinLenOfRun+1) に置き換わる。
出力メンバー変数
- const char*ErrMsg : 通常は "No Error"。エラーが起こると他のエラーメッセージを指す。
- int ErrCode : 通常は 0。エラーが起こるとエラー番号になる。
- int GenMsec : maskex.hpp をインクルードしたときに GetMasks 関数、GetMasksHeap 関数の実行時間を msec 単位で保持する。
- int ShuffleMsec : maskex.hpp をインクルードしたときに GetMasks 関数、GetMasksHeap 関数内でシャッフルの実行時間を msec 単位で保持する。
● mnext_t と NextMask について
mnext_t<byte>mn(mc); は mn を byte 型で mc を関連付けて、
宣言と初期化を行います。
これにより関数 mn.NextMask(mask) を使用することができます。
NextMask 関数は次のマスクがあれば mask に新しいマスクを代入して true を返します。
次のマスクがなければ NextMask 関数は mask を変更せずに false を返します。
● MaxWidth=5; MaxNumOfRun=1; に制限して情報を表示する例
mc を宣言した後、 mc のメンバー変数を変更して条件を加えてから、
mn を mc で初期化すると、 mask を制限できます。
minfo_t について
struct minfo_t { byte BitCount,NumOfRun; char Bsr,Bsf; };
と宣言された４バイトの構造体です。
Bsr は最も左のビット位置、 Bsf は最も右のビット位置を示します。
例えば 0110111011101100 では Bsr は１４に、 Bsf は２になります。
mask が０のときは Bsr、Bsf は -1 になります。
mtoa について
mtoa は mask.hpp に書かれていています。
mtoa(mask,5) は mask を２進数５桁の数文字列を返します。
●幅を６、そしてランの数を１～４にして繰り返す
このように、一つの Mconf と Nmask を繰り返し使うことがですます。
●20001の約数を列挙する例(チューニングなし)
このように short に mc による制限をかけずに、
約数かどうかの確認をすると、65536 個の値を試します。
●20001の約数を列挙する例(チューニングあり)
mc に生成するマスクに様々な制限を指定することでループの繰り返し数を、
65536 から減らして高速化できます。
この例では 20001 の約数が奇数であることも利用しています。
その結果 1456 まで減りました。
※ここまで mask.hpp のみでできることを示しました。
●20001の約数を配列に列挙する例( maskex.hpp の GenMasks )
exampleF.cpp は exampleD.cpp と同じことを配列を使用して実現します。
exampleF.cpp は mask.hpp, maskex.hpp, shuffle.hpp, mex-main.hpp を必要とします。
●20001の約数を配列に列挙する例(シャッフル)
配列を使用することで、疑似乱数を使用してシャッフルすることが可能になります。
大きな約数を確率的に速く得ることができます。
シャッフルするには GenMasks 関数の引数に０以外の種(Seed)を追加します。
●20001の約数を配列に列挙する例(ヒープを使用する)
GenMasks ではあらかじめ配列の大きさを決めなければなりません。
GenMasksHeap を使えば大きなメモリの限界量与えて、
必要な配列をヒープ上に確保することができます。
以下のようにシャッフルも可能です。
GenMasksHeap ではヒープを指すポインタを使い終わったら
delete[] するのを忘れないでください。
●シャッフルのカスタマイズ
GenMasks, GenMasksHeap で０以外の種を与えたときの
シャッフルの方法をマクロで変更できます。
既定の方法
既定ではブロックサイズが１６のブロックベースドシャッフルを行います。
これは配列を１６個のブロックに分けて最初に局所的にシャッフルを行います。
そして、最後にブロックごとにまとめてシャッフルを行います。
Fisher-Yates shuffle
コンパイラ・オプションに -D"BSIZE=1" または
省略して -DBSIZE を加えると単純な Fisher-Yates shuffle を
行います。
この場合、ほぼ完全にランダムになります。
ただし、大きな配列では極端に遅くなります。
原因は１個要素を交換する毎にＣＰＵのキャッシュミスが発生するからです。
ブロックサイズの選択( BSIZE )
既定のブロックサイズを１６個にした理由を説明します。
１個～１６個ではブロックサイズが大きくなるつれ急激に性能が向上します。
対して、１６個～１０２４個までは緩やかに向上します。
さらに、２０４８個以上にすると１０２４個よりも遅くなります。
シャッフルを行う目的は「確率的に速くマスクを見つける」ことです。
ブロックサイズを大きくし過ぎると目的を達成しにくくなるので、
既定は１６個にしました。
局所的なシャッフルをしない( NO_LOCAL )
コンパイラオプションに -DNO_LOCAL を加えると、
局所的なシャッフルを省略します。
その結果、シャッフル時間が半分前後になります。
ブロックサイズが１６ならば、
「確率的に速くマスクを見つける」という目標にはほとんど影響しないと考え、
この仕様を加えました。