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

ux-trieで使われている簡潔ビットベクトルの評価実験に用いたソースコードをおいておきます。


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

#include "rsDic.hpp"
#include <iostream>

using namespace std;
using namespace ux;

int main(int argc, char **argv) {
  try {
    BitVec bv;
    if (argc < 1) { cerr << "USAGE: ux_make < infile > bvfile" << endl; }

    uint64_t n = 0;
    uint64_t pos = 0;
    while (cin >> n) {
      while (pos < n) { pos++; bv.push_back(0); }
      pos++;
      bv.push_back(1);
    }
    RSDic d;
    d.build(bv);
    d.save(cout);
  } catch (const char *err) {
    cerr << err << endl;
    return 1;
  }
  return 0;
}


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

#include "rsDic.hpp"
#include <iostream>
#include <ctime>

using namespace std;
using namespace ux;

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

    RSDic d;
    d.load(cin);

    // 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 << ") = " << d.rank(x, true) << 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 << ") = " << d.select(x, true) << 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;
}

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

$$ cd ux-trie/
$$ g++ -O2 ux_make.cc src/*.cpp -Isrc/ -o ux_make
$$ g++ -O2 ux_test.cc src/*.cpp -Isrc/ -o ux_test

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

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

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

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

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