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

rx-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。rx-trieのbv構造体にはファイル読み書きの関数が無かったので構築と評価を同時にやってしまっています。

簡潔ビットベクトル構築&評価用コード(rx_test.cc)

#include <iostream>
#include <ctime>

using namespace std;

struct bv {
  const unsigned char *v;
  int nr_bytes;
  int *index;
  int index_len;
};
struct bv *bv_alloc(const unsigned char *v, int nr_bytes);
void bv_free(struct bv *b);
int bv_rank(struct bv *b, int n, int z);
int bv_select(const struct bv *b, int n, int z);


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

    int size = (n + 7) / 8;
    unsigned char *v = (unsigned char *)malloc(size);
    for (int i = 0; i < size; i++) { v[i] = 0; }
    int nn;
    while (cin >> nn) { setbit(v, nn); }
    struct bv *b = bv_alloc(v, size);

    // 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_rank(b, x, 1) << 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_select(b, x, 1) << endl;
      }
      double sec = double(clock() - tmp) / CLOCK_PER_SEC;
      cout << "********************************" << endl;
      cout << sec << "s" << endl;
    }
    bv_free(b);
    free(v);
  } catch (const char *err) {
    cerr << err << endl;
    return 1;
  }
  return 0;
}

以上のコードをmozc/src/third_party/rx/v1_0rc2/直下に置いたら、rx.cのstruct bv{...};をコメントアウトしてから

$$ cd mozc/src/third_party/rx/v1_0rc2/
$$ g++ -O2 rx_test.cc rx.c -o rx_test

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

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

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

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

を参照してください。