00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #include <iostream>
00040 #include <iomanip>
00041
00042 #include <ctime>
00043 #include <cmath>
00044
00045 namespace {
00046
00051 class FailTimeStop : public Search::Stop {
00052 private:
00053 Search::TimeStop *ts;
00054 Search::FailStop *fs;
00055
00056 FailTimeStop(int fails, int time) {
00057 ts = new Search::TimeStop(time);
00058 fs = new Search::FailStop(fails);
00059 }
00060 public:
00062 virtual bool stop(const Search::Statistics& s) {
00063 return fs->stop(s) || ts->stop(s);
00064 }
00066 static Search::Stop* create(unsigned int fail, unsigned int time) {
00067 if ((fail == 0) && (time == 0))
00068 return NULL;
00069 if (fail == 0)
00070 return new Search::TimeStop(time);
00071 if (time == 0)
00072 return new Search::FailStop(fail);
00073 return new FailTimeStop(fail,time);
00074 }
00075 };
00076
00078 class Timer {
00079 private:
00080 clock_t t0;
00081 public:
00083 void start(void) {
00084 t0 = clock();
00085 }
00087 double stop(void) {
00088 return (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
00089 }
00091 void stop(std::ostream& os) {
00092 double t = stop();
00093 double sec = floor(t / 1000.0);
00094 int o_msec = static_cast<int>(t - 1000.0*sec);
00095 double min = floor(sec / 60.0);
00096 int o_sec = static_cast<int>(sec - 60.0*min);
00097 double hour = floor(min / 60.0);
00098 int o_min = static_cast<int>(min - 60.0*hour);
00099 double day = floor(hour / 24.0);
00100 int o_hour = static_cast<int>(hour - 24.0*day);
00101 int o_day = static_cast<int>(day);
00102 if (o_day)
00103 os << o_day << " days, ";
00104 if (o_hour)
00105 os << o_hour << ":";
00106 if (o_min) {
00107 if (o_hour) {
00108 os.width(2); os.fill('0');
00109 }
00110 os << o_min << ":";
00111 os.width(2); os.fill('0');
00112 }
00113 os << o_sec << ".";
00114 os.width(3); os.fill('0');
00115 os << o_msec
00116 << " ("
00117 << std::showpoint << std::fixed
00118 << std::setprecision(6) << t << " ms)";
00119 }
00120 };
00121
00122 }
00123
00124
00129 double
00130 am(double t[], int n);
00131
00136 double
00137 dev(double t[], int n);
00138
00139 #ifdef GECODE_HAS_GIST
00140
00144 template <class Engine>
00145 class GistEngine {
00146 };
00147
00149 template <typename S>
00150 class GistEngine<DFS<S> > {
00151 public:
00152 static void explore(S* root, Gist::Inspector* i) {
00153 (void) Gecode::explore(root, i);
00154 }
00155 };
00156
00158 template <typename S>
00159 class GistEngine<LDS<S> > {
00160 public:
00161 static void explore(S* root, Gist::Inspector* i) {
00162 (void) Gecode::explore(root, i);
00163 }
00164 };
00165
00167 template <typename S>
00168 class GistEngine<BAB<S> > {
00169 public:
00170 static void explore(S* root, Gist::Inspector* i) {
00171 (void) exploreBest(root, i);
00172 }
00173 };
00174
00176 template <typename S>
00177 class GistEngine<Restart<S> > {
00178 public:
00179 static void explore(S* root, Gist::Inspector* i) {
00180 (void) exploreBest(root, i);
00181 }
00182 };
00183
00184 #endif
00185
00186 template <class Script, template<class> class Engine, class Options>
00187 void
00188 Example::run(const Options& o) {
00189 using namespace std;
00190 try {
00191 switch (o.mode()) {
00192 case EM_SOLUTION:
00193 {
00194 cout << o.name() << endl;
00195 Timer t;
00196 int i = o.solutions();
00197 t.start();
00198 Script* s = new Script(o);
00199 unsigned int n_p = s->propagators();
00200 unsigned int n_b = s->branchings();
00201 unsigned long int p = 0;
00202 if (o.sac() != SAC_NONE) {
00203 s->sac_collect_vars();
00204 while (s->sac(p) && o.sac() == SAC_FULL) {}
00205 s->sac_remove_vars();
00206 }
00207 Search::Options so;
00208 so.c_d = o.c_d();
00209 so.a_d = o.a_d();
00210 so.stop = FailTimeStop::create(o.fail(), o.time());
00211 Engine<Script> e(s,so);
00212 delete s;
00213 do {
00214 Example* ex = e.next();
00215 if (ex == NULL)
00216 break;
00217 ex->print(std::cout);
00218 delete ex;
00219 } while (--i != 0);
00220 Search::Statistics stat = e.statistics();
00221 cout << endl;
00222 cout << "Initial" << endl
00223 << "\tpropagators: " << n_p << endl
00224 << "\tbranchings: " << n_b << endl
00225 << endl
00226 << "Summary" << endl
00227 << "\truntime: ";
00228 t.stop(cout);
00229 cout << endl
00230 << "\tsolutions: "
00231 << abs(static_cast<int>(o.solutions()) - i) << endl
00232 << "\tpropagations: " << p+stat.propagate << endl
00233 << "\tfailures: " << stat.fail << endl
00234 << "\tclones: " << stat.clone << endl
00235 << "\tcommits: " << stat.commit << endl
00236 << "\tpeak memory: "
00237 << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00238 << endl;
00239 }
00240 break;
00241 case EM_STAT:
00242 {
00243 cout << o.name() << endl;
00244 int i = o.solutions();
00245 Script* s = new Script(o);
00246 unsigned int n_p = s->propagators();
00247 unsigned int n_b = s->branchings();
00248 unsigned long int p = 0;
00249 if (o.sac() != SAC_NONE) {
00250 s->sac_collect_vars();
00251 while (s->sac(p) && o.sac() == SAC_FULL) {}
00252 s->sac_remove_vars();
00253 }
00254 Search::Options so;
00255 so.c_d = o.c_d();
00256 so.a_d = o.a_d();
00257 Engine<Script> e(s,so);
00258 delete s;
00259 do {
00260 Example* ex = e.next();
00261 if (ex == NULL)
00262 break;
00263 delete ex;
00264 } while (--i != 0);
00265 Search::Statistics stat = e.statistics();
00266 cout << endl
00267 << "\tpropagators: " << n_p << endl
00268 << "\tbranchings: " << n_b << endl
00269 << "\tsolutions: "
00270 << abs(static_cast<int>(o.solutions()) - i) << endl
00271 << "\tpropagations: " << p+stat.propagate << endl
00272 << "\tfailures: " << stat.fail << endl
00273 << "\tclones: " << stat.clone << endl
00274 << "\tcommits: " << stat.commit << endl
00275 << "\tpeak memory: "
00276 << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00277 << endl;
00278 }
00279 break;
00280 case EM_TIME:
00281 {
00282 cout << o.name() << endl;
00283 Timer t;
00284 GECODE_AUTOARRAY(double,ts,o.samples());
00285 for (unsigned int s = o.samples(); s--; ) {
00286 t.start();
00287 for (unsigned int k = o.iterations(); k--; ) {
00288 unsigned int i = o.solutions();
00289 Script* s = new Script(o);
00290 if (o.sac() != SAC_NONE) {
00291 unsigned long int p;
00292 s->sac_collect_vars();
00293 while (s->sac(p) && o.sac() == SAC_FULL) {}
00294 s->sac_remove_vars();
00295 }
00296 Search::Options so;
00297 so.c_d = o.c_d();
00298 so.a_d = o.a_d();
00299 Engine<Script> e(s,so);
00300 delete s;
00301 do {
00302 Example* ex = e.next();
00303 if (ex == NULL)
00304 break;
00305 delete ex;
00306 } while (--i != 0);
00307 }
00308 ts[s] = t.stop() / o.iterations();
00309 }
00310 double m = am(ts,o.samples());
00311 double d = dev(ts,o.samples()) * 100.0;
00312 cout << "\tRuntime: "
00313 << setw(20) << right
00314 << showpoint << fixed
00315 << setprecision(6) << m << "ms"
00316 << setprecision(2) << " (" << d << "% deviation)"
00317 << endl;
00318 }
00319 break;
00320 #ifdef GECODE_HAS_GIST
00321 case EM_GIST:
00322 {
00323 Gist::PrintingInspector<Script> pi(o.name());
00324 Script* s = new Script(o);
00325 (void) GistEngine<Engine<Script> >::explore(s, &pi);
00326 delete s;
00327 }
00328 break;
00329 #endif
00330 }
00331 } catch (Exception e) {
00332 cout << "Exception: " << e.what() << "." << endl
00333 << "Stopping..." << endl;
00334 }
00335 }
00336
00337