Logo ROOT   6.08/07
Reference Guide
stdsort.cxx
Go to the documentation of this file.
1 #include <iostream>
2 #include <algorithm>
3 #include <ctime>
4 #include <vector>
5 
6 #include "TStopwatch.h"
7 #include "TMath.h"
8 #include "TRandom2.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 //#include <TSystem.h>
17 
18 using namespace std;
19 
20 const int npass0 = 200000;
21 const int maxint = 20;
22 const int minsize = 10;
23 const int maxsize = 100000;
24 const int increment = 2;
25 const int arraysize = 20;
26 
27 bool showGraphics = false;
28 bool verbose = false;
29 //std::string plotFile;
30 
31 template<typename T>
32 struct Compare {
33 
34  Compare(const T * d) : fData(d) {}
35 
36  bool operator()(int i1, int i2) {
37  return fData[i1] > fData[i2];
38  }
39 
40  const T * fData;
41 };
42 
43 template <typename T> bool testSort(const int n, double* tTMath, double* tStd)
44 {
45 
46  std::cout << "Testing Sort of array - size n = " << n << "\t(Time / call in microsec.) " << std::endl;
47 
48  vector<T> k(n);
49 
50  vector<T> index(n);
51  vector<T> index2(n);
52  TStopwatch t;
53 
54  TRandom2 r( time( 0 ) );
55  for ( Int_t i = 0; i < n; i++) {
56  k[i] = (T) r.Integer( maxint );
57 // cout << k[i] << ' ' << endl;
58  }
59 
60  //int npass = npass0/std::log10(10*n/minsize);
61  int npass = npass0/(n/minsize);
62 
63  t.Start();
64  for (int j = 0; j < npass; ++j) {
65 // for(Int_t i = 0; i < n; i++) { index[i] = i; }
66  TMath::Sort(n,&k[0],&index[0],kTRUE);
67  }
68  t.Stop();
69  *tTMath = t.RealTime()/npass*1.E6;
70  cout << "TMath::Sort time :\t\t " << *tTMath << endl;
71 
72 
73  t.Start();
74  for (int j = 0; j < npass; ++j) {
75  for(Int_t i = 0; i < n; i++) { index2[i] = i; }
76  std::sort(&index2[0],&index2[0]+n, Compare<T>(&k[0]) );
77  }
78  t.Stop();
79  *tStd = t.RealTime()/npass*1.E6;
80  std::cout << "std::sort time (using indices):\t " << *tStd << std::endl;
81 
82  // test results
83  bool ok = true;
84  for(Int_t i = 0; i < n && ok; i++) {
85  ok &= (index[i] == index2[i]);
86  if (!ok) Error("test sort","Different values found at i= %d - index1 = %d - index2 = %d",i,index[i],index2[i]);
87  }
88  return ok;
89 }
90 
91 bool stdsort()
92 {
93  vector<double> tM( arraysize );
94  vector<double> tS( arraysize );
95  vector<double> index( arraysize );
96 
97  //cout << (maxsize-minsize)/10 + 1 << endl;
98 
99  bool ok = true;
100  int j = 0; int i = minsize;
101  while ( i <= maxsize && j < arraysize)
102  {
103  ok &= testSort<Int_t>(i, &tM[j], &tS[j]);
104  index[j] = i;
105  j++;
106  i *= increment;
107  }
108  int ntest = j;
109 
110  if (verbose) {
111  cout << " TMATH - time --- std time " << std::endl;
112  for ( i = 0; i < ntest; ++i) {
113  cout << " size = " << index[i] << " : " << tM[i] << ' ' << tS[i] << endl;
114  }
115  }
116 
117  if ( showGraphics )
118  {
119  TCanvas* c1 = new TCanvas("c1", "Comparision of Sorting Time", 600, 400);
120 
121  TGraph* gM = new TGraph(ntest, &index[0], &tM[0]);
122  gM->SetLineColor(2);
123  gM->SetLineWidth(3);
124  gM->SetMarkerStyle(20);
125  gM->SetTitle("TMath::Sort()");
126  gM->Draw("ALP");
127 
128  TGraph* gS = new TGraph(arraysize, &index[0], &tS[0]);
129  gS->SetLineColor(3);
130  gS->SetLineWidth(3);
131  gS->SetTitle("std::sort()");
132  gS->Draw("SAME");
133 
134  TLegend* legend = new TLegend(0.15,0.72,0.4,0.86);
135  legend->AddEntry(gM, "TMath::Sort()");
136  legend->AddEntry(gS, "std::sort()");
137  legend->Draw();
138 
139  TH1 * hpx = gM->GetHistogram();
140  hpx->GetXaxis()->SetTitle("Array Size");
141  hpx->GetYaxis()->SetTitle("Time");
142  hpx->SetTitle("Comparison of Sorting Time");
143 
144 
145  c1->Show();
146 
147  }
148 
149  return ok;
150 }
151 
152 int main(int argc, char **argv)
153 {
154 
155  // Parse command line arguments
156  for (Int_t i=1 ; i<argc ; i++) {
157  std::string arg = argv[i] ;
158  if (arg == "-g") {
159  showGraphics = true;
160  }
161  if (arg == "-v") {
162  showGraphics = true;
163  verbose = true;
164  }
165  if (arg == "-h") {
166  cerr << "Usage: " << argv[0] << " [-g] [-v]\n";
167  cerr << " where:\n";
168  cerr << " -g : graphics mode\n";
169  cerr << " -v : verbose mode";
170  cerr << endl;
171  return -1;
172  }
173  }
174 
175  TApplication* theApp = 0;
176  if ( showGraphics ) {
177  theApp = new TApplication("App",&argc,argv);
178 // plotFile = std::string(gSystem->TempDirectory())+std::string("/test-stdsort.pdf");
179  }
180 
181 
182  bool ok = stdsort();
183 
184  if ( showGraphics )
185  {
186  theApp->Run();
187  delete theApp;
188  theApp = 0;
189  }
190 
191  return (ok) ? 0 : 1;
192 }
virtual void SetLineWidth(Width_t lwidth)
Set the line width.
Definition: TAttLine.h:49
const int npass
Definition: testPermute.cxx:21
bool stdsort()
Definition: stdsort.cxx:91
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
bool showGraphics
Definition: stdsort.cxx:27
This class displays a legend box (TPaveText) containing several legend entries.
Definition: TLegend.h:27
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
const int maxsize
Definition: stdsort.cxx:23
Random number generator class based on the maximally quidistributed combined Tausworthe generator by ...
Definition: TRandom2.h:29
virtual void Draw(Option_t *option="")
Draw this legend with its current attributes.
Definition: TLegend.cxx:373
const int arraysize
Definition: stdsort.cxx:25
int Int_t
Definition: RtypesCore.h:41
virtual void SetTitle(const char *title="")
Set graph title.
Definition: TGraph.cxx:2176
STL namespace.
virtual void Draw(Option_t *chopt="")
Draw this graph with its current attributes.
Definition: TGraph.cxx:747
TLegend * legend
Definition: pirndm.C:35
void Stop()
Stop the stopwatch.
Definition: TStopwatch.cxx:77
const int increment
Definition: stdsort.cxx:24
virtual void Run(Bool_t retrn=kFALSE)
Main application eventloop. Calls system dependent eventloop via gSystem.
virtual UInt_t Integer(UInt_t imax)
Returns a random integer on [ 0, imax-1 ].
Definition: TRandom.cxx:320
void Sort(Index n, const Element *a, Index *index, Bool_t down=kTRUE)
Definition: TMath.h:989
void Error(const char *location, const char *msgfmt,...)
const int npass0
Definition: stdsort.cxx:20
virtual void SetLineColor(Color_t lcolor)
Set the line color.
Definition: TAttLine.h:46
const int maxint
Definition: stdsort.cxx:21
TRandom2 r(17)
virtual void SetMarkerStyle(Style_t mstyle=1)
Set the marker style.
Definition: TAttMarker.h:45
TAxis * GetYaxis()
Definition: TH1.h:325
The Canvas class.
Definition: TCanvas.h:41
TH1F * GetHistogram() const
Returns a pointer to the histogram used to draw the axis Takes into account the two following cases...
Definition: TGraph.cxx:1466
TLegendEntry * AddEntry(const TObject *obj, const char *label="", Option_t *option="lpf")
Add a new entry to this legend.
Definition: TLegend.cxx:280
int main(int argc, char **argv)
Definition: stdsort.cxx:152
The TH1 histogram class.
Definition: TH1.h:80
const int minsize
Definition: stdsort.cxx:22
Int_t Compare(const void *item1, const void *item2)
A Graph is a graphics object made of two arrays X and Y with npoints each.
Definition: TGraph.h:53
bool verbose
Definition: stdsort.cxx:28
void Show()
Definition: TCanvas.h:221
This class creates the ROOT Application Environment that interfaces to the windowing system eventloop...
Definition: TApplication.h:45
virtual void SetTitle(const char *title)
Change (i.e.
Definition: TH1.cxx:6027
const Bool_t kTRUE
Definition: Rtypes.h:91
virtual void SetTitle(const char *title="")
Set the title of the TNamed.
Definition: TNamed.cxx:155
const Int_t n
Definition: legend1.C:16
TAxis * GetXaxis()
Definition: TH1.h:324
Stopwatch class.
Definition: TStopwatch.h:30
bool testSort(const int n, double *tTMath, double *tStd)
Definition: stdsort.cxx:43