]>
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 | ||
3fbc6987 | 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 | // | |
bf43b41a | 16 | */ |
17 | ||
8a8f8274 | 18 | #include <malloc.h> |
bf43b41a | 19 | #include "TSystem.h" |
8a8f8274 | 20 | #include "TMatrixD.h" |
21 | #include "TRandom.h" | |
22 | #include "TGraph.h" | |
23 | #include "TStopwatch.h" | |
bf43b41a | 24 | #include "TKDTree.h" |
8a8f8274 | 25 | |
26 | ||
3fbc6987 | 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 | ||
8a8f8274 | 37 | Float_t Mem() |
38 | { | |
bf43b41a | 39 | // get mem info |
40 | ProcInfo_t procInfo; | |
41 | gSystem->GetProcInfo(&procInfo); | |
42 | return procInfo.fMemVirtual; | |
8a8f8274 | 43 | } |
44 | ||
8a8f8274 | 45 | //______________________________________________________________________ |
46 | void kDTreeTest() | |
47 | { | |
3fbc6987 | 48 | // |
49 | // | |
50 | // | |
51 | printf("\n\tTesting kDTree memory usage ...\n"); | |
52 | TestBuild(); | |
53 | printf("\n\tTesting kDTree speed ...\n"); | |
54 | TestSpeed(); | |
8a8f8274 | 55 | } |
56 | ||
57 | //______________________________________________________________________ | |
58 | void TestBuild(const Int_t npoints, const Int_t bsize){ | |
bf43b41a | 59 | // |
3fbc6987 | 60 | // Test kdTree for memory leaks |
bf43b41a | 61 | // |
8a8f8274 | 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 | { | |
3fbc6987 | 83 | // |
84 | // Test of building time of kdTree | |
85 | // | |
bf43b41a | 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]; | |
8a8f8274 | 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 | } | |
bf43b41a | 100 | |
101 | TGraph *g = new TGraph(npower2-10); | |
102 | g->SetMarkerStyle(7); | |
103 | TStopwatch timer; | |
104 | Int_t tpoints; | |
8a8f8274 | 105 | TKDTreeIF *kdtree = 0x0; |
bf43b41a | 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; | |
8a8f8274 | 118 | } |
119 | ||
120 | //______________________________________________________________________ | |
3fbc6987 | 121 | void TestSizeIF(Int_t nsec, Int_t nrows, Int_t npoints, Int_t bsize, Int_t mode) |
8a8f8274 | 122 | { |
123 | // | |
3fbc6987 | 124 | // Test size to build kdtree |
8a8f8274 | 125 | // |
126 | Float_t before =Mem(); | |
127 | for (Int_t isec=0; isec<nsec;isec++) | |
128 | for (Int_t irow=0;irow<nrows;irow++){ | |
3fbc6987 | 129 | TestkdtreeIF(npoints,1,mode,bsize); |
8a8f8274 | 130 | } |
131 | Float_t after = Mem(); | |
132 | printf("Memory usage %f\n",after-before); | |
133 | } | |
134 | ||
135 | ||
8a8f8274 | 136 | |
137 | ||
3fbc6987 | 138 | void TestkdtreeIF(Int_t npoints, Int_t bsize, Int_t nloop, Int_t mode) |
8a8f8274 | 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; | |
3fbc6987 | 167 | |
168 | // check time build | |
169 | printf("building kdTree ...\n"); | |
170 | timer.Start(kTRUE); | |
8a8f8274 | 171 | TKDTreeIF *kdtree = new TKDTreeIF(npoints, 2, bsize, data); |
172 | timer.Stop(); | |
173 | timer.Print(); | |
bf43b41a | 174 | if(mode == 0) return; |
175 | ||
bf43b41a | 176 | Float_t countern=0; |
177 | Float_t counteriter = 0; | |
178 | Float_t counterfound = 0; | |
179 | ||
bf43b41a | 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 | } | |
8a8f8274 | 211 | } |
bf43b41a | 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); | |
8a8f8274 | 225 | } |