AliRoot Core  3dc7879 (3dc7879)
kDTreeTest.C
Go to the documentation of this file.
1 /*
2  Test macro for TKDTree
3 
4  //Initialization:
5 
6  gSystem->AddIncludePath("-I$ALICE_ROOT/STAT")
7  gSystem->Load("$ALICE_ROOT/lib/tgt_linux/libSTAT");
8  .L $ALICE_ROOT/STAT/Macros/kDTreeTest.C+
9 
10 
11  TestBuild(); // test build function of kdTree for memory leaks
12  TestSpeed(); // test the CPU consumption to build kdTree
13  TestkdtreeIF(); // test functionality of the kdTree
14  TestSizeIF(); // test the size of kdtree - search application - Alice TPC tracker situation
15  //
16 */
17 
18 #include <malloc.h>
19 #include "TSystem.h"
20 #include "TMatrixD.h"
21 #include "TRandom.h"
22 #include "TGraph.h"
23 #include "TStopwatch.h"
24 #include "TKDTree.h"
25 
26 
27 
28 
29 void TestBuild(const Int_t npoints = 1000000, const Int_t bsize = 100);
30 void TestSpeed(const Int_t npower2 = 20, const Int_t bsize = 10);
31 
32 void TestkdtreeIF(Int_t npoints=1000, Int_t bsize=9, Int_t nloop=1000, Int_t mode = 2);
33 void TestSizeIF(Int_t nsec=36, Int_t nrows=159, Int_t npoints=1000, Int_t bsize=10, Int_t mode=1);
34 
35 
36 
37 Float_t Mem()
38 {
39  // get mem info
40  ProcInfo_t procInfo;
41  gSystem->GetProcInfo(&procInfo);
42  return procInfo.fMemVirtual;
43 }
44 
45 //______________________________________________________________________
46 void kDTreeTest()
47 {
48  //
49  //
50  //
51  printf("\n\tTesting kDTree memory usage ...\n");
52  TestBuild();
53  printf("\n\tTesting kDTree speed ...\n");
54  TestSpeed();
55 }
56 
57 //______________________________________________________________________
58 void TestBuild(const Int_t npoints, const Int_t bsize){
59  //
60  // Test kdTree for memory leaks
61  //
62  Float_t *data0 = new Float_t[npoints*2];
63  Float_t *data[2];
64  data[0] = &data0[0];
65  data[1] = &data0[npoints];
66  for (Int_t i=0;i<npoints;i++) {
67  data[1][i]= gRandom->Rndm();
68  data[0][i]= gRandom->Rndm();
69  }
70  Float_t before =Mem();
71  TKDTreeIF *kdtree = new TKDTreeIF(npoints, 2, bsize, data);
72  Float_t after = Mem();
73  printf("Memory usage %f KB\n",after-before);
74  delete kdtree;
75  Float_t end = Mem();
76  printf("Memory leak %f KB\n", end-before);
77  return;
78 }
79 
80 //______________________________________________________________________
81 void TestSpeed(const Int_t npower2, const Int_t bsize)
82 {
83  //
84  // Test of building time of kdTree
85  //
86  if(npower2 < 10){
87  printf("Please specify a power of 2 greater than 10\n");
88  return;
89  }
90 
91  Int_t npoints = Int_t(pow(2., npower2))*bsize;
92  Float_t *data0 = new Float_t[npoints*2];
93  Float_t *data[2];
94  data[0] = &data0[0];
95  data[1] = &data0[npoints];
96  for (Int_t i=0;i<npoints;i++) {
97  data[1][i]= gRandom->Rndm();
98  data[0][i]= gRandom->Rndm();
99  }
100 
101  TGraph *g = new TGraph(npower2-10);
102  g->SetMarkerStyle(7);
103  TStopwatch timer;
104  Int_t tpoints;
105  TKDTreeIF *kdtree = 0x0;
106  for(int i=10; i<npower2; i++){
107  tpoints = Int_t(pow(2., i))*bsize;
108  timer.Start(kTRUE);
109  kdtree = new TKDTreeIF(tpoints, 2, bsize, data);
110  timer.Stop();
111  g->SetPoint(i-10, i, timer.CpuTime());
112  printf("npoints [%d] nodes [%d] cpu time %f [s]\n", tpoints, kdtree->GetNNodes(), timer.CpuTime());
113  //timer.Print("u");
114  delete kdtree;
115  }
116  g->Draw("apl");
117  return;
118 }
119 
120 //______________________________________________________________________
121 void TestSizeIF(Int_t nsec, Int_t nrows, Int_t npoints, Int_t bsize, Int_t mode)
122 {
123  //
124  // Test size to build kdtree
125  //
126  Float_t before =Mem();
127  for (Int_t isec=0; isec<nsec;isec++)
128  for (Int_t irow=0;irow<nrows;irow++){
129  TestkdtreeIF(npoints,1,mode,bsize);
130  }
131  Float_t after = Mem();
132  printf("Memory usage %f\n",after-before);
133 }
134 
135 
136 
137 
138 void TestkdtreeIF(Int_t npoints, Int_t bsize, Int_t nloop, Int_t mode)
139 {
140 //
141 // Test speed and functionality of 2D kdtree.
142 // Input parametrs:
143 // npoints - number of data points
144 // bsize - bucket size
145 // nloop - number of loops
146 // mode - tasks to be performed by the kdTree
147 // - 0 : time building the tree
148 //
149 
150 
151  Float_t rangey = 100;
152  Float_t rangez = 100;
153  Float_t drangey = 0.1;
154  Float_t drangez = 0.1;
155 
156  //
157  Float_t *data0 = new Float_t[npoints*2];
158  Float_t *data[2];
159  data[0] = &data0[0];
160  data[1] = &data0[npoints];
161  Int_t i;
162  for (i=0; i<npoints; i++){
163  data[0][i] = gRandom->Uniform(-rangey, rangey);
164  data[1][i] = gRandom->Uniform(-rangez, rangez);
165  }
166  TStopwatch timer;
167 
168  // check time build
169  printf("building kdTree ...\n");
170  timer.Start(kTRUE);
171  TKDTreeIF *kdtree = new TKDTreeIF(npoints, 2, bsize, data);
172  timer.Stop();
173  timer.Print();
174  if(mode == 0) return;
175 
176  Float_t countern=0;
177  Float_t counteriter = 0;
178  Float_t counterfound = 0;
179 
180  if (mode ==2){
181  if (nloop) timer.Start(kTRUE);
182  Int_t res[npoints];
183  Int_t nfound = 0;
184  for (Int_t kloop = 0;kloop<nloop;kloop++){
185  if (kloop==0){
186  counteriter = 0;
187  counterfound= 0;
188  countern = 0;
189  }
190  for (Int_t i=0;i<npoints;i++){
191  Float_t point[2]={data[0][i],data[1][i]};
192  Float_t delta[2]={drangey,drangez};
193  Int_t iter =0;
194  nfound =0;
195  Int_t bnode =0;
196  //kdtree->FindBNode(point,delta, bnode);
197  //continue;
198  kdtree->FindInRangeA(point,delta,res,nfound,iter,bnode);
199  if (kloop==0){
200  //Bool_t isOK = kTRUE;
201  Bool_t isOK = kFALSE;
202  for (Int_t ipoint=0;ipoint<nfound;ipoint++)
203  if (res[ipoint]==i) isOK =kTRUE;
204  counteriter+=iter;
205  counterfound+=nfound;
206  if (isOK) {
207  countern++;
208  }else{
209  printf("Bug\n");
210  }
211  }
212  }
213  }
214 
215  if (nloop){
216  timer.Stop();
217  timer.Print();
218  }
219  }
220  delete [] data0;
221 
222  counteriter/=npoints;
223  counterfound/=npoints;
224  if (nloop) printf("Find nearest point:\t%f\t%f\t%f\n",countern, counteriter, counterfound);
225 }
void TestSizeIF(Int_t nsec=36, Int_t nrows=159, Int_t npoints=1000, Int_t bsize=10, Int_t mode=1)
Definition: kDTreeTest.C:121
printf("Chi2/npoints = %f\n", TMath::Sqrt(chi2/npoints))
TStopwatch timer
Definition: kNNSpeed.C:15
void TestBuild(const Int_t npoints=1000000, const Int_t bsize=100)
Definition: kDTreeTest.C:58
npoints
Definition: driftITSTPC.C:85
Float_t Mem()
Definition: kDTreeTest.C:37
void TestSpeed(const Int_t npower2=20, const Int_t bsize=10)
Definition: kDTreeTest.C:81
void kDTreeTest()
Definition: kDTreeTest.C:46
ProcInfo_t procInfo
void TestkdtreeIF(Int_t npoints=1000, Int_t bsize=9, Int_t nloop=1000, Int_t mode=2)
Definition: kDTreeTest.C:138
class TKDTree< Int_t, Float_t > TKDTreeIF
void res(Char_t i)
Definition: Resolution.C:2