簡潔ビットベクトル性能評価実験のソースコード(marisa-trie編)

評価実験に用いたソースコードをおいておきます。これを用意するときに気づいたのですが、rank/select呼ぶ度に標準出力に書き出してるせいでめちゃくちゃ遅くなってたっぽい。適当な実験で迷惑かけてすみませんでした。。。
というわけでまずはmarisa-trie用のコードを。長くなるのでライブラリ毎にエントリを分けます。

簡潔ビットベクトル構築用コード(marisa_make.cc)

#include "vector.h"
#include <iostream>

using namespace std;
using namespace marisa::grimore;
using namespace marisa::grimore::io;

int main(int argc, char **argv) {
  try {
    BitVector bv;
    if (argc < 2) { cerr << "USAGE: marisa_make bvfile < infile" << endl; }
    Writer w;
    w.open(argv[1]);

    uint64_t n = 0;
    uint64_t pos = 0;
    while (cin >> n) {
      while (pos < n) { pos++; bv.push_back(0); }
      pos++;
      bv.push_back(1);
    }
    bv.build(true, true);
    bv.write(w);
  } catch (const char *err) {
    cerr << err << endl;
    return 1;
  }
  return 0;
}

簡潔ビットベクトル評価用コード(marisa_test.cc)

#include "vector.h"
#include <iostream>
#include <ctime>

using namespace std;
using namespace marisa::grimore;
using namespace marisa::grimore::io;

int main(int argc, char **argv) {
  try {
    srand((unsigned)time(NULL));
    int mode = 0; // 1:rank, 2:select
    if (argc < 3) { cerr << "USAGE: marisa_test bvfile mode" << endl; }
    mode = atoi(argv[2]);
    uint64_t t = 10000000;
    uint64_t n = 100000000;
    uint64_t m = 50000000;

    BitVector bv;
    Reader r;
    r.open(argv[1]);
    bv.read(r);

    // rank test
    if (mode == 1) {
      cout << "**** rank test ****" << endl;
      clock_t tmp = clock();
      for (uint64_t i = 0; i < t; i++) {
        uint64_t x = rand() % n;
        cout << "rank(" << x << ") = " << bv.rank1(x) << endl;
      }
      double sec = double(clock() - tmp) / CLOCK_PER_SEC;
      cout << "********************************" << endl;
      cout << sec << "s" << endl;
    }

    // select test
    if (mode == 2) {
      cout << "**** select test ****" << endl;
      clock_t tmp = clock();
      for (uint64_t i = 0; i < t; i++) {
        uint64_t x = rand() % m;
        cout << "select(" << x << ") = " << bv.select1(x) << endl;
      }
      double sec = double(clock() - tmp) / CLOCK_PER_SEC;
      cout << "********************************" << endl;
      cout << sec << "s" << endl;
    }
  } catch (const char *err) {
    cerr << err << endl;
    return 1;
  }
  return 0;
}

以上のコードをmarisa-trie/直下に置いて、

$$ cd marisa-trie/
$$ g++ -O2 marisa_make.cc lib/marisa/grimore/io/*
     lib/marisa/grimore/vector/* -Ilib/marisa/grimore/ -o marisa_make
$$ g++ -O2 marisa_test.cc lib/marisa/grimore/io/*
     lib/marisa/grimore/vector/* -Ilib/marisa/grimore/ -o marisa_test

としたら以下のようにして評価します。

$$ perl -e 'while($n < 100000000) { $n++; print "$n\n"; }' | shuf | head -50000000
     | sort -n | ./marisa_make bvfile
$$ ./marisa_test bvfile 1 | tail -1  # rankの時間測定
$$ ./marisa_test bvfile 2 | tail -1  # selectの時間測定

なおデータのシャッフルにはCoreutilsのshufを使っています。詳細は

Coreutilsのshufを使ってみた - EchizenBlog-Zwei

を参照してください。ux,rxの評価用コードは近いうちに公開します。。。