| Diploma Thesis Percolation Simulation C++ Sourcecode Documentation |
00001 // speedtest.h 00002 // subroutines to test the algorithm 00003 // eg find the "optimal cuts" for each N 00004 // 00005 // (c) 2000 Andreas Krueger 00006 // Version 1.0 00007 // last change: 31.10.2000 00008 00009 namespace optimize{ 00010 using namespace statistics; 00011 00012 using counters::naive_arraycount_and_analyze; 00013 using counters::list_to_given_array_and_find_cluster; 00014 using counters::list_to_temp_array_and_find_cluster; 00015 using counters::count_clusters_iteratively; 00016 using counters::count_clusters_iteratively_only_selected_spherenumbers; 00017 using counters::divide_all_spheres; 00018 using counters::divide_once_count_and_analyze; 00019 using counters::divide_two_times_count_and_analyze; 00020 using counters::maximal_dividings_in_one_coordinate; 00021 using counters::divide_d_times_count_and_analyze; 00022 using counters::combine; 00023 using counters::dividecount; 00024 using counters::count_clusters_iteratively; 00025 using counters::divide_by_c_cuts_count_and_analyze; 00026 using grid::maximal_slots_that_can_be_numbered; 00027 using grid::boxcount_and_analyze; 00028 using analyze::erasehisto; 00029 using analyze::makehistogram; 00030 using analyze::show_sevenhisto; 00031 using analyze::show_threehisto; 00032 using analyze::intersection_of_sortedlists; 00033 using analyze::intersection_of_unsortedlists; 00034 00035 void new_vs_old_algo(int dimension) { 00036 NUMBER N; 00037 cout <<"Please type in NUMBER of spheres: "; 00038 cin >> N; 00039 00040 sphere *spheres = new sphere[N+1]; sphere *temp = new sphere[N+1]; sphere *backup = new sphere[N+1]; 00041 set_dim(spheres,0,N,dimension); set_dim(temp,0,N,dimension); set_dim(backup,0,N,dimension); 00042 00043 cout <<"Please give a random seed: "; 00044 int randseed; cin >>randseed; 00045 srand(randseed); 00046 throw_spheres(spheres, 1, N); // randomly throw spheres from 1 to N in array scatter 00047 00048 double rr=R_critical(N,GRIDSIZE, dimension); 00049 if (rr!=-1) { 00050 cout << "The theoretically critical radius in "; 00051 cout <<dimension<<"dim is "<<rr; 00052 } 00053 else { 00054 rr=R_critical_guessed(N,GRIDSIZE,dimension); 00055 cout << "The critical radius in "; 00056 cout <<dimension<<"dim is approximately "<<rr; 00057 } 00058 cout <<"\nPlease type in the radius of one sphere: "; 00059 REAL R; cin >> R; 00060 cout <<"**************************************************"<<endl; 00061 00062 set_radius(spheres,1,N,R); 00063 00064 // naive recursion 00065 NUMBER *histo1=new NUMBER[(N+1)]; 00066 NUMBER biggestcl1; REAL averagecl1; 00067 cout<<"\nnaive recursion..."<<endl; 00068 set_clusternumber(spheres,1,N,0); 00069 clock_t time1=clock(); 00070 NUMBER bigclno1=naive_arraycount_and_analyze(spheres, 1, N, histo1, biggestcl1,averagecl1); 00071 time1 = clock()-time1; 00072 00073 // a list of all sphere-numbers (used for the divide-algorithms) 00074 NUMLIST all; 00075 increasing_integers (all, N); // fill the list "all" with the numbers 1->N of all spheres 00076 00077 // divide once, then naive recursion 00078 NUMBER *histo2=new NUMBER[(N+1)]; 00079 NUMBER biggestcl2; 00080 REAL averagecl2; 00081 cout <<"\ndivide_once count..."<<endl; 00082 set_clusternumber(spheres,1,N,0); 00083 clock_t time2=clock(); 00084 NUMBER bigclno2=divide_once_count_and_analyze(spheres, temp, all, N,histo2, biggestcl2, averagecl2); 00085 time2=clock()-time2; 00086 00087 // divide twice 00088 NUMBER *histo3=new NUMBER[(N+1)]; 00089 NUMBER biggestcl3; 00090 REAL averagecl3; 00091 cout <<"\ndivide_2times count..."<<endl; 00092 set_clusternumber(spheres,1,N,0); 00093 clock_t time3=clock(); 00094 NUMBER bigclno3=divide_two_times_count_and_analyze(spheres, temp, all, N,histo3, biggestcl3, averagecl3); 00095 time3=clock()-time3; 00096 00097 // use a table of clusterlists (used for the histogram, partly for the algos) 00098 cluson *clusters=new cluson[all.size()+1]; 00099 00100 // divide by c cuts, then naive recursion 00101 NUMBER *histo4=new NUMBER[all.size()+1]; 00102 erasehisto(histo4,1,all.size()); 00103 NUMBER biggestcl4, bigclno4; REAL averagecl4; 00104 cout <<"\n3_cut_stages - count..."<<endl; 00105 set_clusternumber(spheres,1,N,0); 00106 COUNTER cuts=3; 00107 clock_t time4=clock(); 00108 NUMBER numberof_cl=dividecount(spheres, all, 00109 0,GRIDSIZE,(COORDFLOAT)0,GRIDSIZE, 00110 0, cuts, 00111 dimension,dimension, 00112 clusters, 1); 00113 // only for testing: 00114 set_clustersizes(spheres, all, clusters); 00115 copy_array(spheres, backup, 1, N); 00116 // only for testing (END) 00117 00118 NUMBER totalnumber= makehistogram ( clusters, 00119 1,numberof_cl-1, 00120 histo4, 00121 bigclno4, 00122 biggestcl4, 00123 averagecl4); 00124 time4=clock()-time4; 00125 00126 00127 // naive iteration (Stoddard) 00128 NUMBER *histo5=new NUMBER[all.size()+1]; 00129 erasehisto(histo5,1,all.size()); 00130 NUMBER biggestcl5, bigclno5; REAL averagecl5; 00131 cout <<"\nnaive iteration (Stoddard)..."<<endl; 00132 reset_clusters(clusters,N); 00133 set_clusternumber(spheres,1,N,0); 00134 clock_t time5=clock(); 00135 numberof_cl=count_clusters_iteratively(spheres, 1, N, 1); 00136 make_clusterlist_array (spheres, all, clusters); 00137 totalnumber= makehistogram ( clusters, 00138 1,numberof_cl-1, 00139 histo5, 00140 bigclno5, 00141 biggestcl5, 00142 averagecl5); 00143 00144 time5=clock()-time5; 00145 00146 // naive iteration (Stoddard) - but only selected spherenumbers through vector<NUMBER> sphnumber 00147 NUMBER *histo6=new NUMBER[all.size()+1]; 00148 erasehisto(histo6,1,all.size()); 00149 NUMBER biggestcl6, bigclno6; REAL averagecl6; 00150 cout <<"\nnaive iteration (Stoddard), but selected spherenumbers..."<<endl; 00151 reset_clusters(clusters,N); 00152 set_clusternumber(spheres,1,N,0); 00153 std::vector<NUMBER> sphnumbers; sphnumbers.resize(N+1); 00154 increasing_integers(sphnumbers, N); 00155 clock_t time6=clock(); 00156 numberof_cl=count_clusters_iteratively_only_selected_spherenumbers(spheres, sphnumbers, N, 1); 00157 make_clusterlist_array (spheres, all, clusters); 00158 totalnumber= makehistogram ( clusters, 00159 1,numberof_cl-1, 00160 histo6, 00161 bigclno6, 00162 biggestcl6, 00163 averagecl6); 00164 00165 time6=clock()-time6; 00166 00167 00168 // boxcount 00169 00170 NUMBER *histo7=new NUMBER[all.size()+1]; 00171 NUMBER biggestcl7=0, bigclno7=0; REAL averagecl7=0; 00172 NUMBER n=(NUMBER)(GRIDSIZE/(2*R) /2);// heuristic: number of slots in one direction 00173 NUMBER maxn=(NUMBER)maximal_slots_that_can_be_numbered(dimension); 00174 clock_t time7=0; 00175 00176 /* 00177 erasehisto(histo7,1,all.size()); 00178 cout <<"\nboxcount recursion..."<<endl; 00179 reset_clusters(clusters,N); 00180 set_clusternumber(spheres,1,N,0); 00181 cout <<" |n="<<n<<" maxn="<<maxn<<"| "; 00182 n=maxn<n?n=maxn:n; 00183 time7=clock(); 00184 numberof_cl=boxcount_and_analyze(spheres, all, 2 , 2*R, histo7, biggestcl7, averagecl7, bigclno7); 00185 time7=clock()-time7; 00186 */ 00187 00188 delete[] clusters; 00189 00190 00191 if (sameresult(histo1,histo2, 1, biggestcl1)) cout <<"\n! YEAH - I've got a new algorithm - the results for divide_once are the same!"; 00192 else cout <<"\nLOOSER - the new algorithm for divide_once gives differing results !!!"; 00193 00194 if (sameresult(histo1,histo3, 1, biggestcl1)) cout <<"\n! YEAH2 - even the new one, that divides two times is correct!"; 00195 else cout <<"\nLOOSER - the two-times-dividing gives differing results !!!"; 00196 00197 if (sameresult(histo1,histo4, 1, biggestcl1)) cout <<"\n! YEAH4 - even the new one, that cuts on three levels is correct!"; 00198 else cout <<"\nLOOSER - the 3-level-cutting gives differing results !!!"; 00199 00200 if (sameresult(histo1,histo5, 1, biggestcl1)) cout <<"\n! YEAH5 - even the new one, that counts iteratively is correct!"; 00201 else cout <<"\nLOOSER - the iterative counting gives differing results !!!"; 00202 00203 if (sameresult(histo1,histo6, 1, biggestcl1)) cout <<"\n! YEAH6 - even the new one, that counts iteratively with selected sph# is correct!"; 00204 else cout <<"\nLOOSER - the selected sph# iterative counting gives differing results !!!"; 00205 00206 if (sameresult(histo1,histo7, 1, biggestcl1)) cout <<"\n! YEAH7 - even the new one, the boxcount is correct!"; 00207 else { 00208 cout <<"\nLOOSER - the boxcount gives differing results !!!"; 00209 // compare_clustersizes(backup, spheres, 1, N); 00210 } 00211 00212 00213 cout <<"\n\n biggestcluster: \t"<<biggestcl1<<"\t"<<biggestcl2<<"\t"<<biggestcl3<<"\t"<<biggestcl4<<"\t"<<biggestcl5<<"\t"<<biggestcl6<<"\t"<<biggestcl7; 00214 cout <<"\n averagecluster: \t"<<averagecl1<<"\t"<<averagecl2<<"\t"<<averagecl3<<"\t"<<averagecl4<<"\t"<<averagecl5<<"\t"<<averagecl6<<"\t"<<averagecl7; 00215 cout <<"\nname of biggest cluster:\t"<<bigclno1<<"\t"<<bigclno2<<"\t"<<bigclno3<<"\t"<<bigclno4<<"\t"<<bigclno5<<"\t"<<bigclno6<<"\t"<<bigclno7; 00216 00217 cout <<"\n\nnaive recursion: \t"<<ms(time1)<<"ms"; 00218 cout <<"\ndivide_once count: \t"<<ms(time2)<<"ms"; 00219 cout <<"\ndivide2times count: \t"<<ms(time3)<<"ms"; 00220 cout <<"\ncut-on-3-levels count: \t"<<ms(time4)<<"ms"; 00221 cout <<"\nStoddard iteration: \t"<<ms(time5)<<"ms"; 00222 cout <<"\nwith selected sph#: \t"<<ms(time6)<<"ms"; 00223 cout <<"\nboxcount: \t"<<ms(time7)<<"ms"<<endl; 00224 00225 cout <<"if you want to see the histograms, "; 00226 waitanykey(); 00227 show_sevenhisto(histo1, histo2, histo3, histo4, histo5, histo6, histo7, N); 00228 00229 delete[] spheres, temp, histo1, histo2, histo3, histo4, histo5, histo6, histo7; 00230 00231 } 00232 00233 00234 void compare_recursion_and_Stoddard_iteration(int dimension){ 00235 NUMBER N; 00236 cout <<"Please type in NUMBER of spheres: "; 00237 cin >> N; 00238 00239 sphere *spheres = new sphere[N+1]; sphere *temp = new sphere[N+1]; 00240 set_dim(spheres,0,N,dimension); set_dim(temp,0,N,dimension); 00241 NUMBER *histo1=new NUMBER[N+1]; NUMBER *histo5=new NUMBER[N+1]; NUMBER *histo6=new NUMBER[N+1]; 00242 NUMBER biggestcl1, bigclno1; REAL averagecl1; 00243 NUMBER biggestcl5, bigclno5; REAL averagecl5; 00244 NUMBER biggestcl6, bigclno6; REAL averagecl6; 00245 NUMBER totalnumber; NUMBER numberof_cl; 00246 NUMLIST all; 00247 increasing_integers (all, N); 00248 std::vector<NUMBER> sphnumbers; sphnumbers.reserve(N+1); 00249 increasing_integers (sphnumbers, N); 00250 cluson *clusters=new cluson[all.size()+1]; 00251 double rr=R_critical_guessed(N,GRIDSIZE,dimension); 00252 REAL dummy=1.0; // for calculate_moments result type 00253 const COUNTER steps=10; 00254 REAL rep=5; // repetitions for each radius 00255 std::list<clock_t> recursion, iteration, iteration2; 00256 REAL time_recursion[steps+1], time_iteration[steps+1], time_iteration2[steps+1]; 00257 00258 COUNTER index; REAL R; COUNTER i; 00259 00260 cout<<"OK. We now compare at different densities\nthe recursion (r), \nthe iteration (i), \nand the iteration with given spherenumbers (s) \n"; 00261 for (index=0;index<=steps;index++){ 00262 R=2*(REAL)index/steps; 00263 cout <<"\ncritical: "<<R<<" "; 00264 R=R*rr; 00265 set_radius(spheres,1,N,R); 00266 recursion.clear(); iteration.clear(); iteration2.clear(); 00267 for (i=0;i<rep;i++){ 00268 throw_spheres(spheres, 1, N); 00269 00270 // naive recursion 00271 erasehisto(histo1,1,all.size()); 00272 set_clusternumber(spheres,1,N,0); 00273 cout <<"r"<<flush; 00274 clock_t time1=clock(); 00275 bigclno1=naive_arraycount_and_analyze(spheres, 1, N, histo1, biggestcl1,averagecl1); 00276 time1 = clock()-time1; 00277 00278 // naive iteration (Stoddard) 00279 erasehisto(histo5,1,all.size()); 00280 set_clusternumber(spheres,1,N,0); 00281 cout <<"i"<<flush; 00282 clock_t time5=clock(); 00283 numberof_cl=count_clusters_iteratively(spheres, 1, N, 1); 00284 reset_clusters(clusters,N); 00285 make_clusterlist_array (spheres, all, clusters); 00286 totalnumber=makehistogram ( clusters, 1,numberof_cl-1, histo5, bigclno5, biggestcl5, averagecl5); 00287 time5=clock()-time5; 00288 00289 // naive iteration (Stoddard) with selected spherenumbers 00290 erasehisto(histo6,1,all.size()); 00291 set_clusternumber(spheres,1,N,0); 00292 cout <<"s"<<flush; 00293 clock_t time6=clock(); 00294 numberof_cl=count_clusters_iteratively_only_selected_spherenumbers(spheres, sphnumbers, N, 1); 00295 reset_clusters(clusters,N); 00296 make_clusterlist_array (spheres, all, clusters); 00297 totalnumber=makehistogram ( clusters, 1,numberof_cl-1, histo6, bigclno6, biggestcl6, averagecl6); 00298 time6=clock()-time6; 00299 00300 00301 if (!sameresult(histo1,histo5, 1, biggestcl1)) cout <<"\nLOOSER - 2 algorithm -> differing results !!!"; 00302 if (!sameresult(histo1,histo6, 1, biggestcl1)) cout <<"\nLOOSER - 2 algorithm -> differing results (sph#) !!!"; 00303 recursion.push_back(time1); 00304 iteration.push_back(time5); 00305 iteration2.push_back(time6); 00306 } 00307 time_recursion[index]=calculate_moments<REAL,clock_t>(&manipdata<clock_t>::linear, 00308 42, recursion, dummy).mu.av(); 00309 time_iteration[index]=calculate_moments<REAL,clock_t>(&manipdata<clock_t>::linear, 00310 42, iteration, dummy).mu.av(); 00311 time_iteration2[index]=calculate_moments<REAL,clock_t>(&manipdata<clock_t>::linear, 00312 42, iteration2, dummy).mu.av(); 00313 00314 } 00315 00316 cout <<"\nresults of time complexity measurement (in milliseconds):\ncritical\trecursion\titeration\titeration-only-sph#"<<endl; 00317 for (index=0;index<=steps;index++){ 00318 R=2*(REAL)index/steps; 00319 cout <<R<<"\t\t"<<1/rep * ms(time_recursion[index])<<"\t\t"<<1/rep * ms(time_iteration[index]); 00320 cout <<"\t\t"<<1/rep * ms(time_iteration2[index])<<"\n"; 00321 } 00322 00323 delete[] clusters; 00324 } 00325 00326 00327 void choose_dividings(int dimension) { 00328 00329 00330 NUMBER N; 00331 cout <<"Please type in NUMBER of spheres: "; 00332 cin >> N; 00333 00334 sphere *spheres = new sphere[N+1]; sphere *temp = new sphere[N+1]; 00335 set_dim(spheres,0,N,dimension); set_dim(temp,0,N,dimension); 00336 00337 throw_spheres(spheres, 1, N); // randomly throw spheres from 1 to N in array scatter 00338 00339 double rr=R_critical(N,GRIDSIZE, dimension); 00340 if (rr!=-1) { 00341 cout << "The theoretically critical radius in "; 00342 cout <<dimension<<"dim is "<<rr; 00343 } 00344 else { 00345 rr=R_critical_guessed(N,GRIDSIZE,dimension); 00346 cout << "The critical radius in "; 00347 cout <<dimension<<"dim is approximately "<<rr; 00348 } 00349 cout <<"\nPlease type in the radius of one sphere: "; 00350 REAL R; cin >> R; 00351 cout <<"**************************************************"<<endl; 00352 00353 set_radius(spheres,1,N,R); 00354 00355 COUNTER nd_max=maximal_dividings_in_one_coordinate(GRIDSIZE,R); 00356 00357 cout <<"\nPlease type in how often [1..."<<nd_max<<"] "; 00358 cout <<"you want the space \nto be cut in halves (in one direction): "; 00359 COUNTER nd; cin >> nd; 00360 cout <<"OK - in "<<dimension<<" dimensions, these are "<<dimension*nd<<" cuts,"<<endl; 00361 cout <<"so the spheres are divided into "<<pow(2,nd*dimension)<<" little boxes, "<<endl; 00362 cout <<"then the clusters are counted and pairwise combined."<<endl; 00363 00364 NUMBER *histo1=new NUMBER[(N+1)]; 00365 NUMBER biggestcl1; REAL averagecl1; 00366 cout<<"\narraycount..."<<endl; 00367 clock_t time1=clock(); 00368 set_clusternumber(spheres,1,N,0); 00369 NUMBER bigclno1=naive_arraycount_and_analyze(spheres, 1, N, histo1, biggestcl1,averagecl1); 00370 time1 = clock()-time1; 00371 00372 NUMLIST all; 00373 increasing_integers (all, N); // fill the list "all" with the numbers of all spheres 00374 00375 NUMBER *histo3=new NUMBER[(N+1)]; 00376 NUMBER biggestcl3; 00377 REAL averagecl3; 00378 clock_t time3=clock(); 00379 cout <<"\ndivide_2times count..."<<endl; 00380 set_clusternumber(spheres,1,N,0); 00381 NUMBER bigclno3=divide_two_times_count_and_analyze(spheres, temp, all, N,histo3, biggestcl3, averagecl3); 00382 time3=clock()-time3; 00383 00384 NUMBER *histo4=new NUMBER[(N+1)]; 00385 NUMBER biggestcl4; 00386 REAL averagecl4; 00387 clock_t time4=clock(); 00388 cout <<"\ndivide_"<<nd*dimension<<"times count..."<<endl; 00389 set_clusternumber(spheres,1,N,0); 00390 NUMBER bigclno4=divide_d_times_count_and_analyze(spheres, 00391 all, N,nd,histo4, 00392 biggestcl4, averagecl4); 00393 00394 time4=clock()-time4; 00395 00396 if (sameresult(histo1,histo3, 1, biggestcl1)) cout <<"\n! YEAH2 - the new algo, that divides two times is correct!"; 00397 else cout <<"\nLOOSER - the two-times-dividing gives differing results !!!"; 00398 00399 if (sameresult(histo1,histo4, 1, biggestcl1)) cout <<"\n! YEAH3 - even the new one, that divides d times is correct!"; 00400 else cout <<"\nLOOSER - the "<<nd*dimension<<"-times-dividing gives differing results !!!"; 00401 00402 delete[] spheres, temp, histo1, histo3, histo4; 00403 cout <<"\n\n biggestcluster: \t"<<biggestcl1<<"\t"<<biggestcl3<<"\t"<<biggestcl4; 00404 cout <<"\n averagecluster: \t"<<averagecl1<<"\t"<<averagecl3<<"\t"<<averagecl4; 00405 cout <<"\nname of biggest cluster:\t"<<bigclno1<<"\t"<<bigclno3<<"\t"<<bigclno4; 00406 00407 cout <<"\n\nnormalcount: \t"<<ms(time1)<<"ms"; 00408 cout <<"\ndivide2times count: \t"<<ms(time3)<<"ms"; 00409 cout <<"\ndivide"<<nd*dimension<<"times count: \t"<<ms(time4)<<"ms"<<endl; 00410 00411 cout <<"if you want to see the histograms, "; 00412 waitanykey(); 00413 show_threehisto(histo1, histo3, histo4, biggestcl1); 00414 00415 } 00416 00417 00418 00419 00420 void choose_cuts_with_reference_algo(int dimension) { 00421 00422 NUMBER N; 00423 cout <<"Please type in NUMBER of spheres: "; 00424 cin >> N; 00425 00426 sphere *spheres = new sphere[N+1]; 00427 set_dim(spheres,0,N,dimension); 00428 00429 throw_spheres(spheres, 1, N); // randomly throw spheres from 1 to N in array scatter 00430 00431 double rr=R_critical(N,GRIDSIZE, dimension); 00432 if (rr!=-1) { 00433 cout << "The theoretically critical radius in "; 00434 cout <<dimension<<"dim is "<<rr; 00435 } 00436 else { 00437 rr=R_critical_guessed(N,GRIDSIZE,dimension); 00438 cout << "The critical radius in "; 00439 cout <<dimension<<"dim is approximately "<<rr; 00440 } 00441 cout <<"\nPlease type in the radius of one sphere: "; 00442 REAL R; cin >> R; 00443 cout <<"**************************************************"<<endl; 00444 00445 set_radius(spheres,1,N,R); 00446 00447 COUNTER cut_max=dimension*maximal_dividings_in_one_coordinate(GRIDSIZE,R); 00448 00449 cout <<"\nPlease type in how often [1..."<<cut_max<<"] "; 00450 cout <<"you want the space \nto be cut in halves: "; 00451 COUNTER cuts; cin >> cuts; 00452 cout <<"OK - these "<<cuts<<" cuts are distributed among "<<dimension<<" dimensions,"<<endl; 00453 cout <<"so by average "<<(cuts/(REAL)dimension)<<" cuts per dimensional coordinate"<<endl; 00454 cout <<"The spheres will be divided into "<<pow(2,cuts)<<" little boxes, "<<endl; 00455 cout <<"then the clusters will be counted and the boxes will be pairwise combined."<<endl; 00456 00457 NUMBER *histo1=new NUMBER[(N+1)]; 00458 NUMBER biggestcl1; REAL averagecl1; 00459 cout<<"\narraycount (old algo for reference)..."<<endl; 00460 clock_t time1=clock(); 00461 set_clusternumber(spheres,1,N,0); 00462 naive_arraycount_and_analyze(spheres, 1, N, histo1, biggestcl1,averagecl1); 00463 time1 = clock()-time1; 00464 00465 NUMLIST all; 00466 increasing_integers (all, N); // fill the list "all" with the numbers of all spheres 00467 NUMBER *histo2=new NUMBER[(N+1)]; 00468 NUMBER biggestcl2; 00469 REAL averagecl2; 00470 clock_t time2=clock(); 00471 cout <<"\ndivide_"<<cuts<<"times count..."<<endl; 00472 set_clusternumber(spheres,1,N,0); 00473 divide_by_c_cuts_count_and_analyze(spheres, all, cuts,histo2, biggestcl2, averagecl2); 00474 time2=clock()-time2; 00475 00476 if (sameresult(histo1,histo2, 1, biggestcl1)) 00477 cout <<"\n! YEAH - the new algo, that divides by "<<cuts<<" cuts is correct!"; 00478 else 00479 cout <<"\nLOOSER - the two-times-dividing gives differing results !!!"; 00480 00481 delete[] spheres, histo1, histo2; 00482 cout <<"\n\n biggestcluster: \t"<<biggestcl1<<"\t"<<biggestcl2; 00483 cout <<"\n averagecluster: \t"<<averagecl1<<"\t"<<averagecl2; 00484 00485 cout <<"\n\nnormalcount: \t"<<ms(time1)<<"ms"; 00486 cout <<"\ndivide"<<cuts<<"times count: \t"<<ms(time2)<<"ms"<<endl; 00487 00488 cout <<"if you want to see the histograms, "; 00489 waitanykey(); 00490 show_twohisto(histo1, histo2, biggestcl1); 00491 } 00492 00493 00494 00495 void testspeedof_intersection_procedures(){ 00496 NUMLIST a, b, c1, c2; 00497 NUMBER N1,N2; 00498 cout <<"How many random numbers? "<<endl; 00499 cout <<"in list a: "; 00500 cin >>N1; 00501 cout <<"in list b: "; 00502 cin >>N2; 00503 00504 cout <<"generating random numbers in two lists..."<<endl; 00505 NUMBER i; 00506 for (i=0;i<N1;i++){ 00507 a.push_back(rand()); 00508 } 00509 for (i=0;i<N2;i++){ 00510 b.push_back(rand()); 00511 } 00512 cout <<"sorting the numbers in each list..."<<endl; 00513 clock_t t3=clock(); 00514 a.sort(); 00515 b.sort(); 00516 t3=clock()-t3; 00517 00518 cout <<"erasing the doubles in each list..."<<endl; 00519 clock_t t4=clock(); 00520 a.unique(); 00521 b.unique(); 00522 t4=clock()-t4; 00523 00524 cout <<"intersection of lists as if they were unsorted (NAIVE)..."<<endl; 00525 c1.clear(); 00526 clock_t t1=clock(); 00527 COUNTER n1=intersection_of_unsortedlists(a,b,c1); 00528 t1=clock()-t1; 00529 00530 cout <<"intersection of lists knowing they are sorted (CLEVER)..."<<endl; 00531 c2.clear(); 00532 clock_t t2=clock(); 00533 COUNTER n2=intersection_of_sortedlists(a,b,c2); 00534 t2=clock()-t2; 00535 00536 cout <<"\n"; 00537 cout <<a.size()<<" in list a, "<<b.size()<<" in list b."<<endl; 00538 cout <<c1.size()<<" in intersection:"<<endl; 00539 NUMLIST::iterator each1, each2; 00540 each2=c2.begin(); 00541 00542 for (each1=c1.begin(); each1!=c1.end(); each1++){ 00543 if ((*each1!=*each2)) { 00544 cout <<"\n"<<*each1<<"\t"<<*each2<<"\t"<<*each2<<"\t"<<endl; 00545 exit(0); 00546 } 00547 else cout <<*each1<<"\t"; 00548 each2++; 00549 } 00550 cout <<endl; 00551 cout <<"time(ms) \tfor 2*sort:\t"<<ms(t3)<<" \n\t\tfor 2*unique:\t"<<ms(t4)<<endl; 00552 cout <<"for intersection of unsorted list:\t"<<ms(t1)<<" \n\t\t of sorted list: \t"<<ms(t2)<<"\t"<<endl; 00553 cout <<"number of intersections: "<<n1<<"\t"<<n2<<endl; 00554 cout <<"completely equal? "<< ((c1==c2)?"yes":"no") <<endl; 00555 00556 } 00557 00558 #ifdef TIMEMEASUREMENT 00559 00560 void testspeed_divide_cellcount_combine(){ 00561 using counters::tdiv; 00562 using counters::tcom; 00563 cout <<"TIMEMEASUREMENT is switched ON.!!!"<<endl; 00564 NUMBER N; int dim; COUNTER ffc_loops; 00565 frontend::ask_for_dim_N_loops(N,dim,ffc_loops); 00566 cout<<"Give a random seed: ? "; 00567 int randseed; cin>>randseed; 00568 srand(randseed); 00569 ff::find_ffc_scanning_N_and_dim(dim, dim, N, N, 0.30, ffc_loops); 00570 00571 cout <<"\ndivide-and-conquer + naive cellcount\nThe space was cutted by "; 00572 COUNTER c=choose_optimal_cuts(dim,N, ff_critical_guessed(N, dim)); 00573 cout <<c<<" cuts, \nso that "<<pow(2,c)<<" cells had to be counted by naive recursion."<<endl; 00574 00575 REAL total=ms(tdiv.dividerecursion); // +ms(tdiv.divide)+ms(tdiv.cellcount)+ms(tdiv.clusterlist); 00576 cout <<"\nin the divide-and-conquer-counter, time was spent in:\n"; 00577 cout <<"divide spheres %\t"<<100*ms(tdiv.divide)/total<<endl; 00578 cout <<"cellcount (naive) %\t"<<100*ms(tdiv.cellcount)/total<<endl; 00579 cout <<"cell-clusterlist %\t"<<100*ms(tdiv.clusterlist)/total<<endl; 00580 cout <<"combine %\t"<<100*ms(tdiv.combine)/total<<endl; 00581 REAL recursion=total-ms(tdiv.divide+tdiv.cellcount+tdiv.clusterlist+tdiv.combine); 00582 cout <<"dividerecursion %\t"<<100*recursion/total<<endl; 00583 cout <<"total %\t100\n"<<endl;; 00584 00585 total=ms(tcom.sum()); 00586 cout <<"\nin the combine routine, time was spent in:\n"; 00587 cout <<"checks %\t"<<100*ms(tcom.checks)/total<<endl; 00588 cout <<"findedges %\t"<<100*ms(tcom.findedges)/total<<endl; 00589 cout <<"createobjects %\t"<<100*ms(tcom.createobjects)/total<<endl; 00590 cout <<"edgesphere_ovrlap %\t"<<100*ms(tcom.edgesphere_ovrlap)/total<<endl; 00591 cout <<"ovrlpclst_relabel %\t"<<100*ms(tcom.ovrlpclst_relabel)/total<<endl; 00592 cout <<"clustersplice %\t"<<100*ms(tcom.clustersplice)/total<<endl; 00593 cout <<"cleanclustertable %\t"<<100*ms(tcom.cleanclustertable)/total<<endl; 00594 cout <<"total %\t100\n"<<endl;; 00595 waitanykey(); 00596 00597 /* 00598 2dim, N=625 (cuts=4 -> 16 cells), 400 find_ffc-runs 00599 in the divide-and-conquer-counter, time was spent in: 00600 divide spheres % 16.2 00601 cellcount (naive) % 32.2 00602 cell-clusterlist % 4.0 00603 combine % 40.3 00604 dividerecursion % 7.3 00605 total % 100 00606 in the combine routine, time was spent in: 00607 checks % 1.2 00608 findedges % 20.8 00609 createobjects % 5.5 00610 edgesphere_ovrlap % 55.0 00611 ovrlpclst_relabel % 4.0 00612 clustersplice % 1.4 00613 cleanclustertable % 12.1 00614 total % 100 00615 00616 00617 2dim, N=2500 (cuts=5 -> 32 cells), 200 find_ffc-runs 00618 in the divide-and-conquer-counter, time was spent in: 00619 divide spheres % 14.3 00620 cellcount (naive) % 41.2 00621 cell-clusterlist % 3.0 00622 combine % 35.0 00623 dividerecursion % 6.5 00624 total % 100 00625 in the combine routine, time was spent in: 00626 checks % 7.9 00627 findedges % 15.4 00628 createobjects % 3.9 00629 edgesphere_ovrlap % 54.4 00630 ovrlpclst_relabel % 1.9 00631 clustersplice % 1.6 00632 cleanclustertable % 15.0 00633 total % 100 00634 00635 2dim, N=10000 (cuts=7 -> 128 cells), 100 find_ffc-runs 00636 in the divide-and-conquer-counter, time was spent in: 00637 divide spheres % 18.8 00638 cellcount (naive) % 27.6 00639 cell-clusterlist % 1.5 00640 combine % 44.9 00641 dividerecursion % 7.2 00642 total % 100 00643 in the combine routine, time was spent in: 00644 checks % 9.2 00645 findedges % 21.2 00646 createobjects % 3.4 00647 edgesphere_ovrlap % 46.1 00648 ovrlpclst_relabel % 1.4 00649 clustersplice % 3.0 00650 cleanclustertable % 15.7 00651 total % 100 00652 00653 2dim, N=40000 (cuts=9 -> 512 cells), 20 find_ffc-runs 00654 in the divide-and-conquer-counter, time was spent in: 00655 divide spheres % 17.6 00656 cellcount (naive) % 19.0 00657 cell-clusterlist % 1.3 00658 combine % 54.2 00659 dividerecursion % 8.0 00660 total % 100 00661 in the combine routine, time was spent in: 00662 checks % 9.1 00663 findedges % 18.5 00664 createobjects % 2.2 00665 edgesphere_ovrlap % 52.2 00666 ovrlpclst_relabel % 0.7 00667 clustersplice % 2.3 00668 cleanclustertable % 15.0 00669 total % 100 00670 00671 00672 6dim, N=625 (cuts=1 -> 2 cells), 50 find_ffc-runs 00673 in the divide-and-conquer-counter, time was spent in: 00674 divide spheres % 0.5 00675 cellcount (naive) % 56.2 00676 cell-clusterlist % 0.2 00677 combine % 42.9 00678 dividerecursion % 0.2 00679 total % 100 00680 in the combine routine, time was spent in: 00681 checks % 0 00682 findedges % 0.9 00683 createobjects % 0.7 00684 edgesphere_ovrlap % 94.6 00685 ovrlpclst_relabel % 0 00686 clustersplice % 0.2 00687 cleanclustertable % 3.5 00688 total % 100 00689 00690 00691 6dim, N=2500 (cuts=5 -> 32 cells), 30 find_ffc-runs 00692 in the divide-and-conquer-counter, time was spent in: 00693 divide spheres % 1.2 00694 cellcount (naive) % 6.9 00695 cell-clusterlist % 0.2 00696 combine % 91.0 00697 dividerecursion % 0.7 00698 total % 100 00699 in the combine routine, time was spent in: 00700 checks % 0.2 00701 findedges % 1.0 00702 createobjects % 1.0 00703 edgesphere_ovrlap % 94.8 00704 ovrlpclst_relabel % 0.1 00705 clustersplice % 0.1 00706 cleanclustertable % 2.8 00707 total % 100 00708 00709 00710 6dim, N=10000 (cuts=6 -> 64 cells), 20 find_ffc-runs 00711 in the divide-and-conquer-counter, time was spent in: 00712 divide spheres % 0.8 00713 cellcount (naive) % 5.2 00714 cell-clusterlist % 0.1 00715 combine % 93.6 00716 dividerecursion % 0.3 00717 total % 100 00718 in the combine routine, time was spent in: 00719 checks % 0.2 00720 findedges % 0.7 00721 createobjects % 0.4 00722 edgesphere_ovrlap % 96.6 00723 ovrlpclst_relabel % 0 00724 clustersplice % 0.1 00725 cleanclustertable % 1.9 00726 total % 100 00727 00728 6dim, N=40000 (cuts=6 -> 64 cells), 5 find_ffc-runs 00729 in the divide-and-conquer-counter, time was spent in: 00730 divide spheres % 0.3 00731 cellcount (naive) % 5.9 00732 cell-clusterlist % 0 00733 combine % 93.7 00734 dividerecursion % 0.1 00735 total % 100 00736 in the combine routine, time was spent in: 00737 checks % 0.1 00738 findedges % 0.3 00739 createobjects % 0.1 00740 edgesphere_ovrlap % 98.7 00741 ovrlpclst_relabel % 0 00742 clustersplice % 0 00743 cleanclustertable % 0.8 00744 total % 100 00745 00746 10dim, N=625 (cuts=0 -> 1 cell), 10 find_ffc-runs 00747 in the divide-and-conquer-counter, time was spent in: 00748 divide spheres % 0 00749 cellcount (naive) % 99.5 00750 cell-clusterlist % 0.5 00751 combine % 0 00752 dividerecursion % 0 00753 total % 100 00754 00755 10dim, N=2500 (cuts=3, 8 cells), 10 find_ffc-runs 00756 in the divide-and-conquer-counter, time was spent in: 00757 divide spheres % 0.2 00758 cellcount (naive) % 8.3 00759 cell-clusterlist % 0.1 00760 combine % 91.4 00761 dividerecursion % 0.1 00762 total % 100 00763 in the combine routine, time was spent in: 00764 checks % 0 00765 findedges % 0.2 00766 createobjects % 0.2 00767 edgesphere_ovrlap % 99.1 00768 ovrlpclst_relabel % 0 00769 clustersplice % 0 00770 cleanclustertable % 0.5 00771 total % 100 00772 00773 00774 10dim, N=10000 (cuts=4 -> 16 cells), 4 find_ffc-runs 00775 in the divide-and-conquer-counter, time was spent in: 00776 divide spheres % 0.1 00777 cellcount (naive) % 4.5 00778 cell-clusterlist % 0 00779 combine % 95.3 00780 dividerecursion % 0 00781 total % 100 00782 in the combine routine, time was spent in: 00783 checks % 0 00784 findedges % 0.1 00785 createobjects % 0.1 00786 edgesphere_ovrlap % 99.5 00787 ovrlpclst_relabel % 0 00788 clustersplice % 0 00789 cleanclustertable % 0.2 00790 total % 100 00791 00792 */ 00793 00794 } 00795 00796 #endif // TIMEMEASUREMENT 00797 00798 00799 } // end of namespace optimize
| Diploma Thesis Sourcecode
Documentation check out the text and the executable binaries |