r605:f53d641aa967
Fri, 27 Mar 2009 18:49:25
[Not Reviewed]
0 comments (0 inline)
0
2
0
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2009 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/counter.h> |
| 20 | 20 |
#include <vector> |
| 21 |
#include <sstream> |
|
| 22 |
|
|
| 23 |
#include "test/test_tools.h" |
|
| 21 | 24 |
|
| 22 | 25 |
using namespace lemon; |
| 23 | 26 |
|
| 24 | 27 |
template <typename T> |
| 25 | 28 |
void bubbleSort(std::vector<T>& v) {
|
| 26 |
Counter op("Bubble Sort - Operations: ");
|
|
| 27 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 28 |
Counter::NoSubCounter co(op, "Comparisons: "); |
|
| 29 |
for (int i = v.size()-1; i > 0; --i) {
|
|
| 30 |
for (int j = 0; j < i; ++j) {
|
|
| 31 |
if (v[j] > v[j+1]) {
|
|
| 32 |
T tmp = v[j]; |
|
| 33 |
v[j] = v[j+1]; |
|
| 34 |
v[j+1] = tmp; |
|
| 35 |
as += 3; |
|
| 29 |
std::stringstream s1, s2, s3; |
|
| 30 |
{
|
|
| 31 |
Counter op("Bubble Sort - Operations: ", s1);
|
|
| 32 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 33 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 34 |
for (int i = v.size()-1; i > 0; --i) {
|
|
| 35 |
for (int j = 0; j < i; ++j) {
|
|
| 36 |
if (v[j] > v[j+1]) {
|
|
| 37 |
T tmp = v[j]; |
|
| 38 |
v[j] = v[j+1]; |
|
| 39 |
v[j+1] = tmp; |
|
| 40 |
as += 3; |
|
| 41 |
} |
|
| 42 |
++co; |
|
| 36 | 43 |
} |
| 37 |
++co; |
|
| 38 | 44 |
} |
| 39 | 45 |
} |
| 46 |
check(s1.str() == "Bubble Sort - Operations: 102\n", "Wrong counter"); |
|
| 47 |
check(s2.str() == "Assignments: 57\n", "Wrong subcounter"); |
|
| 48 |
check(s3.str() == "Comparisons: 45\n", "Wrong subcounter"); |
|
| 40 | 49 |
} |
| 41 | 50 |
|
| 42 | 51 |
template <typename T> |
| 43 | 52 |
void insertionSort(std::vector<T>& v) {
|
| 44 |
Counter op("Insertion Sort - Operations: ");
|
|
| 45 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 46 |
Counter::NoSubCounter co(op, "Comparisons: "); |
|
| 47 |
for (int i = 1; i < int(v.size()); ++i) {
|
|
| 48 |
T value = v[i]; |
|
| 49 |
++as; |
|
| 50 |
int j = i; |
|
| 51 |
while (j > 0 && v[j-1] > value) {
|
|
| 52 |
v[j] = v[j-1]; |
|
| 53 |
--j; |
|
| 54 |
|
|
| 53 |
std::stringstream s1, s2, s3; |
|
| 54 |
{
|
|
| 55 |
Counter op("Insertion Sort - Operations: ", s1);
|
|
| 56 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 57 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 58 |
for (int i = 1; i < int(v.size()); ++i) {
|
|
| 59 |
T value = v[i]; |
|
| 60 |
++as; |
|
| 61 |
int j = i; |
|
| 62 |
while (j > 0 && v[j-1] > value) {
|
|
| 63 |
v[j] = v[j-1]; |
|
| 64 |
--j; |
|
| 65 |
++co; ++as; |
|
| 66 |
} |
|
| 67 |
v[j] = value; |
|
| 68 |
++as; |
|
| 55 | 69 |
} |
| 56 |
v[j] = value; |
|
| 57 |
++as; |
|
| 58 | 70 |
} |
| 71 |
check(s1.str() == "Insertion Sort - Operations: 56\n", "Wrong counter"); |
|
| 72 |
check(s2.str() == "Assignments: 37\n", "Wrong subcounter"); |
|
| 73 |
check(s3.str() == "Comparisons: 19\n", "Wrong subcounter"); |
|
| 59 | 74 |
} |
| 60 | 75 |
|
| 61 | 76 |
template <typename MyCounter> |
| 62 |
void counterTest() {
|
|
| 63 |
MyCounter c("Main Counter: ");
|
|
| 64 |
c++; |
|
| 65 |
typename MyCounter::SubCounter d(c, "SubCounter: "); |
|
| 66 |
d++; |
|
| 67 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: "); |
|
| 68 |
e++; |
|
| 69 |
d+=3; |
|
| 70 |
c-=4; |
|
| 71 |
e-=2; |
|
| 72 |
c.reset(2); |
|
| 73 |
c.reset(); |
|
| 77 |
void counterTest(bool output) {
|
|
| 78 |
std::stringstream s1, s2, s3; |
|
| 79 |
{
|
|
| 80 |
MyCounter c("Main Counter: ", s1);
|
|
| 81 |
c++; |
|
| 82 |
typename MyCounter::SubCounter d(c, "SubCounter: ", s2); |
|
| 83 |
d++; |
|
| 84 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ", s3); |
|
| 85 |
e++; |
|
| 86 |
d+=3; |
|
| 87 |
c-=4; |
|
| 88 |
e-=2; |
|
| 89 |
c.reset(2); |
|
| 90 |
c.reset(); |
|
| 91 |
} |
|
| 92 |
if (output) {
|
|
| 93 |
check(s1.str() == "Main Counter: 3\n", "Wrong Counter"); |
|
| 94 |
check(s2.str() == "SubCounter: 3\n", "Wrong SubCounter"); |
|
| 95 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 96 |
} else {
|
|
| 97 |
check(s1.str() == "", "Wrong NoCounter"); |
|
| 98 |
check(s2.str() == "", "Wrong SubCounter"); |
|
| 99 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 100 |
} |
|
| 74 | 101 |
} |
| 75 | 102 |
|
| 76 | 103 |
void init(std::vector<int>& v) {
|
| 77 | 104 |
v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; |
| 78 | 105 |
v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; |
| 79 | 106 |
} |
| 80 | 107 |
|
| 81 | 108 |
int main() |
| 82 | 109 |
{
|
| 83 |
counterTest<Counter>(); |
|
| 84 |
counterTest<NoCounter>(); |
|
| 110 |
counterTest<Counter>(true); |
|
| 111 |
counterTest<NoCounter>(false); |
|
| 85 | 112 |
|
| 86 | 113 |
std::vector<int> x(10); |
| 87 | 114 |
init(x); bubbleSort(x); |
| 88 | 115 |
init(x); insertionSort(x); |
| 89 | 116 |
|
| 90 | 117 |
return 0; |
| 91 | 118 |
} |
| ... | ... |
@@ -18,41 +18,39 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/time_measure.h> |
| 20 | 20 |
|
| 21 | 21 |
using namespace lemon; |
| 22 | 22 |
|
| 23 | 23 |
void f() |
| 24 | 24 |
{
|
| 25 | 25 |
double d=0; |
| 26 | 26 |
for(int i=0;i<1000;i++) |
| 27 | 27 |
d+=0.1; |
| 28 | 28 |
} |
| 29 | 29 |
|
| 30 | 30 |
void g() |
| 31 | 31 |
{
|
| 32 | 32 |
static Timer T; |
| 33 | 33 |
|
| 34 | 34 |
for(int i=0;i<1000;i++) |
| 35 | 35 |
TimeStamp x(T); |
| 36 | 36 |
} |
| 37 | 37 |
|
| 38 | 38 |
int main() |
| 39 | 39 |
{
|
| 40 | 40 |
Timer T; |
| 41 | 41 |
unsigned int n; |
| 42 |
for(n=0;T.realTime()< |
|
| 42 |
for(n=0;T.realTime()<0.1;n++) ; |
|
| 43 | 43 |
std::cout << T << " (" << n << " time queries)\n";
|
| 44 |
T.restart(); |
|
| 45 |
while(T.realTime()<2.0) ; |
|
| 46 |
|
|
| 44 |
|
|
| 47 | 45 |
TimeStamp full; |
| 48 | 46 |
TimeStamp t; |
| 49 |
t=runningTimeTest(f,1,&n,&full); |
|
| 47 |
t=runningTimeTest(f,0.1,&n,&full); |
|
| 50 | 48 |
std::cout << t << " (" << n << " tests)\n";
|
| 51 | 49 |
std::cout << "Total: " << full << "\n"; |
| 52 | 50 |
|
| 53 |
t=runningTimeTest(g,1,&n,&full); |
|
| 51 |
t=runningTimeTest(g,0.1,&n,&full); |
|
| 54 | 52 |
std::cout << t << " (" << n << " tests)\n";
|
| 55 | 53 |
std::cout << "Total: " << full << "\n"; |
| 56 | 54 |
|
| 57 | 55 |
return 0; |
| 58 | 56 |
} |
0 comments (0 inline)