競技プログラミング向けの完備辞書の実装 - arosh/arosh.github.com GitHub Wiki

FID(Fully Indexable Dictionary, 完備辞書)とかSucBV(Succinct Bit Vector, 簡潔ビットベクトル)と呼ばれているデータ構造の競技プログラミング向けの実装です。

(↑の2つの呼び方が全く同じものを指しているのかどうかよく分からないので誰か教えて)

性能についての記述はMacbook Air(13-inch, Mid 2011)で測定したものです。

  • uint64_tよりもuint32_tを使ったほうがほんの少し(5%程度)高速でした. 当然ながらuint64_tのほうが高速な環境もあると思いますが, 1ULLとか__builtin_popcountllとか書くのが嫌なので32bitで行きましょう.
  • 部分和辞書において平方分割などのテクを使うと使用メモリを減らすことができ, CPUのキャッシュに乗ることを期待できますが, 以下の実装でも240kBほどしか使用しないようだったので, 簡単に実装できることを優先しました.
  • %32 を &31 で代用すると2〜3%程度高速になります.
  • selectの実装は無難にO(log n)です 参考
  • 以下の実装では部分和辞書で二分探索してからrank(k)で二分探索することで高速化を目論んでいます. rank(k)だけで二分探索すると1.5〜2倍遅くなります.
  • 500kbit/1000kbitがTrueの密ビット列において、clangで-O2を付けてselectを10^7回実行すると以下の実装では1.59secかかりました。↑のようにrankだけで二分探索すると2.71secかかりました。
struct sbv {
  int size;
  int blocks;
  vector<unsigned> b;
  vector<int> s;
  sbv(int size_) {
    size = size_;
    blocks = (size + 32 - 1) / 32;
    b.assign(blocks, 0U);
    s.assign(blocks, 0U);
  }

  void set(int p) {
    b[p / 32] |= (1U << (p % 32));
  }
  void build() {
    s[0] = 0;
    for(int i = 1; i < blocks; i++) {
      s[i] = s[i - 1] + __builtin_popcount(b[i - 1]);
    }
  }
  bool access(int p) {
    return (b[p / 32] >> (p % 32)) & 1U;
  }
  int rank(int p) {
    unsigned mask = (1U << (p % 32)) - 1;
    return s[p / 32] + __builtin_popcount(b[p / 32] & mask);
  }
  int select(int x) {
    // max(k; v[k] <= x)
    // [lb, ub)
    int lb = 0, ub = blocks;
    while(ub - lb > 1) {
      int mid = (lb + ub) / 2;
      if(s[mid] <= x) {
        lb = mid;
      }
      else {
        ub = mid;
      }
    }
    int block_id = lb;
    // max(k; rank(k) <= x)
    // [lb, ub)
    lb = block_id * 32, ub = (block_id + 1) * 32;
    while(ub - lb > 1) {
      int mid = (lb + ub) / 2;
      if(rank(mid) <= x) {
        lb = mid;
      }
      else {
        ub = mid;
      }
    }
    return lb;
  }
};
⚠️ **GitHub.com Fallback** ⚠️