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