1st_noiz (1st_noiz) wrote,
1st_noiz
1st_noiz

Совет 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.  


Subscribe

  • C/C++ memory management - realloc and mremap

    English version below Прочитал новость, что mremap в Linux 3.2 ускорили, а точнее улучшили работу с TLB. Какие программы это ускорит? В каких…

  • Science article generator

    English version below Генератор научных статей. Вводим автора(ов) нажимаем generate и у нас статья с картинками, формулами, графиками. Я ввел…

  • DJBX33A collisions

    (English version below) Прочитал новость о коллизиях в реализациях хэш функций в php/python/ ... Как пишут в статье "PHP realistically: 500k of…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 2 comments