ナンプレの正規化 ステップ・バイ・ステップ その５

はじめに

Step4では、一番上にくる行のヒント配置による枝刈りでちょっとだけ早くした。まだ刈れそうな枝はあるが、とりあえず高速化の定番、ビット演算を試そう。早くなるかどうかなど問題ではない。とりあえずプログラマはビット演算をするものなのだ。

ソースはこちら。
https://github.com/kaityo256/minlex/tree/master/step5

ビット表現

ナンプレをビット表現するにあたり、それぞれの数字がどのマスにあるかを81bitの整数9個で表現することにしよう。

たとえば以下の問題は次のような9個の81ビット整数として表現する。

# 元データ
207005000000340000150000009005000001040000320000016500000002084700000010010580000
# そのビット表現
000000000000000000100000000000000001000000000000010000000000000000000010010000000
100000000000000000000000000000000000000000010000000000000001000000000000000000000
000000000000100000000000000000000000000000100000000000000000000000000000000000000
000000000000010000000000000000000000010000000000000000000000001000000000000000000
000001000000000000010000000001000000000000000000000100000000000000000000000100000
000000000000000000000000000000000000000000000000001000000000000000000000000000000
001000000000000000000000000000000000000000000000000000000000000100000000000000000
000000000000000000000000000000000000000000000000000000000000010000000000000010000
000000000000000000000000001000000000000000000000000000000000000000000000000000000

上から順番に「1がある場所のビットが立っている整数」「2がある場所が立っている整数」・・・となっている。81ビットなので、unsigned __int128で表現する。typedefしておこう。

typedef unsigned __int128 mbit;

行の入れ替えなどは全部ビット演算でやる。以下、ビット演算化のキーポイントだけ書く。

数字の振り直し

ビットのエンディアンだが、一番左(Left Most Bit)がMSBとする。もっというと、MSBをナンプレの一番左の数字に対応させる。こうすると、計算時間のかなりの部分を占めていた「数字の振り直し」がソート一発でできるようになる。ビットデータをmbit bdata[9]というメンバとすると、数字の振り直し、つまり「ナンプレの左上から見て、数字を出現順に1から振り直す」手続きは

  Sudoku renumbering(void) {
    mbit bdata2[9];
    for (int i = 0; i < 9; i++) {
      bdata2[i] = bdata[i];
    }
    std::sort(&bdata2[0], &bdata2[9], std::greater<mbit>());
    return Sudoku(bdata2);
  }

と書けてしまう。これはそこそこ早くなってくれるんじゃなかろうかという期待がある。

比較

枝刈りのためには、ナンプレ同士の比較関数を書かないといけない。配列版はこう書いていた。

  bool operator<(const Sudoku &rhs) const {
    for (int i = 0; i < 81; i++) {
      if (rhs.data[i] != this->data[i]) {
        return (this->data[i] < rhs.data[i]);
      }
    }
    return false;
  }

これをビット演算でやるのはちょっと頭をつかう。方針としては

1. 数字を1から順番に見ていく
2. 両者で違っていたら、Left Most Bit (LMB)を見て、それがこれまでのLMBと等しいか大きければ不等号の判定を更新する

みたいなことをする。LMBを見るのは、ナンプレを81桁の整数だと思った時に一番左側の違いを見るため。もし同じ場所で異なっていたら、数字が大きい方の判定を優先する。

以上を実装するとこんな感じになるだろう。

  bool operator<(const Sudoku &rhs) const {
    mbit vmax = 0;
    bool less = false;
    for (int i = 0; i < 9; i++) {
      mbit v = bdata[i] ^ rhs.bdata[i];
      v = left_most_bit(v);
      if (v >= vmax) {
        vmax = v;
        less = (bdata[i] < rhs.bdata[i]);
      }
    }
    return less;
  }

ここで、128ビット整数のLMBを得る関数left_most_bitが必要になる。ちょっと考えたけど賢い実装が思いつかなかったので、Right Most Bitを削っていく実装にしてみた。

mbit left_most_bit(mbit v) {
  mbit vt = 0;
  while (v) {
    vt = v;
    v ^= v & (-v);
  }
  return vt;
}

残りの行や列の入れ替えだの、最上位行のインデックス作成だのはそのままなので説明は不要であろう。

結果

以上の実装をした結果、どのくらい早くなったかを調べる。

配列版。

$ time ./b.out sample.txt > test.txt 
./b.out sample.txt > test.txt  3.27s user 0.01s system 99% cpu 3.295 total

ビット演算版

$ time ./a.out sample.txt > test.txt 
./a.out sample.txt > test.txt  2.57s user 0.01s system 99% cpu 2.593 total

うーん、二倍いかなかった○|￣|＿

もうちょっと高速化

perf見てみたら、なんかstd::__unguarded_linear_insertみたいなのが12%とか占めていたので、自分で書いてみる。9個のデータなら挿入ソートでいいかな。

void
mysort(mbit v[9]){
  int j;
  for(int i=1;i<9;i++){
    mbit tmp = v[i];
    if(v[i-1] < tmp) {
      j = i;
      do {
       v[j] = v[j-1];
       j--;
      }while (j>0 && v[j-1] < tmp);
      v[j] = tmp;
    }
  }
}

$ time ./a.out sample.txt > test.txt
./a.out sample.txt > test.txt 2.48s user 0.01s system 99% cpu 2.496 total

んー、誤差の範囲かなぁ。HaswellなLinuxマシン + GCC 5.1.0だと、この修正で5.162[s]→3.666[s]とそこそこの効果があったんだけど、手元のSkylakeなMac + GCC7.2.0だとほとんど早くならない。

# 最後の行の入れ替え

一番上のボックス行が確定した後、残りの中段、下段の行の入れ替えをするんだけど、この時6*6パターン全部作ってしまっている。

```cpp
  void perm_restrbox(Sudoku &g) {
    for (auto ai : perm3) {
      for (auto aj : perm3) {
        Sudoku g2 = g.perm_restrbox(ai,aj).renumbering();
        if (g2 < min) {
          min = g2;
        }
      }
    }
  }

これは無駄なので、一度中段を入れ替えたテンポラリなナンプレを作って、それを受け取って下段を入れ替えるように修正しよう。

  void perm_restrbox(Sudoku &g) {
    for (auto ai : perm3) {
      Sudoku g1 = g.perm_restrbox2(ai,0);
      for (auto aj : perm3) {
        Sudoku g2 = g1.perm_restrbox2(aj,1).renumbering();
        //Sudoku g2 = g.perm_restrbox(ai,aj).renumbering();
        if (g2 < min) {
          min = g2;
        }
      }
    }
  }

perm_restrbox2とか、いよいよソースが汚くなってきたが気にしてはいけない。

$ time ./a.out sample.txt > test.txt
./a.out sample.txt > test.txt  2.29s user 0.01s system 99% cpu 2.308 total

これはまぁまぁ(といってもちょっとだけど)効果があった。Haswellでも3.777 [s]→ 3.693 [s]とちょっとだけ早くなったけど、これはもう誤差かなぁ。

もうちょっとだけ頑張る

perfを見る限り、遅いのはSudoku::perm_columnsである。見てみる。

  Sudoku perm_columns(int ai[3], int aj[3], int ak[3]) {
    mbit bdata2[9] = {};
    mbit v[9];
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        v[j] = (bdata[i] & column_bits[j]) >> (8 - j);
      }
      bdata2[i] |= v[ai[0]] << 8;
      bdata2[i] |= v[ai[1]] << 7;
      bdata2[i] |= v[ai[2]] << 6;
      bdata2[i] |= v[aj[0] + 3] << 5;
      bdata2[i] |= v[aj[1] + 3] << 4;
      bdata2[i] |= v[aj[2] + 3] << 3;
      bdata2[i] |= v[ak[0] + 6] << 2;
      bdata2[i] |= v[ak[1] + 6] << 1;
      bdata2[i] |= v[ak[2] + 6] << 0;
    }
    return Sudoku(bdata2);
  }

ここで、最初にmbit bdata2[9] = {};と初期化しているのが気になる。これをこうしてみる。

  Sudoku perm_columns(int ai[3], int aj[3], int ak[3]) {
    mbit bdata2[9];
    mbit v[9];
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        v[j] = (bdata[i] & column_bits[j]) >> (8 - j);
      }
      bdata2[i] = v[ai[0]] << 8;
      bdata2[i] |= v[ai[1]] << 7;
      bdata2[i] |= v[ai[2]] << 6;
      bdata2[i] |= v[aj[0] + 3] << 5;
      bdata2[i] |= v[aj[1] + 3] << 4;
      bdata2[i] |= v[aj[2] + 3] << 3;
      bdata2[i] |= v[ak[0] + 6] << 2;
      bdata2[i] |= v[ak[1] + 6] << 1;
      bdata2[i] |= v[ak[2] + 6] << 0;
    }
    return Sudoku(bdata2);
  }

$ time ./a.out sample.txt > test.txt
./a.out sample.txt > test.txt  2.18s user 0.01s system 99% cpu 2.198 total

ちびっとだけ早くなった。

まとめ

ビット演算とちまちまとした最適化で、Step 4の3.3秒から、2.18秒くらいになった。手間の割には倍いかなかったのが残念。

追記(10/6)

herumiさんより、128bitのLeft Most Bitを探すところを高速化する方法を教えていただいた。こんな感じ。

mbit left_most_bit(mbit v) {
  union ai {
    uint64_t a[2];
    mbit i;
  } ai;
  ai.i = v;
  if (ai.a[1]) {
    ai.a[0] = 0;
    ai.a[1] = 1ull << (63 - __builtin_clzl(ai.a[1]));
    return ai.i;
  }
  if (ai.a[0] == 0) return 0;
  return 1ull << (63 - __builtin_clzl(ai.a[0]));
}

128bitの処理をするために上位64ビットと下位64bitを別処理しているけれど、ロジックとしては

• Bit Scan Reverseで最上位ビットの位置(Left Most Bitの左側にあるゼロの数)を取得
• (127 - ゼロの数)だけ1を左にビットシフトしたものがLeft Most Bit

というもの。BSRは知識としては知っていたんだけれど、一度ビット位置を取得してからビットシフトで元に戻す、という発想には至らなかった。

これでさらに一割くらい早くなる。

./before.out sample.txt > orig.txt  2.17s user 0.01s system 99% cpu 2.183 total
./after.out sample.txt  > test.txt  1.95s user 0.01s system 96% cpu 2.030 total

もっとがんばるといろいろ速くなりそう・・・