Grafalgo
Library of useful data structures and algorithms
|
00001 #include "stdinc.h" 00002 #include "HashMap.h" 00003 #include "Util.h" 00004 00005 using namespace grafalgo; 00006 00007 void basicEval(int n) { 00008 int t1, t2; 00009 HashMap map(n); 00010 int *perm = new int[2*n+1]; 00011 Util::genPerm(2*n,perm); 00012 00013 cout << "putting in random order: "; 00014 t1 = Util::getTime(); 00015 for (int i = 1; i <= n; i++) { 00016 map.put(perm[i],i); 00017 } 00018 t2 = Util::getTime(); 00019 cout << t2-t1 << " " << ((double) (t2-t1))/n << endl; 00020 00021 cout << "getting in reverse random order (hits): "; 00022 t1 = Util::getTime(); 00023 for (int i = 1; i <= n; i++) { 00024 map.get(perm[(n+1)-i]); 00025 } 00026 t2 = Util::getTime(); 00027 cout << t2-t1 << " " << ((double) (t2-t1))/n << endl; 00028 00029 cout << "getting in random order (misses): "; 00030 t1 = Util::getTime(); 00031 for (int i = n+1; i <= 2*n; i++) { 00032 map.get(perm[i]); 00033 } 00034 t2 = Util::getTime(); 00035 cout << t2-t1 << " " << ((double) (t2-t1))/n << endl; 00036 00037 cout << "remapping existing pairs: "; 00038 t1 = Util::getTime(); 00039 for (int i = 1; i <= n; i++) { 00040 if (!map.put(perm[i],-i)) { 00041 cout << "put failed\n"; 00042 return; 00043 } 00044 } 00045 t2 = Util::getTime(); 00046 cout << t2-t1 << " " << ((double) (t2-t1))/n << endl; 00047 00048 cout << "remove/put pairs: "; 00049 t1 = Util::getTime(); 00050 for (int i = 1; i <= n; i++) { 00051 map.remove(perm[i]); 00052 if (!map.put(perm[i+n],i+n)) { 00053 cout << "put failed\n"; 00054 return; 00055 } 00056 } 00057 t2 = Util::getTime(); 00058 cout << t2-t1 << " " << ((double) (t2-t1))/n << endl; 00059 } 00060 00061 00062 int main() { 00063 int n = 1000; 00064 cout << "n=" << n << endl; 00065 basicEval(n); 00066 00067 n = 2000; 00068 cout << "n=" << n << endl; 00069 basicEval(n); 00070 00071 n = 4000; 00072 cout << "n=" << n << endl; 00073 basicEval(n); 00074 00075 n = 10000; 00076 cout << "n=" << n << endl; 00077 basicEval(n); 00078 00079 n = 20000; 00080 cout << "n=" << n << endl; 00081 basicEval(n); 00082 00083 n = 40000; 00084 cout << "n=" << n << endl; 00085 basicEval(n); 00086 00087 n = 100000; 00088 cout << "n=" << n << endl; 00089 basicEval(n); 00090 00091 n = 200000; 00092 cout << "n=" << n << endl; 00093 basicEval(n); 00094 00095 n = 400000; 00096 cout << "n=" << n << endl; 00097 basicEval(n); 00098 00099 n = 1000000; 00100 cout << "n=" << n << endl; 00101 basicEval(n); 00102 }