542/doc/perf_stl_set_8cpp_source.html

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