ROOT logo
#include "TSystem.h"
#include "TFile.h"
#include "TTree.h"
#include "TH2I.h"
#include "TLegend.h"
#include "TRandom.h"
#include "TString.h"
#include "TGraph.h"
#include "TMarker.h"
#include "TStopwatch.h"
#include "../src/TKDInterpolator.h"
#include "../src/TKDTree.h"

const int ntimes = 500000; // times to repeate kNN search
TStopwatch timer;

Float_t kdTreeNN(Float_t **p, const int ndim = 5, const int np = 10000);
Float_t standAloneNN(Float_t **p, const int ndim = 5, const int np = 10000);

//______________________________________________________________
TTree *db = 0x0;
void kNNSpeed(const Int_t method = 0)
{
// Estimate kNN algorithm speed:
// method = 0 : run kDTree kNN search
// method = 1 : run kNN loop search

	const Int_t ndim  = 5;
	const Int_t nstat = 9;


	// generate test sample
	Float_t **p = new Float_t*[ntimes];
	for(int ip =0 ; ip<ntimes; ip++){
		p[ip] = new Float_t[ndim];
		for(int idim=0; idim<ndim; idim++) p[ip][idim] = gRandom->Uniform(-.5, .5);
	}

	Float_t time;
	Int_t stat;
	TLegend *leg = new TLegend(.7, .7, .9, .9);
	TH1 *h1 = new TH1I("h1", "", 100, 9.5, 20.5);
	h1->SetMaximum(1.E2);
	h1->SetMinimum(1.E-1);
	h1->GetXaxis()->SetTitle("Statistics");
	h1->GetYaxis()->SetTitle("CPU [#mus]");
	h1->SetStats(0);
	h1->Draw();
	TGraph **g=new TGraph*[ndim];
	for(int idim=2; idim<3/*ndim*/; idim++){
		g[idim] = new TGraph(nstat);
		g[idim]->SetMarkerStyle(20+idim);
		g[idim]->SetMarkerColor(idim+1);
		leg->AddEntry(g[idim], Form("%dD", idim+1), "pl");
		stat = 16384;//1024;
		for(int istat = 0; istat<nstat; istat++){
			time = kdTreeNN(p, idim+1, stat);
			//time = standAloneNN(p, idim+1, stat);
			g[idim]->SetPoint(istat, TMath::Log2(float(stat)), time);
			stat *= 2;
		}
		g[idim]->Draw("pl");
	}
	leg->Draw();
	
	for(int ip=0; ip<ntimes; ip++) delete [] p[ip];
	delete [] p;
}

//______________________________________________________________
Float_t kdTreeNN(Float_t **p, const int ndim, const int np)
{
	Float_t **x = new Float_t*[ndim];
	for(int idim =0 ; idim<ndim; idim++){
		x[idim] = new Float_t[np];
		for(int ip=0; ip<np; ip++) x[idim][ip] = gRandom->Gaus();
	}
	TKDTreeIF nnFinder(np, ndim, 1, x);
	nnFinder.MakeBoundaries();
	
	Int_t *index, fNN = 1;
	Float_t *d;
	timer.Start(kTRUE);
	for(int itime=0; itime<ntimes; itime++){
		nnFinder.FindNearestNeighbors(p[itime], fNN, index, d);
	}
	timer.Stop();
	Float_t time = 1.E6*timer.CpuTime()/float(ntimes);

	printf("np[%7d] nd[%d] time = %5.2f[mus]\n", np, ndim, time);
	
	// clean
	for(int idim=0; idim<ndim; idim++) delete [] x[idim];
	delete [] x;
	

	return time;
}

//______________________________________________________________
Float_t standAloneNN(Float_t **p, const int ndim, const int np)
{	
	// STAND ALONE
	const Int_t kNN = 1;
	Float_t ftmp, gtmp, dist;
	Int_t itmp, jtmp;
	Int_t   fkNN[kNN];
	Float_t fkNNdist[kNN];
	for(int i=0; i<kNN; i++) fkNNdist[i] = 9999.;

	Float_t **x = new Float_t*[ndim];
	for(int idim =0 ; idim<ndim; idim++){
		x[idim] = new Float_t[np];
		for(int ip=0; ip<np; ip++) x[idim][ip] = gRandom->Gaus();
	}
	Int_t npoints = np;
	
	// calculate
	Int_t ntimes = 100;
	timer.Start(kTRUE);
	for(int it=0; it<ntimes; it++){
		for(int idx=0; idx<npoints; idx++){
			// calculate distance in the L1 metric
			dist = 0.;
			for(int idim=0; idim<ndim; idim++) dist += TMath::Abs(p[it*10][idim] - x[idim][idx]);
			if(dist >= fkNNdist[kNN-1]) continue;
	
			//insert neighbor
			int iNN=0;
			while(dist >= fkNNdist[iNN]) iNN++;
			itmp = fkNN[iNN]; ftmp = fkNNdist[iNN];
			fkNN[iNN]     = idx;
			fkNNdist[iNN] = dist;
			for(int ireplace=iNN+1; ireplace<kNN; ireplace++){
				jtmp = fkNN[ireplace]; gtmp = fkNNdist[ireplace];
				fkNN[ireplace] = itmp; fkNNdist[ireplace] = ftmp;
				itmp = jtmp; ftmp = gtmp;
				if(ftmp == 9999.) break;
			}
		}
	}
	timer.Stop();
	
	Float_t time = timer.CpuTime()/float(ntimes);
	printf("np[%5d] nd[%d] time[%f] %6.2f\n", np, ndim, time, timer.CpuTime());

	return time;
}

 kNNSpeed.C:1
 kNNSpeed.C:2
 kNNSpeed.C:3
 kNNSpeed.C:4
 kNNSpeed.C:5
 kNNSpeed.C:6
 kNNSpeed.C:7
 kNNSpeed.C:8
 kNNSpeed.C:9
 kNNSpeed.C:10
 kNNSpeed.C:11
 kNNSpeed.C:12
 kNNSpeed.C:13
 kNNSpeed.C:14
 kNNSpeed.C:15
 kNNSpeed.C:16
 kNNSpeed.C:17
 kNNSpeed.C:18
 kNNSpeed.C:19
 kNNSpeed.C:20
 kNNSpeed.C:21
 kNNSpeed.C:22
 kNNSpeed.C:23
 kNNSpeed.C:24
 kNNSpeed.C:25
 kNNSpeed.C:26
 kNNSpeed.C:27
 kNNSpeed.C:28
 kNNSpeed.C:29
 kNNSpeed.C:30
 kNNSpeed.C:31
 kNNSpeed.C:32
 kNNSpeed.C:33
 kNNSpeed.C:34
 kNNSpeed.C:35
 kNNSpeed.C:36
 kNNSpeed.C:37
 kNNSpeed.C:38
 kNNSpeed.C:39
 kNNSpeed.C:40
 kNNSpeed.C:41
 kNNSpeed.C:42
 kNNSpeed.C:43
 kNNSpeed.C:44
 kNNSpeed.C:45
 kNNSpeed.C:46
 kNNSpeed.C:47
 kNNSpeed.C:48
 kNNSpeed.C:49
 kNNSpeed.C:50
 kNNSpeed.C:51
 kNNSpeed.C:52
 kNNSpeed.C:53
 kNNSpeed.C:54
 kNNSpeed.C:55
 kNNSpeed.C:56
 kNNSpeed.C:57
 kNNSpeed.C:58
 kNNSpeed.C:59
 kNNSpeed.C:60
 kNNSpeed.C:61
 kNNSpeed.C:62
 kNNSpeed.C:63
 kNNSpeed.C:64
 kNNSpeed.C:65
 kNNSpeed.C:66
 kNNSpeed.C:67
 kNNSpeed.C:68
 kNNSpeed.C:69
 kNNSpeed.C:70
 kNNSpeed.C:71
 kNNSpeed.C:72
 kNNSpeed.C:73
 kNNSpeed.C:74
 kNNSpeed.C:75
 kNNSpeed.C:76
 kNNSpeed.C:77
 kNNSpeed.C:78
 kNNSpeed.C:79
 kNNSpeed.C:80
 kNNSpeed.C:81
 kNNSpeed.C:82
 kNNSpeed.C:83
 kNNSpeed.C:84
 kNNSpeed.C:85
 kNNSpeed.C:86
 kNNSpeed.C:87
 kNNSpeed.C:88
 kNNSpeed.C:89
 kNNSpeed.C:90
 kNNSpeed.C:91
 kNNSpeed.C:92
 kNNSpeed.C:93
 kNNSpeed.C:94
 kNNSpeed.C:95
 kNNSpeed.C:96
 kNNSpeed.C:97
 kNNSpeed.C:98
 kNNSpeed.C:99
 kNNSpeed.C:100
 kNNSpeed.C:101
 kNNSpeed.C:102
 kNNSpeed.C:103
 kNNSpeed.C:104
 kNNSpeed.C:105
 kNNSpeed.C:106
 kNNSpeed.C:107
 kNNSpeed.C:108
 kNNSpeed.C:109
 kNNSpeed.C:110
 kNNSpeed.C:111
 kNNSpeed.C:112
 kNNSpeed.C:113
 kNNSpeed.C:114
 kNNSpeed.C:115
 kNNSpeed.C:116
 kNNSpeed.C:117
 kNNSpeed.C:118
 kNNSpeed.C:119
 kNNSpeed.C:120
 kNNSpeed.C:121
 kNNSpeed.C:122
 kNNSpeed.C:123
 kNNSpeed.C:124
 kNNSpeed.C:125
 kNNSpeed.C:126
 kNNSpeed.C:127
 kNNSpeed.C:128
 kNNSpeed.C:129
 kNNSpeed.C:130
 kNNSpeed.C:131
 kNNSpeed.C:132
 kNNSpeed.C:133
 kNNSpeed.C:134
 kNNSpeed.C:135
 kNNSpeed.C:136
 kNNSpeed.C:137
 kNNSpeed.C:138
 kNNSpeed.C:139
 kNNSpeed.C:140
 kNNSpeed.C:141
 kNNSpeed.C:142
 kNNSpeed.C:143
 kNNSpeed.C:144
 kNNSpeed.C:145
 kNNSpeed.C:146
 kNNSpeed.C:147
 kNNSpeed.C:148
 kNNSpeed.C:149
 kNNSpeed.C:150