From db0fe313ef1827a5305e1ec33a67dfe18e8afd40 Mon Sep 17 00:00:00 2001 From: APTX Date: Wed, 1 Dec 2010 16:20:53 +0100 Subject: [PATCH] Add performance measurements. --- shared/shared.h | 46 ++++++++++ tal-algorithm/main.cpp | 151 +++++++++++++++++++++----------- tal-algorithm/tal-algorithm.pro | 3 + 3 files changed, 150 insertions(+), 50 deletions(-) diff --git a/shared/shared.h b/shared/shared.h index 5770224..08a2885 100644 --- a/shared/shared.h +++ b/shared/shared.h @@ -21,3 +21,49 @@ inline int max(int a, int b) { return a ^ ((a ^ b) & -(a < b)); } + +#define START_ALLOC int memory = 0, maxmemory = 0; + +#define ALLOC(type, count) memory += (count) * sizeof(int); maxmemory = max(memory, maxmemory); +#define DEALLOC(type, count) memory -= (count) * sizeof(int); +#define FINISH_ALLOC if (memory != 0) cerr << "Not all memory has been freed!" << endl; + +#if defined(HAVE_WINDOWS) +# include + +# define START_CPU \ + LARGE_INTEGER starttime; \ + { \ + BOOL s = QueryPerformanceCounter(&starttime); \ + if (!s) cerr << "Failed to obtain performance counter data!" << endl; \ + } starttime; + +# define STOP_CPU \ + LARGE_INTEGER endtime; \ + LARGE_INTEGER frequency; \ + { \ + BOOL s = QueryPerformanceCounter(&endtime); \ + if (!s) cerr << "Failed to obtain performance counter data!" << endl; \ + s = QueryPerformanceFrequency(&frequency);\ + if (!s) cerr << "Failed to obtain performance frequency data!" << endl; \ + } endtime; + +# define CPU_ELAPSED (double(endtime.QuadPart - starttime.QuadPart) / double(frequency.QuadPart) * 1000) + +#elif defined(HAVE_UNIX) +# include + +# define START_CPU \ + timeval starttime; \ + gettimeofday(&starttime, NULL);starttime; + +# define STOP_CPU \ + timeval endtime; \ + gettimeofday(&endtime, NULL);endtime; + +# define CPU_ELAPSED (double(endtime.tv_sec - starttime.tv_sec) * 1000 + double(endtime.tv_usec - starttime.tv_usec) / 1000) +#else +# define START_CPU ; +# define STOP_CPU ; +# define CPU_ELAPSED -1 +#endif diff --git a/tal-algorithm/main.cpp b/tal-algorithm/main.cpp index a810a2c..4a35e61 100644 --- a/tal-algorithm/main.cpp +++ b/tal-algorithm/main.cpp @@ -142,45 +142,71 @@ ostream &operator<<(ostream &o, const Problem &p) void solve_dp(Problem * p) { - Array2d V(p->count + 1, p->limit + 1); + START_ALLOC; -/* - // Initialized in Array2d constructor - for (int w = 0; w <= p->limit; ++w) - { - V(0, w) = 0; - } -*/ - for (int k = 0; k < p->count; ++k) + ALLOC(Array2d, 1); + ALLOC(int, (p->count + 1) * (p->limit + 1)); + + START_CPU; { - V(k + 1, 0) = 0; - for (int w = 1; w <= p->limit; ++w) + Array2d V(p->count + 1, p->limit + 1); + +/* + // Initialized in Array2d constructor + for (int w = 0; w <= p->limit; ++w) { - if (p->items[k].weight > w) - V(k + 1, w) = V(k, w); - else - V(k + 1, w) = max(V(k, w), p->items[k].value + V(k, w - p->items[k].weight)); + V(0, w) = 0; } - } - - int w = p->limit; - int totalWeight = 0; - for (int i = p->count; i > 0; --i) - { - if (V(i, w) == V(i - 1, w)) +*/ + ALLOC(int, 2); { - p->items[i - 1].solution = false; + int k, w; + for (k = 0; k < p->count; ++k) + { + V(k + 1, 0) = 0; + for (w = 1; w <= p->limit; ++w) + { + if (p->items[k].weight > w) + V(k + 1, w) = V(k, w); + else + V(k + 1, w) = max(V(k, w), p->items[k].value + V(k, w - p->items[k].weight)); + } + } } - else + DEALLOC(int, 2); + + ALLOC(int, 1); + int tempLimit = p->limit; + p->totalWeight = 0; + + ALLOC(int, 1); + for (int i = p->count; i > 0; --i) { - p->items[i - 1].solution = true; - w -= p->items[i - 1].weight; - totalWeight += p->items[i - 1].weight; + if (V(i, tempLimit) == V(i - 1, tempLimit)) + { + p->items[i - 1].solution = false; + } + else + { + p->items[i - 1].solution = true; + tempLimit -= p->items[i - 1].weight; + p->totalWeight += p->items[i - 1].weight; + } } + p->solved = true; + p->totalValue = V(p->count, p->limit); } - p->solved = true; - p->totalValue = V(p->count, p->limit); - p->totalWeight = totalWeight; + STOP_CPU; + + DEALLOC(int, 1); + DEALLOC(int, 1); + DEALLOC(int, (p->count + 1) * (p->limit + 1)); + DEALLOC(Array2d, 1); + + FINISH_ALLOC; + + cerr << "dp\tcpu\t" << setw(20) << CPU_ELAPSED << "\tms" << endl; + cerr << "dp\tmem\t" << setw(20) << maxmemory << "\tbytes" << endl; } // =============================================================================== @@ -204,28 +230,50 @@ bool greed_BestRatio(const Item &a, const Item &b) void solve_greedy(Problem *p, bool (*greed_func)(const Item &a, const Item &b)) { - sort(p->items, p->items + p->count, greed_func); + START_ALLOC; + START_CPU; + { + sort(p->items, p->items + p->count, greed_func); - int totalWeight = 0; - int totalValue = 0; - for (int i = 0; i < p->count; ++i) - { - if (p->items[i].weight + totalWeight <= p->limit) - { - totalWeight += p->items[i].weight; - totalValue += p->items[i].value; - p->items[i].solution = true; - } - else + p->totalWeight = 0; + p->totalValue = 0; + + ALLOC(int, 1); + for (int i = 0; i < p->count; ++i) { - p->items[i].solution = false; + if (p->items[i].weight + p->totalWeight <= p->limit) + { + p->totalWeight += p->items[i].weight; + p->totalValue += p->items[i].value; + p->items[i].solution = true; + } + else + { + p->items[i].solution = false; + } } + DEALLOC(int, 1); + + p->solved = true; } - p->solved = true; - p->totalWeight = totalWeight; - p->totalValue = totalValue; + STOP_CPU; + + if (greed_func == greed_HighestValue) + cerr << "gv\tcpu\t" << setw(20) << CPU_ELAPSED << "\tms" << endl; + else if (greed_func == greed_LowestWeight) + cerr << "gw\tcpu\t" << setw(20) << CPU_ELAPSED << "\tms" << endl; + else if (greed_func == greed_BestRatio) + cerr << "gr\tcpu\t" << setw(20) << CPU_ELAPSED << "\tms" << endl; + + FINISH_ALLOC; + if (greed_func == greed_HighestValue) + cerr << "gv\tmem\t" << setw(20) << maxmemory << "\tbytes" << endl; + else if (greed_func == greed_LowestWeight) + cerr << "gw\tmem\t" << setw(20) << maxmemory << "\tbytes" << endl; + else if (greed_func == greed_BestRatio) + cerr << "gr\tmem\t" << setw(20) << maxmemory << "\tbytes" << endl; } // =============================================================================== @@ -321,28 +369,31 @@ int main(int argc, char **argv) goto help; } cout << *p; + + bool printSolutions = true; for (int i = 0; i < runs; ++i) { if (run_dp) { solve_dp(p); - cout << "dp\t" << p->totalValue << "\t" << p->totalWeight << endl; + if(printSolutions) cout << "dp\tresult\t" << p->totalValue << "\t" << p->totalWeight << endl; } if (run_greedy_HighestValue) { solve_greedy(p, greed_HighestValue); - cout << "gv\t" << p->totalValue << "\t" << p->totalWeight << endl; + if(printSolutions) cout << "gv\tresult\t" << p->totalValue << "\t" << p->totalWeight << endl; } if (run_greedy_LowestWeight) { solve_greedy(p, greed_LowestWeight); - cout << "gw\t" << p->totalValue << "\t" << p->totalWeight << endl; + if(printSolutions) cout << "gw\tresult\t" << p->totalValue << "\t" << p->totalWeight << endl; } if (run_greedy_BestRatio) { solve_greedy(p, greed_BestRatio); - cout << "gr\t" << p->totalValue << "\t" << p->totalWeight << endl; + if(printSolutions) cout << "gr\tresult\t" << p->totalValue << "\t" << p->totalWeight << endl; } + printSolutions = false; } delete p; diff --git a/tal-algorithm/tal-algorithm.pro b/tal-algorithm/tal-algorithm.pro index 405bb61..7cc016c 100644 --- a/tal-algorithm/tal-algorithm.pro +++ b/tal-algorithm/tal-algorithm.pro @@ -5,3 +5,6 @@ SOURCES += \ main.cpp HEADERS += \ ../shared/shared.h + +win32:DEFINES += HAVE_WINDOWS +unix:DEFINES += HAVE_UNIX -- 2.52.0