1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include <sdsl/bit_vectors.hpp>
#include <random>
#include <iostream>
#include <chrono>
using namespace sdsl;
using namespace std;
using namespace std::chrono;
using timer = std::chrono::high_resolution_clock;
template<class t_vec>
uint64_t test_inv_random_access(const t_vec& v, const int_vector<64>& rands, uint64_t mask, uint64_t times=100000000)
{
uint64_t cnt=0;
for (uint64_t i=0; i<times; ++i) {
cnt += v(rands[ i&mask ]);
}
return cnt;
}
//int main(int argc, char* argv[]){
int main()
{
auto start = timer::now();
bool default_value = 0; //ID[ID.length()-1]-'0';
bit_vector bv = bit_vector(800000000, default_value);
std::mt19937_64 rng;
std::uniform_int_distribution<uint64_t> distribution(0, bv.size()-1);
auto dice = bind(distribution, rng);
// populate vectors with some other bits
for (uint64_t i=0; i < bv.size()/25; ++i) {
uint64_t x = dice();
bv[x] = !default_value;
}
auto stop = timer::now();
cout << "initialization in (ms): " << duration_cast<milliseconds>(stop-start).count() << endl;
cout << "size in MiB: " << size_in_mega_bytes(bv) << endl;
start = timer::now();
sd_vector<> bv_sd(bv);
stop = timer::now();
cout << "sd_construction in (ms): " << duration_cast<milliseconds>(stop-start).count() << endl;
{
bit_vector().swap(bv);
}
cout << "size in MiB: " << size_in_mega_bytes(bv_sd) << endl;
cout << "wl = " << (size_t) bv_sd.wl << endl;
cout << "n = " << bv_sd.size() << endl;
cout << "2*m = " << bv_sd.high.size()<<endl;
cout <<"n/m=" << (2.0*bv_sd.size())/bv_sd.high.size()<<endl;
auto zeros = sd_vector<>::rank_0_type(&bv_sd)(bv_sd.size());
auto ones = bv_sd.size()-zeros;
cout << "zeros = "<< zeros << endl;
{
uint64_t mask = 0;
auto rands = util::rnd_positions<int_vector<64>>(20, mask, zeros, 17);
for (uint64_t i=0; i<rands.size(); ++i) rands[i] = rands[i]+1;
sd_vector<>::select_0_type select0(&bv_sd);
const uint64_t reps = 10000000;
start = timer::now();
auto check = test_inv_random_access(select0, rands, mask, reps);
stop = timer::now();
cout << "# select0_time = " << duration_cast<nanoseconds>(stop-start).count()/(double)reps << endl;
cout << "# select_check = " << check << endl;
cout << "# size_in_mega_bytes(bv_sd) = " << size_in_mega_bytes(bv_sd) << endl;
cout << "# size_in_mega_bytes(select0) = " << size_in_mega_bytes(select0) << endl;
}
{
uint64_t mask = 0;
auto rands = util::rnd_positions<int_vector<64>>(20, mask, zeros, 17);
for (uint64_t i=0; i<rands.size(); ++i) rands[i] = rands[i]+1;
select_0_support_sd<sd_vector<>> select0(&bv_sd);
const uint64_t reps = 10000000;
start = timer::now();
auto check = test_inv_random_access(select0, rands, mask, reps);
stop = timer::now();
cout << "# select0_time = " << duration_cast<nanoseconds>(stop-start).count()/(double)reps << endl;
cout << "# select_check = " << check << endl;
cout << "# size_in_mega_bytes(bv_sd) = " << size_in_mega_bytes(bv_sd) << endl;
cout << "# size_in_mega_bytes(select0) = " << size_in_mega_bytes(select0) << endl;
}
{
uint64_t mask = 0;
auto rands = util::rnd_positions<int_vector<64>>(20, mask, ones, 17);
for (uint64_t i=0; i<rands.size(); ++i) rands[i] = rands[i]+1;
sd_vector<>::select_1_type select1(&bv_sd);
const uint64_t reps = 10000000;
start = timer::now();
auto check = test_inv_random_access(select1, rands, mask, reps);
stop = timer::now();
cout << "# select1_time = " << duration_cast<nanoseconds>(stop-start).count()/(double)reps << endl;
cout << "# select_check = " << check << endl;
}
{
uint64_t mask = 0;
auto rands = util::rnd_positions<int_vector<64>>(20, mask, bv_sd.size(), 17);
cout<<"done"<<endl;
cout<<(uint64_t)&(bv_sd.high_1_select)<<endl;
cout<<(uint64_t)&(bv_sd.high_0_select)<<endl;
sd_vector<>::rank_1_type rank1(&bv_sd);
cout<<"done"<<endl;
const uint64_t reps = 10000000;
// for(size_t i=0; i<bv_sd.size();++i){
// cout << "i="<<i<<" rank1("<<i<<")="<<rank1(i)<<endl;
// }
start = timer::now();
auto check = test_inv_random_access(rank1, rands, mask, reps);
stop = timer::now();
cout << "# rank1_time = " << duration_cast<nanoseconds>(stop-start).count()/(double)reps << endl;
cout << "# select_check = " << check << endl;
}
}
|
