Logo ROOT   6.10/09
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 namespace {
32 template<typename T>
33 struct Compare {
34 
35  Compare(const T * d) : fData(d) {}
36 
37  bool operator()(int i1, int i2) {
38  return fData[i1] > fData[i2];
39  }
40 
41  const T * fData;
42 };
43 }
44 
45 template <typename T> bool testSort(const int n, double* tTMath, double* tStd)
46 {
47 
48  std::cout << "Testing Sort of array - size n = " << n << "\t(Time / call in microsec.) " << std::endl;
49 
50  vector<T> k(n);
51 
52  vector<T> index(n);
53  vector<T> index2(n);
54  TStopwatch t;
55 
56  TRandom2 r( time( 0 ) );
57  for ( Int_t i = 0; i < n; i++) {
58  k[i] = (T) r.Integer( maxint );
59 // cout << k[i] << ' ' << endl;
60  }
61 
62  //int npass = npass0/std::log10(10*n/minsize);
63  int npass = npass0/(n/minsize);
64 
65  t.Start();
66  for (int j = 0; j < npass; ++j) {
67 // for(Int_t i = 0; i < n; i++) { index[i] = i; }
68  TMath::Sort(n,&k[0],&index[0],kTRUE);
69  }
70  t.Stop();
71  *tTMath = t.RealTime()/npass*1.E6;
72  cout << "TMath::Sort time :\t\t " << *tTMath << endl;
73 
74 
75  t.Start();
76  for (int j = 0; j < npass; ++j) {
77  for(Int_t i = 0; i < n; i++) { index2[i] = i; }
78  std::sort(&index2[0],&index2[0]+n, Compare<T>(&k[0]) );
79  }
80  t.Stop();
81  *tStd = t.RealTime()/npass*1.E6;
82  std::cout << "std::sort time (using indices):\t " << *tStd << std::endl;
83 
84  // test results
85  bool ok = true;
86  for(Int_t i = 0; i < n && ok; i++) {
87  ok &= (index[i] == index2[i]);
88  if (!ok) Error("test sort","Different values found at i= %d - index1 = %d - index2 = %d",i,index[i],index2[i]);
89  }
90  return ok;
91 }
92 
93 bool stdsort()
94 {
95  vector<double> tM( arraysize );
96  vector<double> tS( arraysize );
97  vector<double> index( arraysize );
98 
99  //cout << (maxsize-minsize)/10 + 1 << endl;
100 
101  bool ok = true;
102  int j = 0; int i = minsize;
103  while ( i <= maxsize && j < arraysize)
104  {
105  ok &= testSort<Int_t>(i, &tM[j], &tS[j]);
106  index[j] = i;
107  j++;
108  i *= increment;
109  }
110  int ntest = j;
111 
112  if (verbose) {
113  cout << " TMATH - time --- std time " << std::endl;
114  for ( i = 0; i < ntest; ++i) {
115  cout << " size = " << index[i] << " : " << tM[i] << ' ' << tS[i] << endl;
116  }
117  }
118 
119  if ( showGraphics )
120  {
121  TCanvas* c1 = new TCanvas("c1", "Comparision of Sorting Time", 600, 400);
122 
123  TGraph* gM = new TGraph(ntest, &index[0], &tM[0]);
124  gM->SetLineColor(2);
125  gM->SetLineWidth(3);
126  gM->SetMarkerStyle(20);
127  gM->SetTitle("TMath::Sort()");
128  gM->Draw("ALP");
129 
130  TGraph* gS = new TGraph(arraysize, &index[0], &tS[0]);
131  gS->SetLineColor(3);
132  gS->SetLineWidth(3);
133  gS->SetTitle("std::sort()");
134  gS->Draw("SAME");
135 
136  TLegend* legend = new TLegend(0.15,0.72,0.4,0.86);
137  legend->AddEntry(gM, "TMath::Sort()");
138  legend->AddEntry(gS, "std::sort()");
139  legend->Draw();
140 
141  TH1 * hpx = gM->GetHistogram();
142  hpx->GetXaxis()->SetTitle("Array Size");
143  hpx->GetYaxis()->SetTitle("Time");
144  hpx->SetTitle("Comparison of Sorting Time");
145 
146 
147  c1->Show();
148 
149  }
150 
151  return ok;
152 }
153 
154 int main(int argc, char **argv)
155 {
156 
157  // Parse command line arguments
158  for (Int_t i=1 ; i<argc ; i++) {
159  std::string arg = argv[i] ;
160  if (arg == "-g") {
161  showGraphics = true;
162  }
163  if (arg == "-v") {
164  showGraphics = true;
165  verbose = true;
166  }
167  if (arg == "-h") {
168  cerr << "Usage: " << argv[0] << " [-g] [-v]\n";
169  cerr << " where:\n";
170  cerr << " -g : graphics mode\n";
171  cerr << " -v : verbose mode";
172  cerr << endl;
173  return -1;
174  }
175  }
176 
177  TApplication* theApp = 0;
178  if ( showGraphics ) {
179  theApp = new TApplication("App",&argc,argv);
180 // plotFile = std::string(gSystem->TempDirectory())+std::string("/test-stdsort.pdf");
181  }
182 
183 
184  bool ok = stdsort();
185 
186  if ( showGraphics )
187  {
188  theApp->Run();
189  delete theApp;
190  theApp = 0;
191  }
192 
193  return (ok) ? 0 : 1;
194 }
virtual void SetLineWidth(Width_t lwidth)
Set the line width.
Definition: TAttLine.h:43
const int npass
Definition: testPermute.cxx:21
bool stdsort()
Definition: stdsort.cxx:93
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: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
const int maxsize
Definition: stdsort.cxx:23
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
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:2180
STL namespace.
TRObject operator()(const T1 &t1) const
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
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:1151
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:40
const int maxint
Definition: stdsort.cxx:21
TRandom2 r(17)
virtual void SetMarkerStyle(Style_t mstyle=1)
Set the marker style.
Definition: TAttMarker.h:40
TAxis * GetYaxis()
Definition: TH1.h:301
The Canvas class.
Definition: TCanvas.h:31
TH1F * GetHistogram() const
Returns a pointer to the histogram used to draw the axis Takes into account the two following cases...
Definition: TGraph.cxx:1469
TLegendEntry * AddEntry(const TObject *obj, const char *label="", Option_t *option="lpf")
Add a new entry to this legend.
Definition: TLegend.cxx:359
int main(int argc, char **argv)
Definition: stdsort.cxx:154
The TH1 histogram class.
Definition: TH1.h:56
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:41
bool verbose
Definition: stdsort.cxx:28
void Show()
Definition: TCanvas.h:212
This class creates the ROOT Application Environment that interfaces to the windowing system eventloop...
Definition: TApplication.h:39
virtual void SetTitle(const char *title)
Change (i.e.
Definition: TH1.cxx:6028
virtual void SetTitle(const char *title="")
Set the title of the TNamed.
Definition: TNamed.cxx:155
const Bool_t kTRUE
Definition: RtypesCore.h:91
const Int_t n
Definition: legend1.C:16
TAxis * GetXaxis()
Definition: TH1.h:300
Stopwatch class.
Definition: TStopwatch.h:28
bool testSort(const int n, double *tTMath, double *tStd)
Definition: stdsort.cxx:45