簡潔ビットベクトル性能評価実験のソースコード(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を使っています。詳細は
を参照してください。残るrxの評価用コードも近いうちに公開します。。。