ビットが立つ位置の列挙アルゴリズム

投稿者: | 2017-03-11

前の記事ではBitboardでのパターン検索方法を紹介しました。検索結果はビット列になるため具体的な盤面位置を求めるにはビット列中のビットが立つ位置を列挙する必要があります。

例えば
0000 0100 0010 0011
というビット列では右端のビット位置を0としてビットが立つ位置は
0, 1, 5, 10
になり、このビット位置を列挙することを考えます。

REAL Coreでの実装に先立ち以下の3つのアルゴリズムの性能評価を行いました。

  • ビット列走査(ScanBitSequence)
  • 8bit表引き(TableLookup)
  • 最右ビット列挙(EnumerateRightmostBit)

プログラムおよび結果はGitHub上に置いています。

列挙アルゴリズムの概要

ビット列走査(ScanBitSequence)

ぱっと誰でも思いつくのは1bitずつbitが立っているかチェックするアルゴリズムです。コードでは

  size_t index = 0;
  constexpr uint64_t lowest_bit_mask = 1ULL;
  
  while(bit_sequence != 0){
    if( (bit_sequence & lowest_bit_mask) != 0){
      index_list->push_back(index);
    }

    index++;
    bit_sequence >>= 1;
  }

になります。シンプルな反面、左端のbitが離れているとループ回数&if文の判定回数が多くなり速度的には改善の余地があるアルゴリズムです。

8bit表引き(TableLookup)

次に思いつきそうなのが1bitずつチェックするのではなくある程度まとめて処理をすることで高速化することです。ここでは、8bit(0~255)の値に対する結果を前もって計算しておき、8bitずつ処理します。

  constexpr std::uint64_t eight_bit_mask = 0b11111111;
  size_t shift_num = 0;

  while(bit_sequence != 0){
    const std::uint64_t value = bit_sequence & eight_bit_mask;

    for(auto index : value_index_table[value]){
      index_list->push_back(index + shift_num);
    }

    bit_sequence >>= 8;
    shift_num += 8;
  }

コード中のvalue_index_tableがvalue(0~255)に対するbitが立つ位置のリストを保持したテーブルでbit_sequenceを8bitずつ切り出してbitの立つ位置を求めています。

最右ビット列挙(EnumerateRightmostBit)

ネットで最右ビットの位置を高速に求める手法が紹介されており、それを使い

  • 最右ビット位置を求める
  • 最右ビットをオフ

を繰り返すことでビットが立つ位置を列挙するアルゴリズムが最右ビット列挙(EnumerateRightmostBit)です。コードは

  while(bit_sequence != 0){
    const std::uint64_t rightmost_bit = realcore::GetRightmostBit(bit_sequence);
    const size_t rightmost_bit_index = realcore::GetNumberOfTrailingZeros(bit_sequence, rightmost_bit);
    index_list->push_back(rightmost_bit_index);

    bit_sequence ^= rightmost_bit;
  }

とシンプルですが、最右ビットの算出(GetRightmostBit)、最右ビット位置の算出(GetNumberOfTrailingZeros)のアルゴリズムがすごくて

inline uint64_t GetRightmostBit(const BitBoard bit_board)
{
  const int64_t signed_bit = static_cast<int64_t>(bit_board);
  const uint64_t rightmost_bit = static_cast<uint64_t>(signed_bit & (-signed_bit));

  return rightmost_bit;
}

inline size_t GetNumberOfTrailingZeros(const BitBoard bit_board, const uint64_t rightmost_bit)
{
  assert(bit_board != 0);

  constexpr uint64_t kDeBruijnSequence = 0x03F566ED27179461ULL;
  const uint64_t shifted_DeBruijn = kDeBruijnSequence * rightmost_bit;
  const size_t truncated_DeBruijn = shifted_DeBruijn >> 58;

  static const std::array<size_t, 64> kDeBruijnMapping{{
    #include "def/DeBruijnMapping.h"
  }};

  return kDeBruijnMapping[truncated_DeBruijn];
}

と初見では理解不能なコードです。GetNumberOfTrailingZeros関数で現れるマジックナンバー(0x03F566ED27179461ULL)はDe Bruijn Sequenceと呼ばれる特殊な数列でこの数列をうまく使うことでコンパクトな表引きでビット位置を求めることができます。詳細は分かりやすい解説が

にあるので興味のある方はご覧ください。

性能評価

ビットが立つ数(PopCountと言います)に依存して性能が変わることが想定されるのでPopCount別に性能を測定します。具体的にはPopCountが0~64になる乱数をそれぞれ100万個生成してビットが立っている位置を列挙するのにかかった時間を計測しました。

  • CPU: Core i5-2500K
  • OS: Ubuntu 16.04 on Windows with VMWare Player
  • Mem: 4GB
  • Compiler: g++ 5.4.0
  • Compile Option: -O3 -DNDEBUG

評価結果

予想通りPopCountのほとんど(55以下)ではEnumerateRightmostBitが最も高速になりました。少し面白いのはScanBitSequenceで分岐予測の正否がパフォーマンスに影響を与えているのかPopCountが32付近で最も処理時間がかかりPopCountが多い/少ない領域では速くなる(と言っても他のアルゴリズムよりは遅いですが)結果になりました。

REAL Coreでは1地点を2bitで表現しており検索結果のbit列は最大でも32個しかbitが立たないのでBit位置の列挙アルゴリズムとしてはEnumerateRightmostBitを実装しています。

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください