Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами

Комментарии к посту, а также оформление будет, когда будет время :)

Компиляция: g++ -O3 1.cpp -felide-constructors -fno-exceptions -fno-rtti -funroll-loops -ffast-math -fomit-frame-pointer -march=opteron

Результаты:
test_map_inserts: Elapsed time: 1.900393s.
test_set_inserts: Elapsed time: 1.737445s.
test_vector_push_back: Elapsed time: 0.150905s.
test_vector_sort: Elapsed time: 0.105872s.
test_map_find: Elapsed time: 12.016727s.
test_set_find: Elapsed time: 11.943843s.
test_vector_find: Elapsed time: 5.747178s.
Mapsize =999752, Setsize=999778, Vsize=1000000


Код:

Copy Source | Copy HTML

1. #include <map>


2. #include <algorithm>


3. #include <stdio.h>


4. #include <set>


5. #include <stdlib.h>


6. #include <string.h>


7. #include <vector>


8. #include <sys/stat.h>


9. #include <sys/time.h>


10.  


11.  


12. using namespace std;


13.  


14. void start_profile();


15. void end_profile_print();


16.  


17.  


18. const long iterations = 10000000;


19. const long inserts = 1000000;


20. typedef long type1;


21. typedef int type2;


22.  


23. map<type1, type2> m;


24. map<type1, type2>::iterator m_it;


25. set<type1> s;


26. set<type1>::iterator s_it;


27. vector<type1> v;


28. vector<type1>::iterator v_it;


29.  


30. type1 my_rand(){


31.     return random();


32. }


33.  


34. void test_map_find(){


35.     type1 finder;


36.     for(long i=0; i<iterations; i++){


37.         finder = my_rand();


38.         m_it = m.find(finder);


39.     }


40. }


41.  


42. void test_set_find(){


43.     type1 finder;


44.     for(long i=0; i<iterations; i++){


45.         finder = my_rand();


46.         s_it = s.find(finder);


47.     }


48. }


49.  


50. void test_vector_find(){


51.     type1 finder;


52.     for(long i=0; i<iterations; i++){


53.         finder = my_rand();


54.         binary_search (v.begin(), v.end(), finder);


55.     }


56. }


57.  


58. void test_map_inserts(type2 x){


59.     type1 inserter;


60.     for(long i=0; i<inserts; i++){


61.         inserter = my_rand();


62.         m[inserter] = x;


63.     }


64. }


65. void test_set_inserts(){


66.     type1 inserter;


67.     for(long i=0; i<inserts; i++){


68.         inserter = my_rand();


69.         s.insert(inserter);


70.     }


71. }


72.  


73. void test_vector_push_back(){


74.     type1 inserter;


75.     for(long i=0; i<inserts; i++){


76.         inserter = my_rand();


77.         v.push_back(inserter);


78.     }


79. }


80.  


81. void test_vector_sort(){


82.     sort(v.begin(), v.end());


83. }


84.  


85. int main(){


86.     printf("test_map_inserts: ");


87.     start_profile();


88.     test_map_inserts(1);


89.     end_profile_print();


90.  


91.     printf("test_set_inserts: ");


92.     start_profile();


93.     test_set_inserts();


94.     end_profile_print();


95.  


96.     printf("test_vector_push_back: ");


97.     start_profile();


98.     test_vector_push_back();


99.     end_profile_print();


100.  


101.     printf("test_vector_sort: ");


102.     start_profile();


103.     test_vector_sort();


104.     end_profile_print();


105.  


106.     printf("test_map_find: ");


107.     start_profile();


108.     test_map_find();


109.     end_profile_print();


110.  


111.     printf("test_set_find: ");


112.     start_profile();


113.     test_set_find();


114.     end_profile_print();


115.  


116.     printf("test_vector_find: ");


117.     start_profile();


118.     test_vector_find();


119.     end_profile_print();


120.  


121.  


122.     printf("Mapsize =%ld, Setsize=%ld, Vsize=%ld\n", (long)m.size(), (long)s.size(), (long)v.size());


123.     return 0;


124. }


125.  


126. static struct timeval t1,t2;


127.  


128. void start_profile(){


129.     gettimeofday(&t1, NULL);


130. }


131. void end_profile_print(){


132.     gettimeofday(&t2, NULL);


133.     double d1 = double(t1.tv_sec) + double(t1.tv_usec ) / 1000000.0;


134.     double d2 = double(t2.tv_sec) + double(t2.tv_usec ) / 1000000.0;


135.     printf("Elapsed time: %fs.\n", d2-d1);


136. }


137.