542/doc/perf_dlist_8cpp_source.html

00001 #include "stdinc.h"
00002 #include "UiDlist.h"
00003 #include "Util.h"
00004
00005 void perfTest(int n) {
00006         UiDlist lst(n);
00007         int perm[n+1];
00008         Util::genPerm(n,perm);
00009
00010         cout << "perfTest " << n << endl;
00011
00012         uint32_t t0 = Util::getTime();
00013         for (int i = 1; i <= n; i++) lst.addLast(i);
00014         uint32_t t1= Util::getTime();
00015         double addBack = ((double) t1 - (double) t0)/n;
00016         cout << "appending to end: " << addBack << " us per operation\n";
00017
00018         t0= Util::getTime();
00019         for (int i = 1; i <= n; i++) lst.removeFirst();
00020         t1= Util::getTime();
00021         double removeFront = ((double) t1 - (double) t0)/n;
00022         cout << "removing from front: " << removeFront << " us per operation\n";
00023
00024         t0 = Util::getTime();
00025         for (int i = 1; i <= n; i++) lst.addLast(perm[i]);
00026         t1= Util::getTime();
00027         double addBackRand = ((double) t1 - (double) t0)/n;
00028         cout << "appending to end in random order: " << addBack
00029              << " us per operation\n";
00030
00031         t0= Util::getTime();
00032         for (int i = 1; i <= n; i++) lst.removeFirst();
00033         t1= Util::getTime();
00034         removeFront = ((double) t1 - (double) t0)/n;
00035         cout << "removing from front: " << removeFront << " us per operation\n";
00036
00037         for (int i = 1; i <= n; i++) lst.addLast(perm[i]);
00038         t0= Util::getTime();
00039         for (int i = 1; i <= n; i++) lst.remove(i);
00040         t1= Util::getTime();
00041         double removeByValue = ((double) t1 - (double) t0)/n;
00042         cout << "removing by value: " << removeByValue << " us per operation\n";
00043
00044         for (int i = 1; i <= n; i++) lst.addFirst(i);
00045         int sum = 0;
00046         t0= Util::getTime();
00047         for (int i = lst.first(); i != 0; i = lst.next(i)) sum += i;
00048         t1= Util::getTime();
00049         double sumInOrder = ((double) t1 - (double) t0)/n;
00050         cout << "summing in order: " << sumInOrder << " us per operation "
00051              << sum << "\n";
00052
00053         if (n <= 10000) {
00054                 sum = 0;
00055                 t0= Util::getTime();
00056                 for (int i = 1; i <= n; i++) sum += lst.get(perm[i]);
00057                 t1= Util::getTime();
00058                 double sumRandom = ((double) t1 - (double) t0)/n;
00059                 cout << "summing in random order: " << sumRandom
00060                      << " us per operation " << sum << "\n";
00061         }
00062
00063         lst.clear();
00064         for (int i = 1; i <= n/2; i++) lst.addLast(perm[i]);
00065         t0 = Util::getTime();
00066         sum = 0;
00067         for (int i = 1; i <= n; i++) sum += lst.member(i);
00068         t1 = Util::getTime();
00069         double memberTest = ((double) t1 - (double) t0)/n;
00070         cout << sum << " " << t0 << " " << t1 << endl;
00071         cout << "membership testing: " << memberTest << " us per operation "
00072              << sum << "\n";
00073
00074         cout << endl;
00075 }
00076
00077 main() {
00078         perfTest(100);
00079         perfTest(1000);
00080         perfTest(10000);
00081         perfTest(100000);
00082         perfTest(1000000);
00083 }