k-permutations で爆弾の配置を総当たりで生成した後で盤面の判定処理を行うが、この判定処理を行う回数は最も多い。つまり一回分の処理の最適化が数万倍に効果を出すのだ。
n x n マスの毎回ループして判断対象を探すのはとても無駄なので、探索ルートを事前いきめて、そのルートで指定されたマスのみの判断を行うようにする。
探索ルートの決め方には前述の Point of Interest が強く関わってくる。
特定のマス目の Point of Interest の中に爆弾設置可能な空白がある場合はそれが「爆弾設置可能候補」としてマーキングされるのだが、そういった数字マスが探索ルートとなる。
画像をグレースケール化して 9x8 のサイズにリサンプルし、隣合わせのピクセル同士を比較して増減に応じて 0 か 1 の値を設定して画像を 64bit 値にするというものだ。画像の検索には Binary Search Tree (2分探索木) を使って、3 bit 程度の誤差なら許容するような形で検索する。
※ グレースケール化やリサンプルのアルゴリズム、増減に応じて 0/1付与の方式によって dHash値の互換性が無くなるので長期の利用の際には互換性の維持については要注意である。
ただし Binary Search Tree を構築するのには時間と手間がかかるし、頻繁に検索するには Binary Search Tree のデータをメモリ上に長期間保持する必要があるので運用が面倒である。
そこで MySQL で Binary Search Tree を用いずに単純検索をしてみるとした場合、どうなるかを確認してみた。
MySQL には BIT(n) 型というのがあって、最大 64bit までの値を格納できる。今回はSIGNED/UNSIGNED関係にまったく気を配りたくないのでdhash値はBIT型にした。
※尚、UPDATE images SET dhash_bits = UNHEX(dhash); 等で16進文字列からBITへの変換は容易にできる。
SELECT HEX(dhash_bits), BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') AS SCORE
FROM images
WHERE dhash_bits IS NOT NULL
AND BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') <= 3
ORDER BY BIT_COUNT(dhash_bits ^ b'1111000111110000111000100100000001100100010011001101001011111001') ASC
RAIDの場合はデータをストライプすることによってパフォーマンス向上を狙うが、パリティドライブ数+1のHDD欠損で全データをロストする。UNRAIDでは各データドライブは通常のファイルシステムのまま運用されるので、複数のHDDが欠損しても残存HDD上のデータは専用の復旧ソフトの必要もなしに復元できる。必要なのは対象ファイルシステムに対応したLinux の Live Boot メディアだけだ。