libcds/tests/static_bitsequence_tester.cpp

   1 /* static_bitsequence_tester.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_bitsequence_tester
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include <iostream>
  23 #include <algorithm>
  24 #include <sstream>
  25 #include <basics.h>
  26 #include <static_bitsequence.h>
  27
  28 using namespace std;
  29
  30 /* Time meassuring */
  31 double ticks= (double)sysconf(_SC_CLK_TCK);
  32 struct tms t1,t2;
  33
  34 void start_clock() {
  35   times (&t1);
  36 }
  37
  38
  39 double stop_clock() {
  40   times (&t2);
  41   return (t2.tms_utime-t1.tms_utime)/ticks;
  42 }
  43 /* end Time meassuring */
  44
  45 uint NQUERIES=10000000;
  46 uint SEED=47;
  47
  48 void load(char *fname, uint ** text, uint * n) {
  49   FILE * fp = fopen(fname,"r");
  50   if(fp==NULL) {
  51     cout << "could not open " << fname << endl;
  52     return;
  53   }
  54   if(fread(n,sizeof(uint),1,fp)!=1) {
  55     cout << "Error reading file " << fname << endl;
  56     return;
  57   }
  58   *text = new uint[uint_len(*n,1)];
  59
  60   if(fread(*text,sizeof(uint),uint_len(*n,1),fp)!=uint_len(*n,1)) {
  61     cout << "Error reading file " << fname << endl;
  62     return;
  63   }
  64 }
  65
  66 void test_bitsequence(uint * bitseq, uint len, static_bitsequence * bs) {
  67   uint ones = 0;
  68         uint last_one = 0;
  69   bool error = false;
  70   for(uint i=0;i<len && !error;i++) {
  71     //cout << "i="<<i<< endl;
  72     if(i>0) {
  73       if(i%max((uint)1,(bs->length()/100))==0) { cout << "."; cout.flush(); }
  74       if(i%max((uint)1,(bs->length()/10))==0) { cout << endl; cout.flush(); }
  75     }
  76     if(bitget(bitseq,i)) {
  77                         for(uint k=last_one; !error && k<i;k++) {
  78                                 if(bs->select_next1(k)!=i) {
  79                                         uint ans= bs->select_next1(k);
  80                                         cout << "Error select_next1" << endl;
  81                                         cout << " got: (k=" << k << ") " << ans << " expected: " << i << endl;
  82                                         cout << " rank(" << k << ")=" << bs->rank1(k) << " access(" << k << ")=" << bs->access(k) << endl;
  83                                         cout << " rank(" << ans << ")=" << bs->rank1(ans) << " access(" << ans << ")=" << bs->access(ans) << endl;
  84                                         error = true;
  85                                 }
  86                         }
  87                         last_one = i;
  88                         ones++;
  89                 }
  90     if(bs->access(i) != (bitget(bitseq,i)!=0)) {
  91       cout << "Access error for position " << i << endl;
  92       cout << " got: " << bs->access(i) << " expected: " << (bitget(bitseq,i)!=0) << endl;
  93       error = true;
  94     }
  95     if(bs->rank1(i) != ones) {
  96       cout << "Rank1 error for position " << i << endl;
  97       cout << " got: " << bs->rank1(i) << " expected: " << ones << endl;
  98       error = true;
  99     }
 100     if(bitget(bitseq,i) && bs->select1(ones) != i) {
 101       cout << "Select1 error for position " << i << " ones:" << ones << endl;
 102       cout << " got: " << bs->select1(ones) << " expected: " << i << endl;
 103       error = true;
 104     }
 105     if(bs->rank0(i) != i+1-ones) {
 106       cout << "Rank0 error for position " << i << endl;
 107       cout << " got: " << bs->rank0(i) << " expected: " << ones << endl;
 108       error = true;
 109     }
 110     if(!bitget(bitseq,i) && bs->select0(i+1-ones) != i) {
 111       cout << "Select0 error for position " << i << endl;
 112       cout << " got: " << bs->select0(i+1-ones) << " expected: " << i << endl;
 113       error = true;
 114     }
 115   }
 116         cout << "." << endl;
 117 }
 118
 119 void speed_access(static_bitsequence * ss, uint * bitseq, uint n) {
 120   uint acc=0;
 121   srand(SEED);
 122
 123   start_clock();
 124   for(uint i=0;i<NQUERIES;i++) {
 125     uint pos = rand()%n;
 126     acc += ss->access(pos);
 127   }
 128   double t = stop_clock();
 129   cout << " * Time for " << NQUERIES << " accesses: " << t << " secs" << endl;
 130   cout << " * Time per access: " << 1000*t/NQUERIES << " msecs" << endl;
 131   cout << " - Check sum: " << acc << endl;
 132 }
 133
 134 void speed_rank0(static_bitsequence * ss, uint * bitseq, uint n) {
 135   uint acc=0;
 136   srand(SEED);
 137
 138   start_clock();
 139   for(uint i=0;i<NQUERIES;i++) {
 140     uint pos = rand()%n;
 141     acc += ss->rank0(pos);
 142   }
 143   double t = stop_clock();
 144   cout << " * Time for " << NQUERIES << " rank0s: " << t << " secs" << endl;
 145   cout << " * Time per rank0: " << 1000*t/NQUERIES << " msecs" << endl;
 146   cout << " - Check sum: " << acc << endl;
 147 }
 148
 149 void speed_rank1(static_bitsequence * ss, uint * bitseq, uint n) {
 150   uint acc=0;
 151   srand(SEED);
 152
 153   start_clock();
 154   for(uint i=0;i<NQUERIES;i++) {
 155     uint pos = rand()%n;
 156     acc += ss->rank1(pos);
 157   }
 158   double t = stop_clock();
 159   cout << " * Time for " << NQUERIES << " rank1s: " << t << " secs" << endl;
 160   cout << " * Time per rank1: " << 1000*t/NQUERIES << " msecs" << endl;
 161   cout << " - Check sum: " << acc << endl;
 162 }
 163
 164 void speed_select0(static_bitsequence * ss, uint * bitseq, uint n) {
 165   uint acc=0;
 166   uint ones=ss->rank0(n-1);
 167   srand(SEED);
 168
 169   start_clock();
 170   for(uint i=0;i<NQUERIES;i++) {
 171     uint pos = rand()%ones+1;
 172     acc += ss->select0(pos);
 173   }
 174   double t = stop_clock();
 175   cout << " * Time for " << NQUERIES << " select0s: " << t << " secs" << endl;
 176   cout << " * Time per select0: " << 1000*t/NQUERIES << " msecs" << endl;
 177   cout << " - Check sum: " << acc << endl;
 178 }
 179
 180 void speed_select1(static_bitsequence * ss, uint * bitseq, uint n) {
 181   uint acc=0;
 182   uint ones=ss->rank1(n-1);
 183   srand(SEED);
 184
 185   start_clock();
 186   for(uint i=0;i<NQUERIES;i++) {
 187     uint pos = rand()%ones+1;
 188     acc += ss->select1(pos);
 189   }
 190   double t = stop_clock();
 191   cout << " * Time for " << NQUERIES << " select1s: " << t << " secs" << endl;
 192   cout << " * Time per select1: " << 1000*t/NQUERIES << " msecs" << endl;
 193   cout << " - Check sum: " << acc << endl;
 194 }
 195
 196 void speed_selectnext1(static_bitsequence * ss, uint * bitseq, uint n) {
 197   uint acc=0;
 198   srand(SEED);
 199
 200   start_clock();
 201   for(uint i=0;i<NQUERIES;i++) {
 202     uint pos = rand()%n;
 203     acc += ss->select_next1(pos);
 204   }
 205   double t = stop_clock();
 206   cout << " * Time for " << NQUERIES << " select_next1s: " << t << " secs" << endl;
 207   cout << " * Time per select_next1: " << 1000*t/NQUERIES << " msecs" << endl;
 208   cout << " - Check sum: " << acc << endl;
 209 }