00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #include <iostream>
00036 #include <stdlib.h>
00037 #include <stdio.h>
00038 #include <time.h>
00039
00040
00041
00042
00043
00044
00045
00046 #define BM_DISBALE_BIT_IN_PTR
00047 #include "bm.h"
00048
00049 using namespace std;
00050
00051
00052
00053
00054 typedef bm::bvector<bm::standard_allocator,
00055 bm::miniset<bm::block_allocator, bm::set_total_blocks> > bvect;
00056
00057
00058 const unsigned setscount = 10000;
00059 const unsigned randombits = 150;
00060 const unsigned maxbit = 100000000;
00061
00062 bvect* bitsets[setscount];
00063
00064
00065
00066 void CreateSets()
00067 {
00068 unsigned mu = 0;
00069 for (unsigned i = 0; i < setscount; ++i)
00070 {
00071 if ((i % 100) == 0) { cout << "."; cout.flush(); }
00072
00073
00074 bitsets[i] =
00075 new bvect(bm::BM_GAP, bm::gap_len_table_min<true>::_len, maxbit);
00076 bvect& bv = *bitsets[i];
00077 bvect::statistics st;
00078 bv.calc_stat(&st);
00079 mu += st.memory_used;
00080 }
00081 cout << endl << "Created " << setscount << " sets." << endl;
00082 cout << "Used " << mu / (1024*1024)<< " MB." << endl;
00083 }
00084
00085
00086
00087 void FillSets()
00088 {
00089 unsigned mu, bit_blocks, gap_blocks;
00090 cout << "Filling sets...";
00091 mu = bit_blocks = gap_blocks = 0;
00092 for (unsigned i = 0; i < setscount; ++i)
00093 {
00094 if ((i % 100) == 0) { cout << "."; cout.flush(); }
00095 if ((i % 3) == 0) continue;
00096 bvect& bv = *bitsets[i];
00097 unsigned bn = 0;
00098 for (unsigned j = 0; j < randombits; j+=3)
00099 {
00100 bn += (maxbit / randombits) + rand() % 10;
00101 if (bn > maxbit) bn = rand() % maxbit;
00102
00103 bv[bn] = true;
00104 bv[bn+1] = true;
00105 bv[bn+2] = true;
00106 }
00107 bvect::statistics st;
00108 bv.calc_stat(&st);
00109 mu += st.memory_used;
00110 bit_blocks += st.bit_blocks;
00111 gap_blocks += st.gap_blocks;
00112 }
00113 cout << endl << "Used " << mu / (1024*1024)<< " MB." << endl;
00114
00115 cout << "BIT Blocks=" << bit_blocks << endl;
00116 cout << "GAP Blocks=" << gap_blocks << endl;
00117 }
00118
00119
00120
00121 void EnumerateSets()
00122 {
00123 cout << "Enumerating sets...";
00124 unsigned bitcnt = 0;
00125 for (unsigned i = 0; i < setscount; ++i)
00126 {
00127 if ((i % 100) == 0) { cout << "."; cout.flush(); }
00128 bvect& bv = *bitsets[i];
00129
00130 bvect::enumerator en = bv.first();
00131 bvect::enumerator en_end = bv.end();
00132
00133 for (;en < en_end; ++en)
00134 {
00135 ++bitcnt;
00136 }
00137 }
00138 cout << endl << bitcnt << endl;
00139 }
00140
00141
00142
00143 void DestroySets()
00144 {
00145 for (unsigned i = 0; i < setscount; ++i)
00146 {
00147 delete bitsets[i];
00148 }
00149 }
00150
00151
00152
00153 void OrSets()
00154 {
00155 bvect res;
00156 cout << "Calculating Or...";
00157 for (unsigned i = 0; i < setscount; ++i)
00158 {
00159 if ((i % 100) == 0) { cout << "."; cout.flush(); }
00160 const bvect& bv = *bitsets[i];
00161
00162 res |= bv;
00163 }
00164 cout << endl << res.count() << endl;
00165 }
00166
00167
00168
00169
00170
00171 int main(void)
00172 {
00173 time_t start_time = time(0);
00174
00175 CreateSets();
00176 FillSets();
00177 EnumerateSets();
00178 OrSets();
00179
00180 time_t end_time = time(0);
00181 unsigned elapsed = unsigned(end_time - start_time);
00182 cout << "elapsed=" << elapsed << endl;
00183 unsigned ops;
00184 if (elapsed)
00185 ops = setscount / elapsed;
00186 else
00187 ops = setscount;
00188
00189 cout << "Time = " << (end_time - start_time) << endl;
00190 cout << "Operations per second:" << ops << endl;
00191
00192 DestroySets();
00193
00194 return 0;
00195 }
00196
00197