tests/static_sequence_tester.cpp

   1 /* static_sequence_tester.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * static_sequence_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 "static_sequence_tester.h"
  23
  24 using namespace std;
  25
  26 /* Time meassuring */
  27 double ticks= (double)sysconf(_SC_CLK_TCK);
  28 struct tms t1,t2;
  29
  30 void start_clock() {
  31   times (&t1);
  32 }
  33
  34
  35 double stop_clock() {
  36   times (&t2);
  37   return (t2.tms_utime-t1.tms_utime)/ticks;
  38 }
  39 /* end Time meassuring */
  40
  41 uint NQUERIES=100000;
  42 uint SEED=47;
  43
  44 void test_static_sequence(uint * symbols, uint n, static_sequence * ss) {
  45   cout << "Size: " << ss->size() << endl;
  46   uint max_v=0;
  47   for(uint i=0;i<n;i++)
  48     max_v = max(max_v,symbols[i]);
  49   uint * occ = new uint[max_v+1];
  50   for(uint i=0;i<=max_v;i++)
  51     occ[i] = 0;
  52   bool error = false;
  53   for(uint i=0;i<n && !error;i++) {
  54     if(i!=0 && i%max((uint)1,(n-1)/100)==0) { cout << "."; cout.flush(); }
  55     if(i!=0 && i%max((uint)1,(n-1)/10)==0) cout << endl;
  56     occ[symbols[i]]++;
  57     uint a = /*symbols[i]; /*/ss->access(i);
  58     uint r = /*occ[symbols[i]];/*/ss->rank(symbols[i],i);
  59     uint s = /*i; /*/ss->select(symbols[i],occ[symbols[i]]);
  60     uint rM1 = (i==0)?0:ss->rank(symbols[i],i-1);
  61     if(r!=occ[symbols[i]]) {
  62       cout << "Error in rank for symbol " << symbols[i] << " at position " << i << endl;
  63       cout << "value: " << r << endl;
  64       cout << "Expected: " << occ[symbols[i]] << endl;
  65       error = true;
  66     }
  67     if(s!=i) {
  68       cout << "Error in select for symbol " << symbols[i] << " at position " << occ[symbols[i]] << endl;
  69       cout << "value: " << s << endl;
  70       cout << "Expected: " << i << endl;
  71       error = true;
  72     }
  73     if(a!=symbols[i]) {
  74       cout << "Error in access at position " << i << endl;
  75       cout << "value: " << a << endl;
  76       cout << "Expected: " << symbols[i] << endl;
  77       error = true;
  78     }
  79     if(rM1!=occ[symbols[i]]-1) {
  80       cout << "Error in rankM1 for symbol " << symbols[i] << " at position " << i-1 << endl;
  81       cout << "value: " << rM1 << endl;
  82       cout << "Expected: " << occ[symbols[i]]-1 << endl;
  83       error = true;
  84     }
  85   }
  86   if(!error)
  87     cout << "Test OK! It works :)" << endl;
  88   delete [] occ;
  89 }
  90
  91 void load(char *fname, uint ** text, uint * n) {
  92   struct stat text_info;
  93   if(stat(fname,&text_info)<0) {
  94     cout << "could not stat: " << fname << endl;
  95     return;
  96   }
  97
  98   *n= (uint)text_info.st_size/4;
  99   *text = new uint[*n+1];
 100   FILE * fp = fopen(fname,"r");
 101   if(fp==NULL) {
 102     cout << "could not open " << fname << endl;
 103     return;
 104   }
 105
 106   cout << "File: " << fname << endl;
 107   cout << "Length: " << *n << endl;
 108
 109   uint max_symbol = 0;
 110   for(uint i=0;i<*n;i++) {
 111     uint c;
 112     uint read=fread(&c,sizeof(uint),1,fp);
 113     //assert(read==1);
 114     (*text)[i] = 1+(uint)c;
 115     c += read;
 116     max_symbol = max(max_symbol,(*text)[i]);
 117   }
 118   max_symbol++;
 119   fclose(fp);
 120
 121   /*static_sequence * ss = ssb->build(*text,*n);
 122
 123   char * fname2 = new char[10+string(fname).length()];
 124   sprintf(fname2,"%s.wt",fname);
 125   fp = fopen(fname2,"w");
 126   ss->save(fp);
 127   fclose(fp);
 128   delete ss;
 129   fp = fopen(fname2,"r");
 130   ss = static_sequence::load(fp);
 131   fclose(fp);
 132   delete [] fname2;
 133   return ss;*/
 134 }
 135
 136 static_sequence * savetest(char * bname, static_sequence * ss) {
 137         char * fname = new char[10+string(bname).length()];
 138         sprintf(fname,"%s.ss",bname);
 139         FILE * fp = fopen(fname,"w");
 140         cout << "Saving structure ... "; cout.flush();
 141         ss->save(fp);
 142         cout << "done" << endl; cout.flush();
 143         fclose(fp);
 144         cout << "Deleting structure ... "; cout.flush();
 145         delete ss;
 146         cout << "done" << endl; cout.flush();
 147         fp = fopen(fname,"r");
 148         cout << "Loading structure ... "; cout.flush();
 149         ss = static_sequence::load(fp);
 150         cout << "done" << endl; cout.flush();
 151         fclose(fp);
 152         if(ss==NULL) cout << "Error loading static_sequence" << endl;
 153         //cout << ss << endl;
 154         delete [] fname;
 155         return ss;
 156 }
 157
 158 void speed_rank(static_sequence * ss, uint * text, uint n) {
 159   uint max_symbol = 0;
 160   for(uint i=0;i<n;i++) {
 161     max_symbol = max(max_symbol,text[i]);
 162   }
 163   max_symbol++;
 164   uint *occ = new uint[max_symbol];
 165   for(uint i=0;i<max_symbol;i++)
 166     occ[i] = 0;
 167   for(uint i=0;i<n;i++)
 168     occ[text[i]]++;
 169
 170   uint * valid_symbols = new uint[max_symbol]; uint c=0;
 171   for(uint i=0;i<max_symbol;i++) {
 172     if(occ[i]>0)
 173       valid_symbols[c++]=i;
 174   }
 175
 176   uint acc=0;
 177   srand(SEED);
 178
 179   start_clock();
 180   for(uint i=0;i<NQUERIES;i++) {
 181     uint symb = rand()%c;
 182     uint pos = rand()%n;
 183     acc += ss->rank(valid_symbols[symb],pos);
 184   }
 185   double t = stop_clock();
 186   cout << " * Time for " << NQUERIES << " ranks: " << t << " secs" << endl;
 187   cout << " * Time per rank: " << 1000*t/NQUERIES << " msecs" << endl;
 188   cout << " - Check sum: " << acc << endl;
 189   delete [] valid_symbols;
 190   delete [] occ;
 191 }
 192
 193 void speed_select(static_sequence * ss, uint * text, uint n) {
 194   uint max_symbol = 0;
 195   for(uint i=0;i<n;i++) {
 196     max_symbol = max(max_symbol,text[i]);
 197   }
 198   max_symbol++;
 199   uint *occ = new uint[max_symbol];
 200   for(uint i=0;i<max_symbol;i++)
 201     occ[i] = 0;
 202   for(uint i=0;i<n;i++)
 203     occ[text[i]]++;
 204
 205   uint * valid_symbols = new uint[max_symbol]; uint c=0;
 206   for(uint i=0;i<max_symbol;i++) {
 207     if(occ[i]>0)
 208       valid_symbols[c++]=i;
 209   }
 210
 211   uint acc=0;
 212   srand(SEED);
 213
 214   start_clock();
 215   for(uint i=0;i<NQUERIES;i++) {
 216     uint symb = rand()%c;
 217     uint pos = rand()%occ[valid_symbols[symb]]+1;
 218     acc += ss->select(valid_symbols[symb],pos);
 219   }
 220   double t = stop_clock();
 221   cout << " * Time for " << NQUERIES << " selects: " << t << " secs" << endl;
 222   cout << " * Time per select: " << 1000*t/NQUERIES << " msecs" << endl;
 223   cout << " - Check sum: " << acc << endl;
 224   delete [] valid_symbols;
 225   delete [] occ;
 226 }
 227
 228 void speed_access(static_sequence * ss, uint * text, uint n) {
 229   uint acc=0;
 230   srand(SEED);
 231
 232   start_clock();
 233   for(uint i=0;i<NQUERIES;i++) {
 234     uint pos = rand()%n;
 235     acc += ss->access(pos);
 236   }
 237   double t = stop_clock();
 238   cout << " * Time for " << NQUERIES << " accesses: " << t << " secs" << endl;
 239   cout << " * Time per access: " << 1000*t/NQUERIES << " msecs" << endl;
 240   cout << " - Check sum: " << acc << endl;
 241 }