Logo ROOT   6.10/09
Reference Guide
binarySearchTime.cxx
Go to the documentation of this file.
1 #include <iostream>
2 #include <ctime>
3 #include <cstring>
4 #include <vector>
5 
6 #include <TRandom2.h>
7 #include <TMath.h>
8 #include <TStopwatch.h>
9 
10 #include <TApplication.h>
11 #include <TCanvas.h>
12 #include <TH2F.h>
13 #include <TGraph.h>
14 #include <TLegend.h>
15 #include <TAxis.h>
16 
17 using namespace std;
18 
19 const int npass0 = 200000;
20 const int maxint = 100;//20;
21 const int minsize = 10;//20;
22 const int maxsize = 1000000;//500;
23 const int increment = 10; // increment factor (multiplicative)
24 const int arraysize = int(std::log10(double(maxsize/minsize)))+1;
25 
26 bool showGraphics = false;
27 bool verbose = false;
28 
29 template <typename T> bool testBinarySearch(const int n, double* tTMath, double* tStd)
30 {
31  std::cout << "Testing size n = " << n << "\t(Time / call in microsec.) " << std::endl;
32 
33  vector<T> k(n);
34  TStopwatch t;
35  TRandom2 r( time( 0 ) );
36  for ( Int_t i = 0; i < n; i++) {
37  k[i] = (T) r.Integer( maxint );
38  }
39 
40  std::sort(k.begin(), k.end());
41 
42  int npass = npass0/std::log10(double(10*n/minsize));
43 
44  int s1 = 0;
45  t.Start();
46  for (int j = 0; j < npass; ++j) {
47  for ( T elem = 0; elem < maxint; ++elem ) {
48  Long_t index = TMath::BinarySearch((Long_t) n, &k[0], elem);
49  s1 += index;
50  }
51  }
52  t.Stop();
53  *tTMath = t.RealTime()/npass*1.E6;
54  cout << "TMath::BinarySearch time :\t " << *tTMath << endl;
55 // cout << "sum " << s1 << endl;
56 
57  int s2 = 0;
58  t.Start();
59  for (int j = 0; j < npass; ++j) {
60  for ( T elem = 0; elem < maxint; ++elem ) {
61  T* pind;
62  pind = std::lower_bound(&k[0], &k[n], elem);
63  Long_t index2 = ((*pind == elem)? (pind - &k[0]): ( pind - &k[0] - 1));
64  s2+= index2;
65  }
66  }
67  t.Stop();
68  *tStd = t.RealTime()/double(npass)*1.E6;
69  std::cout << "std::binary_search time:\t " << *tStd << '\n' << std::endl;
70 // cout << "sum " << s2 << endl;
71  if (s1 != s2) {
72  Error("testBinarySearch","Different results obtained for size n = %d - s1 = %d s2 = %d",n,s1,s2);
73  return false;
74  }
75  return true;
76 
77 }
78 
80 {
81  vector<double> tM( arraysize );
82  vector<double> tS( arraysize );
83  vector<double> index( arraysize );
84 
85  //cout << (maxsize-minsize)/10 + 1 << endl;
86 
87  bool ok = true;
88  int j = 0; int i = minsize;
89  while ( i <= maxsize)
90  {
91  ok &= testBinarySearch<Double_t>(i, &tM[j], &tS[j]);
92  index[j] = i;
93  j++;
94  i *= increment;
95  }
96  int ntest = j;
97 
98  if (verbose) {
99  cout << " TMATH - time --- std time " << std::endl;
100  for ( i = 0; i < ntest; ++i) {
101  cout << " size = " << index[i] << " : " << tM[i] << ' ' << tS[i] << endl;
102  }
103  }
104 
105  if ( showGraphics )
106  {
107  TCanvas* c1 = new TCanvas("c1", "Comparision of Searching Time", 600, 400);
108  c1->SetLogx(true);
109 
110  TGraph* gM = new TGraph(arraysize, &index[0], &tM[0]);
111  gM->SetLineColor(2);
112  gM->SetLineWidth(3);
113  gM->SetMarkerStyle(20);
114  gM->SetTitle("TMath::BinarySearch()");
115  gM->Draw("ALP");
116 
117  TGraph* gS = new TGraph(arraysize, &index[0], &tS[0]);
118  gS->SetLineColor(3);
119  gS->SetLineWidth(3);
120  gS->SetMarkerStyle(20);
121  gS->SetTitle("std::binary_search()");
122  gS->Draw("SAME");
123 
124  TLegend* legend = new TLegend(0.15,0.72,0.4,0.86);
125  legend->AddEntry(gM, "TMath::BinarySearch()");
126  legend->AddEntry(gS, "std::binary_search()");
127  legend->Draw();
128 
129  gM->SetTitle("Comparision of Searching Time");
130  gM->GetXaxis()->SetTitle("Array Size");
131  gM->GetYaxis()->SetTitle("Time");
132 
133 
134  c1->Show();
135  }
136 
137  if (ok)
138  cout << "Test done!" << endl;
139  else
140  cout << "Error: Test Failed!" << endl;
141  return ok;
142 }
143 
144 int main(int argc, char **argv)
145 {
146 
147  // Parse command line arguments
148  for (Int_t i=1 ; i<argc ; i++) {
149  std::string arg = argv[i] ;
150  if (arg == "-g") {
151  showGraphics = true;
152  }
153  if (arg == "-v") {
154  showGraphics = true;
155  verbose = true;
156  }
157  if (arg == "-h") {
158  cerr << "Usage: " << argv[0] << " [-g] [-v]\n";
159  cerr << " where:\n";
160  cerr << " -g : graphics mode\n";
161  cerr << " -v : verbose mode";
162  cerr << endl;
163  return -1;
164  }
165  }
166 
167  TApplication* theApp = 0;
168  if ( showGraphics )
169  theApp = new TApplication("App",&argc,argv);
170 
171 
172  bool ok = binarySearchTime();
173 
174  if ( showGraphics )
175  {
176  theApp->Run();
177  delete theApp;
178  theApp = 0;
179  }
180 
181  return (ok) ? 0 : 1;
182 }
virtual void SetLineWidth(Width_t lwidth)
Set the line width.
Definition: TAttLine.h:43
const int npass
Definition: testPermute.cxx:21
const int npass0
Double_t RealTime()
Stop the stopwatch (if it is running) and return the realtime (in seconds) passed between the start a...
Definition: TStopwatch.cxx:110
This class displays a legend box (TPaveText) containing several legend entries.
Definition: TLegend.h:23
void Start(Bool_t reset=kTRUE)
Start the stopwatch.
Definition: TStopwatch.cxx:58
return c1
Definition: legend1.C:41
double T(double x)
Definition: ChebyshevPol.h:34
Random number generator class based on the maximally quidistributed combined Tausworthe generator by ...
Definition: TRandom2.h:27
virtual void Draw(Option_t *option="")
Draw this legend with its current attributes.
Definition: TLegend.cxx:452
TAxis * GetYaxis() const
Get y axis of the graph.
Definition: TGraph.cxx:1602
int Int_t
Definition: RtypesCore.h:41
virtual void SetTitle(const char *title="")
Set graph title.
Definition: TGraph.cxx:2180
const int minsize
STL namespace.
int main(int argc, char **argv)
virtual void Draw(Option_t *chopt="")
Draw this graph with its current attributes.
Definition: TGraph.cxx:745
TLegend * legend
Definition: pirndm.C:35
void Stop()
Stop the stopwatch.
Definition: TStopwatch.cxx:77
virtual void Run(Bool_t retrn=kFALSE)
Main application eventloop. Calls system dependent eventloop via gSystem.
double log10(double)
virtual UInt_t Integer(UInt_t imax)
Returns a random integer on [ 0, imax-1 ].
Definition: TRandom.cxx:320
const int maxsize
bool testBinarySearch(const int n, double *tTMath, double *tStd)
virtual void SetLogx(Int_t value=1)
Set Lin/Log scale for X.
Definition: TPad.cxx:5766
void Error(const char *location, const char *msgfmt,...)
virtual void SetLineColor(Color_t lcolor)
Set the line color.
Definition: TAttLine.h:40
TRandom2 r(17)
bool showGraphics
bool verbose
const int arraysize
virtual void SetMarkerStyle(Style_t mstyle=1)
Set the marker style.
Definition: TAttMarker.h:40
TAxis * GetXaxis() const
Get x axis of the graph.
Definition: TGraph.cxx:1592
long Long_t
Definition: RtypesCore.h:50
The Canvas class.
Definition: TCanvas.h:31
TLegendEntry * AddEntry(const TObject *obj, const char *label="", Option_t *option="lpf")
Add a new entry to this legend.
Definition: TLegend.cxx:359
const int increment
const int maxint
A Graph is a graphics object made of two arrays X and Y with npoints each.
Definition: TGraph.h:41
void Show()
Definition: TCanvas.h:212
bool binarySearchTime()
This class creates the ROOT Application Environment that interfaces to the windowing system eventloop...
Definition: TApplication.h:39
virtual void SetTitle(const char *title="")
Set the title of the TNamed.
Definition: TNamed.cxx:155
const Int_t n
Definition: legend1.C:16
Long64_t BinarySearch(Long64_t n, const T *array, T value)
Definition: TMath.h:1093
Stopwatch class.
Definition: TStopwatch.h:28