| Diploma Thesis Percolation Simulation C++ Sourcecode Documentation |
00001 // counters.h
00002 // the cluster-counters
00003 //
00004 // (c) 2000 Andreas Krueger
00005 // Version 1.0
00006 // last change: 31.10.2000
00007
00008
00009 // the naive counters time(N) ~ O(N^2)
00010 //
00011
00012 namespace counters {
00013 using analyze::sameresult;
00014 using analyze::spanning_dirs_and_clusters;
00015 using analyze::mean_without_lr_spanningcls;
00016 using results::one_result;
00017
00018
00019 // calls the naive recursion and analyzes the histogram
00020 clock_t naive_count_and_analyze(sphere *spheres,
00021 NUMBER first,
00022 NUMBER last,
00023 NUMBER *histo,
00024 NUMBER &biggestcl,
00025 REAL &averagecl)
00026 {
00027 // returns these results:
00028 // the biggest cluster is of size: << biggestcl
00029 // each sphere is on average part of a cluster of size << averagecl
00030 // the detailed size-distribution is in << histo[...]
00031
00032 clock_t time=clock();
00033 NUMBER *tableofclusters=new NUMBER[(last-first+3)]; // must be one bigger than number of spheres because of ending 0
00034
00035 countclusters_naive(spheres, first, last, tableofclusters); //count clusters, vs.1
00036
00037 averagecl=set_clustersize_to_each_sphere(tableofclusters, spheres, first,last);
00038 erasehisto(histo,first, last);
00039
00040 NUMBER biggestcl_no;
00041 makehistogram(tableofclusters,histo,biggestcl,biggestcl_no);
00042
00043 delete[] tableofclusters;
00044
00045 return (clock()-time);
00046 }
00047
00048
00049 // same as 'naive_count_and_analyze'
00050 // but returns the number of the biggest-cluster
00051 NUMBER naive_arraycount_and_analyze(sphere *spheres,
00052 NUMBER first,
00053 NUMBER last,
00054 NUMBER *histo,
00055 NUMBER &biggestcl,
00056 REAL &averagecl){
00057
00058 NUMBER *tableofclusters=new NUMBER[(last-first+3)]; // must be one bigger than number of spheres because of ending 0
00059
00060 countclusters_naive(spheres, first, last, tableofclusters); //count clusters, vs.1
00061
00062 averagecl=set_clustersize_to_each_sphere(tableofclusters, spheres, first,last);
00063 erasehisto(histo,first, last);
00064 NUMBER biggestcl_no;
00065 makehistogram(tableofclusters,histo,biggestcl,biggestcl_no);
00066
00067 delete[] tableofclusters;
00068
00069 return (biggestcl_no);
00070 }
00071
00072
00073 // this sorts the spheres first, then does the naive clustercount
00074 clock_t sort_naivecount_and_analyze(sphere *spheres,
00075 sphere *copy ,
00076 NUMBER first,
00077 NUMBER last,
00078 NUMBER *histo,
00079 NUMBER &biggestcl,
00080 REAL &averagecl)
00081 {
00082
00083 // returns these results:
00084 // the biggest cluster is of size: << biggestcl
00085 // each sphere is on average part of a cluster of size << averagecl
00086 // the most frequent cluster is of size: << mostfreqcl
00087 // the detailed size-distribution is in << histo[...]
00088
00089 clock_t time=clock();
00090
00091 copy_array(spheres,copy,1,last); // store it before sorting
00092 quicksort1 (spheres,1,last); // sort by length
00093 naive_count_and_analyze(spheres, first, last, histo, biggestcl, averagecl);
00094 copy_array(copy,spheres,1,last); // copy it back
00095
00096 return (clock()-time);
00097 }
00098
00099
00100 // the listcounters
00101 // same as naivecounters, but takes in lists of spheres instead of arrays
00102 // (slower)
00103
00104 clock_t naive_listcount_and_analyze(sphere *spheres,
00105 NUMLIST &sphlist,
00106 NUMBER N,
00107 NUMBER *histo,
00108 NUMBER &biggestcl,
00109 REAL &averagecl
00110 ){
00111 // returns these results:
00112 // the biggest cluster is of size: << biggestcl
00113 // each sphere is on average part of a cluster of size << averagecl
00114 // the detailed size-distribution is in << histo[...]
00115
00116 clock_t time=clock();
00117 NUMBER *tableofclusters=new NUMBER[(sphlist.size()+2)]; // must be one bigger than number of spheres because of ending 0
00118 NUMBER clusternumber=1; // first cluster is "1"
00119
00120 countclusters_l(spheres,sphlist, tableofclusters, clusternumber);
00121
00122 averagecl=set_clustersize_to_each_sphere_l(tableofclusters, spheres, sphlist);
00123 erasehisto(histo,1, N);
00124 NUMBER biggestcl_no;
00125 makehistogram(tableofclusters,histo,biggestcl, biggestcl_no);
00126
00127 delete[] tableofclusters;
00128
00129 return (clock()-time);
00130 }
00131
00132 // this copies the list to a given array and starts the naive recursive count
00133 clock_t copy_l_count_and_analyze(sphere *spheres,
00134 sphere *copy,
00135 NUMLIST &sphlist,
00136 NUMBER *histo,
00137 NUMBER &biggestcl,
00138 REAL &averagecl){
00139
00140 clock_t time=clock();
00141
00142 NUMLIST::iterator iter;
00143 NUMBER index=0;
00144 for (iter = sphlist.begin(); iter != sphlist.end(); iter++){
00145 index++;
00146 copy[index]=spheres[*iter];
00147 }
00148
00149 naive_count_and_analyze(copy,1,index,histo,biggestcl,averagecl);
00150
00151 index=0;
00152 for (iter = sphlist.begin(); iter != sphlist.end(); iter++){
00153 index++;
00154 spheres[*iter]=copy[index];
00155 }
00156
00157 return (clock()-time);
00158 }
00159
00160
00161
00162
00163 // the reference test, if the new counter works
00164 bool reference_test(NUMBER N, int dim, COUNTER cuts ){ // test if new and old algo's results are the SAME!
00165
00166 sphere *scatter = new sphere[N+1];
00167 set_dim(scatter,0,N,dim);
00168 throw_spheres(scatter, 1, N); // randomly throw spheres from 1 to N in array scatter
00169 REAL r=R_critical(N,GRIDSIZE,dim);
00170 if (r==-1) r=R_critical_guessed(N,GRIDSIZE,dim); // with _critical_ sphere radius, if known, otherwise r=guess
00171 set_radius(scatter, 1,N,r);
00172
00173 // new algo
00174 NUMBER *histogram=new NUMBER[(N+1)];
00175 NUMBER biggestcl;
00176 REAL averagecl;
00177 NUMLIST all;
00178 increasing_integers (all, N); // fill the list "all" with the numbers of all spheres
00179
00180 clock_t speed=clock();
00181 cout <<"\ndivide_by_c_cuts count (new algo):.."<<flush;
00182 set_clusternumber(scatter,1,N,0); // no sphere is found yet
00183 divide_by_c_cuts_count_and_analyze(scatter, all, cuts,histogram, biggestcl, averagecl);
00184 cout <<" speed: "<<ms(clock()-speed)<<" ms"<<endl;
00185 cout <<" (biggestcluster: "<<biggestcl<<"\taverage cluster: "<<averagecl<<" )"<<endl;
00186
00187 // old algo
00188 sphere *copy = new sphere[N+1];
00189 set_dim(copy,0,N,dim);
00190 NUMBER *histogramcontrol=new NUMBER[(N+1)];
00191
00192 speed=clock();
00193 cout <<"\nsorted-array-count (old, naive algo):.. "<<flush;
00194 set_clusternumber(scatter,1,N,0); // no sphere is found yet
00195 sort_naivecount_and_analyze(scatter, copy, 1, N, histogramcontrol, biggestcl, averagecl);
00196 cout <<" speed: "<<ms(clock()-speed)<<" ms"<<endl;
00197 cout <<" (biggestcluster: "<<biggestcl<<"\taverage cluster: "<<averagecl<<" )"<<endl;
00198
00199 if (sameresult(histogram,histogramcontrol,1,biggestcl)) {
00200 cout <<"\nThe new algorithm was tested. Results are perfect. Let us begin.\n\n"<<endl;
00201 delete [] scatter, copy, histogram, histogramcontrol;
00202 all.clear();
00203 return true;
00204 }
00205
00206 else {
00207 cout <<".\nTERRIBLE !\n";
00208 errorout("The new algorithm has different results. \nPlease write to cpp__at__AndreasKrueger__dot__de\n");
00209 cout<<"cuts="<<cuts<<endl;
00210
00211 delete [] scatter, copy, histogram, histogramcontrol;
00212 all.clear();
00213 return false;
00214 }
00215 }
00216
00217
00218 // This divid-and-conquer counter and analyzer is used NOW
00219 // e.g. in find_ffc
00220 one_result setR_count_analyze_step(NUMBER N, int dim, sphere* spheres, NUMLIST& L_sph_numbers, REAL radius,
00221 string& throwtime, clock_t &clcount_time, clock_t &spclsearch_time)
00222 {
00223 COUNTER cuts=choose_optimal_cuts(dim,N, radius);
00224
00225 cluson *clusters=new cluson[N+1];
00226 if (clusters==NULL) exit_out_of_memory("radiusstep(...): cluson *clusters");
00227
00228 NUMBER numberof_cl; NUMBER biggestcl; REAL mean_clsz; REAL mean_clsz_without_spcls;
00229 LONGBITS spcl_dirs; NUMLIST L_spanningclusters; L_spanningclusters.clear();
00230
00231 clock_t time_start=clock();
00232 set_radius(spheres, 1,N,radius);
00233 set_clusternumber(spheres,1,N,0);
00234 numberof_cl=divide_count_and_analyze(spheres, L_sph_numbers, cuts, clusters, biggestcl, mean_clsz);
00235 clcount_time=(clock()-time_start);
00236
00237 clock_t time_spsearch_start=clock();
00238 spcl_dirs=spanning_dirs_and_clusters(spheres, L_sph_numbers, 0, GRIDSIZE, radius, dim,
00239 clusters, L_spanningclusters);
00240 mean_clsz_without_spcls= mean_without_lr_spanningcls(mean_clsz, N, clusters,
00241 L_spanningclusters, spcl_dirs);
00242
00243 spclsearch_time=(clock()-time_spsearch_start);
00244 string counttime=give_short_timestamp();
00245
00246 delete[] clusters;
00247 return one_result(spcl_dirs, numberof_cl, biggestcl, mean_clsz, mean_clsz_without_spcls,
00248 clcount_time + spclsearch_time, throwtime, counttime);
00249 }
00250
00251 // This is used NOW in into_file8
00252 // same as 'setR_count_analyze_step' but throws new coordinates before counting
00253 one_result throw_dnc_count_analyze_step(sphere* spheres, NUMLIST& L_sph_numbers, REAL radius,
00254 clock_t &clcount_time, clock_t &spclsearch_time)
00255 {
00256 NUMBER N=L_sph_numbers.size();
00257 int dim=getdim(spheres[L_sph_numbers.front()]);
00258
00259 throw_spheres(spheres, 1, N);
00260 string throwtime=give_short_timestamp();
00261
00262 return setR_count_analyze_step(N,dim, spheres, L_sph_numbers, radius,
00263 throwtime, clcount_time, spclsearch_time);
00264 }
00265
00266
00267
00268 } // end of namespace counters
| Diploma Thesis Sourcecode
Documentation check out the text and the executable binaries |