Logo ROOT   6.10/09
Reference Guide
testPermute.cxx
Go to the documentation of this file.
1 #include <iostream>
2 #include <ctime>
3 #include <algorithm>
4 #include <vector>
5 
6 #include <gsl/gsl_permutation.h>
7 
8 #include <TRandom2.h>
9 #include <TMath.h>
10 #include <TStopwatch.h>
11 
12 #include <TApplication.h>
13 #include <TCanvas.h>
14 #include <TH2F.h>
15 #include <TGraph.h>
16 #include <TLegend.h>
17 #include <TAxis.h>
18 
19 bool showGraphics = false;
20 
21 const int npass = 2;
22 const int minsize = 5;
23 const int maxsize = 12;
24 const int maxint = 5000;
25 const int arraysize = (maxsize-minsize) + 1;
26 
27 using namespace std;
28 
29  ostream& operator <<(ostream& os, const vector<Int_t>& v)
30 {
31  os << "[ ";
32  for ( vector<Int_t>::const_iterator i = v.begin(); i != v.end() ; ++i) {
33  os << *i << ' ';
34  }
35  os << ']';
36 
37  return os;
38 }
39 
40 void initArray(Int_t n, vector<Int_t>& array)
41 {
42  TRandom2 r( time( 0 ) );
43  for ( Int_t i = 0; i < n; i++) {
44  array[i] = r.Integer( maxint );
45  }
46  sort(array.begin(), array.end());
47 }
48 
50 {
51  const Int_t n = minsize;
52 
53  vector<Int_t> original(n);
54  vector<Int_t> vM(n);
55  vector<Int_t> vS(n);
56 
57  bool equals = true;
58 
59  initArray(n, original);
60 
61  // TMATH
62  copy(original.begin(), original.end(), vM.begin());
63  copy(original.begin(), original.end(), vS.begin());
64  //cout << original << vM << vS << endl;
65 
66  while ( TMath::Permute(n, &vM[0]) ) {
67  std::next_permutation(&vS[0], &vS[n]);
68  //cout << vM << vS << endl;
69  equals &= equal(vM.begin(), vM.end(), vS.begin());
70  }
71 
72  TMath::Permute(n, &vM[0]);
73  std::next_permutation(vS.begin(), vS.end());
74  //cout << "kFALSE: " << vM << vS << endl;
75 
76  return equals;
77 }
78 
79 void permuteTime(const int n, double* tTMath, double* tStd)
80 {
81  vector<Int_t> original(n);
82  vector<Int_t> v(n);
83 
84  TStopwatch t;
85 
86  initArray(n, original);
87 
88  // TMATH
89  t.Start();
90  for (int j = 0; j < npass; ++j) {
91  copy(original.begin(), original.end(), v.begin());
92  while ( TMath::Permute(n, &v[0]) ) {}
93  }
94  t.Stop();
95  *tTMath = t.RealTime();
96  cout << "TMath::Permute time :\t " << t.RealTime();
97 
98  // STD
99  t.Start();
100  for (int j = 0; j < npass; ++j) {
101  copy(original.begin(), original.end(), v.begin());
102  while ( std::next_permutation(&v[0], &v[n]) ) {}
103  }
104  t.Stop();
105  *tStd = t.RealTime();
106  cout << " std::next_permutation time :\t " << t.RealTime();
107 }
108 
109 void testGSLPermute(Int_t n, double* tGSL)
110 {
111  TStopwatch t;
112 
113  gsl_permutation *original = gsl_permutation_alloc(n);
114  gsl_permutation *p = gsl_permutation_alloc(n);
115 
116  gsl_permutation_init(original);
117 
118  t.Start();
119  for (int j = 0; j < npass; ++j) {
120  gsl_permutation_memcpy(p, original);
121  while ( gsl_permutation_next(p) == GSL_SUCCESS )
122  {
123 // gsl_permutation_fprintf(stdout, p, " %u");
124 // fprintf(stdout, "\n");
125  }
126  }
127  t.Stop();
128  *tGSL = t.RealTime();
129  cout << " gsl_permutation_next time :\t " << t.RealTime();
130 
131  gsl_permutation_free(p);
132  gsl_permutation_free(original);
133 }
134 
136 {
137  int status = 0;
138  bool equals;
139 
140  vector<double> tM( arraysize );
141  vector<double> tS( arraysize );
142  vector<double> tG( arraysize );
143  vector<double> index( arraysize );
144 
145  equals = checkPermute();
146 
147  cout << "checkPermute()...."
148  << (equals? "OK" : "FAILED")
149  << endl;
150 
151  status += (equals == false);
152 
153  for ( int i = minsize; i <= maxsize; i += 1)
154  {
155  permuteTime(i, &tM[ i - minsize ], &tS[ i -minsize ]);
156  testGSLPermute(i, &tG[ i - minsize ]);
157  index[ i - minsize ] = i;
158  cout << endl;
159  }
160 
161  for ( int i = minsize; i <= maxsize; i += 1)
162  cout << tM[ i - minsize ] << ' ' << tS[ i - minsize ] << ' ' << tG[ i - minsize ] << endl;
163 
164  if ( showGraphics )
165  {
166  TCanvas* c1 = new TCanvas("c1", "Comparision of Permutation Time", 600, 400);
167  TH2F* hpx = new TH2F("hpx", "Comparision of Permutation Time", arraysize, minsize, maxsize, arraysize, tM[0],tS[arraysize-1]);
168  hpx->SetStats(kFALSE);
169  hpx->Draw();
170 
171  TGraph* gM = new TGraph(arraysize, &index[0], &tM[0]);
172  gM->SetLineColor(2);
173  gM->SetLineWidth(3);
174  gM->SetTitle("TMath::Permute()");
175  gM->Draw("SAME");
176 
177  TGraph* gS = new TGraph(arraysize, &index[0], &tS[0]);
178  gS->SetLineColor(3);
179  gS->SetLineWidth(3);
180  gS->SetTitle("std::next_permutation()");
181  gS->Draw("SAME");
182 
183  TGraph* gG = new TGraph(arraysize, &index[0], &tG[0]);
184  gG->SetLineColor(4);
185  gG->SetLineWidth(3);
186  gG->SetTitle("gsl_permutation_next()");
187  gG->Draw("SAME");
188 
189  TLegend* legend = new TLegend(0.15,0.72,0.4,0.86);
190  legend->AddEntry(gM, "TMath::Permute()");
191  legend->AddEntry(gS, "std::next_permutation()");
192  legend->AddEntry(gG, "gsl_permutation_next()");
193  legend->Draw();
194 
195  hpx->GetXaxis()->SetTitle("Array Size");
196  hpx->GetYaxis()->SetTitle("Time");
197 
198 
199  c1->Show();
200  }
201 
202  cout << "Test Done!" << endl;
203 
204  return status;
205 }
206 
207 int main(int argc, char **argv)
208 {
209  int status = 0;
210 
211  // Parse command line arguments
212  for (Int_t i=1 ; i<argc ; i++) {
213  std::string arg = argv[i] ;
214  if (arg == "-g") {
215  showGraphics = true;
216  }
217  if (arg == "-v") {
218  showGraphics = true;
219  //verbose = true;
220  }
221  if (arg == "-h") {
222  cerr << "Usage: " << argv[0] << " [-g] [-v]\n";
223  cerr << " where:\n";
224  cerr << " -g : graphics mode\n";
225  cerr << " -v : verbose mode";
226  cerr << endl;
227  return -1;
228  }
229  }
230 
231  TApplication* theApp = 0;
232 
233  if ( showGraphics )
234  theApp = new TApplication("App",&argc,argv);
235 
236 
237  status += testPermute();
238 
239  if ( showGraphics )
240  {
241  theApp->Run();
242  delete theApp;
243  theApp = 0;
244  }
245 
246  return status;
247 }
virtual void SetLineWidth(Width_t lwidth)
Set the line width.
Definition: TAttLine.h:43
const int npass
Definition: testPermute.cxx:21
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
bool showGraphics
Definition: testPermute.cxx:19
return c1
Definition: legend1.C:41
bool equal(double d1, double d2, double stol=10000)
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
int Int_t
Definition: RtypesCore.h:41
virtual void SetTitle(const char *title="")
Set graph title.
Definition: TGraph.cxx:2180
int equals(Double_t n1, Double_t n2, double ERRORLIMIT=1.E-10)
Definition: UnitTesting.cxx:24
STL namespace.
void permuteTime(const int n, double *tTMath, double *tStd)
Definition: testPermute.cxx:79
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.
virtual UInt_t Integer(UInt_t imax)
Returns a random integer on [ 0, imax-1 ].
Definition: TRandom.cxx:320
virtual void SetLineColor(Color_t lcolor)
Set the line color.
Definition: TAttLine.h:40
const int maxsize
Definition: testPermute.cxx:23
void initArray(Int_t n, vector< Int_t > &array)
Definition: testPermute.cxx:40
TRandom2 r(17)
virtual void Draw(Option_t *option="")
Draw this histogram with options.
Definition: TH1.cxx:2851
const int arraysize
Definition: testPermute.cxx:25
SVector< double, 2 > v
Definition: Dict.h:5
int testPermute()
tomato 2-D histogram with a float per channel (see TH1 documentation)}
Definition: TH2.h:249
Bool_t Permute(Int_t n, Int_t *a)
Simple recursive algorithm to find the permutations of n natural numbers, not necessarily all distinc...
Definition: TMath.cxx:2503
const int maxint
Definition: testPermute.cxx:24
bool checkPermute()
Definition: testPermute.cxx:49
const int minsize
Definition: testPermute.cxx:22
TAxis * GetYaxis()
Definition: TH1.h:301
const Bool_t kFALSE
Definition: RtypesCore.h:92
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
void testGSLPermute(Int_t n, double *tGSL)
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
int main(int argc, char **argv)
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
THist< 2, float, THistStatContent, THistStatUncertainty > TH2F
Definition: THist.hxx:317
const Int_t n
Definition: legend1.C:16
virtual void SetStats(Bool_t stats=kTRUE)
Set statistics option on/off.
Definition: TH1.cxx:8103
TAxis * GetXaxis()
Definition: TH1.h:300
Stopwatch class.
Definition: TStopwatch.h:28