Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4204760
  • 博文数量: 176
  • 博客积分: 10059
  • 博客等级: 上将
  • 技术积分: 4681
  • 用 户 组: 普通用户
  • 注册时间: 2006-03-24 12:27
文章分类

全部博文(176)

文章存档

2012年(1)

2011年(4)

2010年(14)

2009年(71)

2008年(103)

分类: C/C++

2012-01-08 22:27:29

by zieckey

测试条件:
gcc version 4.2.1 20070719  [FreeBSD]
FreeBSD  7.2-RELEASE #0: Fri May  1 07:18:07 UTC 2009     root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC  amd64
Intel(R) Xeon(R) CPU           E5620  @ 2.40GHz 16核

测试程序说明:
先准备好n个字符串随机的MD5字符串做为key,然后分别对3个容器进行插入、遍历、查找、删除操作。
例如,n=100的时候,插入是指插入100个随机MD5 key;遍历是指对容器遍历一次;查找是指分别对这个100个随机的MD5 key做查找操作(即查找100次);删除是指挨个删除这个100个随机MD5 key。

测试数据如下表:

插入,单位us1001K10K100K1M10M
std::map241283335888381214443908862233380
std::ext/hash_map97166716466146025178844618512639
std::tr1::unordered_map777728052530946583127429297


遍历,单位us1001K10K100K1M10M
std::map1176842116031557001771906
std::ext/hash_map474304218398804703444781575
std::tr1::unordered_map112121

查找,单位us1001K10K100K1M10M
std::map156211130456258709410026059064394
std::ext/hash_map777748056569746602317705527
std::tr1::unordered_map777728051544566595377600263

删除,单位us1001K10K100K1M10M
std::map291364149584472414667589792491113
std::ext/hash_map8986990688652496476710372650
std::tr1::unordered_map494804879330873950984369617

结论:
1. std::tr1::unordered_map 与 std::ext/hash_map 
     任何情况下,如果要在这两个容器之间选择的话,我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map,甚至可以说远远优于 hash_map。

2. std::tr1::unordered_map 与 std::map 
     map的性能总体来说是最差的。但是,当我们需要一个有序的关联容器的时候,我们必须选择std::map,因为 unordered_map 内部元素不是有序的,这一点从名字都可以看出来。除此之外都应该选择 unordered_map 。

3. 上述测试中,unordered_map 的遍历性能几乎是常数级别的,与常识不太相符,需要再研究研究。

附录:贴上源代码
说明:与测试程序稍有区别,这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。

如有错误还请跟帖指出,非常感谢。


  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <list>
  5. #include <map>
  6. #include <sys/time.h>
  7. #include <ext/hash_map>
  8. #include <tr1/unordered_map>

  9. namespace zl
  10. { //{{{
  11.     struct equal_to
  12.     {
  13.         bool operator()(const char* s1, const char* s2) const
  14.         {
  15.             return strcmp(s1, s2) == 0;
  16.         }
  17.     };
  18.  
  19.     struct hash_string
  20.         : public std::unary_function<std::string, std::size_t>
  21.         {
  22.             std::size_t
  23.                 operator()(const std::string& __s) const
  24. #ifdef __linux__
  25.                 { return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
  26. #else
  27.                 { return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
  28. #endif
  29.         };

  30.     
  31.     struct hash_charptr
  32.         : public std::unary_function<const char*, std::size_t>
  33.         {
  34.             std::size_t
  35.                 operator()(const char* __s) const
  36. #ifdef __linux__
  37.                 { return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
  38. #else
  39.                 { return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
  40. #endif
  41.         };
  42. }//}}}

  43. typedef std::list<std::string> string_list;
  44. typedef std::map<std::string, int> string_map;
  45. typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
  46. typedef std::tr1::unordered_map<std::string, int> string_unordered_map;

  47. void fill_list(string_list& slist, size_t count);
  48. uint64_t current_usec();

  49. int main( int argc, char* argv[] )
  50. {
  51.     if (argc != 2 && argc != 3)
  52.     {
  53.         fprintf(stderr, "Usage:%s test_count rehash\n", argv[0]);
  54.         fprintf(stderr, "For example:%s 10000 rehash\n", argv[0]);
  55.         return -1;
  56.     }

  57.     size_t count = atoi(argv[1]);
  58.     bool rehash = false;
  59.     if (argc == 3)
  60.     {
  61.         rehash = true;
  62.     }

  63.     string_map smap;
  64.     string_hash_map shash_map;
  65.     string_unordered_map sunordered_map;

  66.     if (rehash)
  67.     {
  68.         sunordered_map.rehash(count);
  69.     }

  70.     string_list slist;
  71.     fill_list(slist, count);

  72.     uint64_t start = 0;
  73.     uint64_t end = 0;

  74.     uint64_t map_insert_us = 0;
  75.     uint64_t hash_map_insert_us = 0;
  76.     uint64_t unordered_map_insert_us = 0;

  77.     uint64_t map_traverse_us = 0;
  78.     uint64_t hash_map_traverse_us = 0;
  79.     uint64_t unordered_map_traverse_us = 0;

  80.     uint64_t map_find_us = 0;
  81.     uint64_t hash_map_find_us = 0;
  82.     uint64_t unordered_map_find_us = 0;

  83.     uint64_t map_delete_us = 0;
  84.     uint64_t hash_map_delete_us = 0;
  85.     uint64_t unordered_map_delete_us = 0;



  86.     // Insert test
  87.     {//{{{
  88.         string_list::iterator it(slist.begin());
  89.         string_list::iterator ite(slist.end());

  90.         //map insert
  91.         start = current_usec();
  92.         for (int i = 0; it != ite; ++it, ++i)
  93.         {
  94.             smap[*it] = i;
  95.         }
  96.         end = current_usec();
  97.         map_insert_us = end - start;

  98.         //hash_map insert
  99.         it = slist.begin();
  100.         start = current_usec();
  101.         for (int i = 0; it != ite; ++it, ++i)
  102.         {
  103.             shash_map[*it] = i;
  104.         }
  105.         end = current_usec();
  106.         hash_map_insert_us = end - start;

  107.         //unordered_map insert
  108.         it = slist.begin();
  109.         start = current_usec();
  110.         for (int i = 0; it != ite; ++it, ++i)
  111.         {
  112.             shash_map[*it] = i;
  113.         }
  114.         end = current_usec();
  115.         unordered_map_insert_us = end - start;
  116.     }//}}}

  117.     // Traverse test
  118.     {//{{{
  119.         //map traverse
  120.         {
  121.             string_map::iterator it(smap.begin());
  122.             string_map::iterator ite(smap.end());
  123.             start = current_usec();
  124.             for (int i = 0; it != ite; ++it)
  125.             {
  126.                 i++;
  127.             }
  128.             end = current_usec();
  129.             map_traverse_us = end - start;
  130.         }

  131.         //hash_map traverse
  132.         {
  133.             string_hash_map::iterator it(shash_map.begin());
  134.             string_hash_map::iterator ite(shash_map.end());
  135.             start = current_usec();
  136.             for (int i = 0; it != ite; ++it)
  137.             {
  138.                 i++;
  139.             }
  140.             end = current_usec();
  141.             hash_map_traverse_us = end - start;
  142.         }

  143.         //unordered_map traverse
  144.         {
  145.             string_unordered_map::iterator it(sunordered_map.begin());
  146.             string_unordered_map::iterator ite(sunordered_map.end());
  147.             start = current_usec();
  148.             for (int i = 0; it != ite; ++it)
  149.             {
  150.                 i++;
  151.             }
  152.             end = current_usec();
  153.             unordered_map_traverse_us = end - start;
  154.         }
  155.     }//}}}

  156.     // Find test
  157.     {//{{{
  158.         string_list::iterator it(slist.begin());
  159.         string_list::iterator ite(slist.end());

  160.         //map find
  161.         start = current_usec();
  162.         for (int i = 0; it != ite; ++it, ++i)
  163.         {
  164.             smap[*it] = i;
  165.         }
  166.         end = current_usec();
  167.         map_find_us = end - start;

  168.         //hash_map find
  169.         it = slist.begin();
  170.         start = current_usec();
  171.         for (int i = 0; it != ite; ++it, ++i)
  172.         {
  173.             shash_map[*it] = i;
  174.         }
  175.         end = current_usec();
  176.         hash_map_find_us = end - start;

  177.         //unordered_map find
  178.         it = slist.begin();
  179.         start = current_usec();
  180.         for (int i = 0; it != ite; ++it, ++i)
  181.         {
  182.             shash_map[*it] = i;
  183.         }
  184.         end = current_usec();
  185.         unordered_map_find_us = end - start;
  186.     }//}}}

  187.     // Delete test
  188.     {//{{{
  189.         string_list::iterator it(slist.begin());
  190.         string_list::iterator ite(slist.end());

  191.         //map delete
  192.         start = current_usec();
  193.         for (int i = 0; it != ite; ++it, ++i)
  194.         {
  195.             smap.erase(*it);
  196.         }
  197.         end = current_usec();
  198.         map_delete_us = end - start;

  199.         //hash_map delete
  200.         it = slist.begin();
  201.         start = current_usec();
  202.         for (int i = 0; it != ite; ++it, ++i)
  203.         {
  204.             shash_map.erase(*it);
  205.         }
  206.         end = current_usec();
  207.         hash_map_delete_us = end - start;

  208.         //unordered_map delete
  209.         it = slist.begin();
  210.         start = current_usec();
  211.         for (int i = 0; it != ite; ++it, ++i)
  212.         {
  213.             shash_map.erase(*it);
  214.         }
  215.         end = current_usec();
  216.         unordered_map_delete_us = end - start;
  217.     }//}}}

  218.     //stat output
  219.     std::cout << " insert, count " << count << std::endl;
  220.     std::cout << " std::map " << map_insert_us << " us\n";
  221.     std::cout << " std::ext/hash_map " << hash_map_insert_us << " us\n";
  222.     std::cout << "std::tr1::unordered_map " << unordered_map_insert_us << " us\n";

  223.     std::cout << "\n";
  224.     std::cout << " traverse, count " << count << std::endl;
  225.     std::cout << " std::map " << map_traverse_us << " us\n";
  226.     std::cout << " std::ext/hash_map " << hash_map_traverse_us << " us\n";
  227.     std::cout << "std::tr1::unordered_map " << unordered_map_traverse_us << " us\n";

  228.     std::cout << "\n";
  229.     std::cout << " find, count " << count << std::endl;
  230.     std::cout << " std::map " << map_find_us << " us\n";
  231.     std::cout << " std::ext/hash_map " << hash_map_find_us << " us\n";
  232.     std::cout << "std::tr1::unordered_map " << unordered_map_find_us << " us\n";

  233.     std::cout << "\n";
  234.     std::cout << " delete, count " << count << std::endl;
  235.     std::cout << " std::map " << map_delete_us << " us\n";
  236.     std::cout << " std::ext/hash_map " << hash_map_delete_us << " us\n";
  237.     std::cout << "std::tr1::unordered_map " << unordered_map_delete_us << " us\n";

  238.      
  239.     return 0;
  240. }

  241. void fill_list(string_list& slist, size_t count)
  242. {
  243.     for (size_t i = 0; i < count; ++i)
  244.     {
  245.         std::ostringstream oss;
  246.         oss << i;
  247.         //slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
  248.         slist.push_back(oss.str());
  249.     }
  250. }


  251. uint64_t current_usec()
  252. {
  253.     struct timeval tv;
  254.     gettimeofday( &tv, NULL );
  255.     return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
  256. }
阅读(35814) | 评论(2) | 转发(1) |
2

上一篇:C++ STL 学习 :自己写仿函数(functor)(三)

下一篇:没有了

给主人留下些什么吧!~~

goodmomuce2016-05-04 18:47:31

一看博主就很不认真,你这样的测试结果不是误导大家吗?
我专门注册一个帐号来发表评论的,估计大家发现了也懒得注册帐号了

好几个地方shash_map和sunordered_map没有分清楚

插入的地方:sunordered_map根本就没有插入任何变量,难关变量时间那么短
查找的地方:应该使用find而你不是[]运算符,sunordered_map也没有进行查找,写的还是shash_map
删除的地方:sunordered_map也没有进行删除,写的还是shash_map,只不过这个时候sunordered_map已经空了

这个是我的测试结果
 insert, count 2000000
 std::map 1204 ms
 std::ext/hash_map 850 ms
std::tr1::unordered_map 544 ms

 traverse, count 2000000
 std::map 52 ms
 st

lonely_212014-03-20 15:30:02

文明上网,理性发言...