vector,unordered_map和map的效率简要比较 - 小众知识

vector,unordered_map和map的效率简要比较

2013年01月27日 14:18:05 苏内容
  标签: vector/map/unordered_map
阅读:592

项目中要对一些数据结构进行存取,而项目本身对时间延时比较敏感,在使用vector还是map上着实纠结了一番,主要某些数据量比较小,才有此纠结。

而且想搞明白,到底大到什么数据量该用map?做了一些简单的测试,见下。


首先,不管是vector还是map,请尽量存取指针,否则在存取时会有数据拷贝带来不必要的时间损失。通常用int和string做key的场景比较普遍(我的项目即如此),能用int作key就用int作key,效率比string高。


测试方法:

给vector和map容器中分别塞入1,000,000个数据(顺序插入,有序的),然后设定一个查找目标,vector顺序遍历查找,map用key查找,对比查找时间。使用高精度定时器计时。


基本结论:

1、unordered_map比map快

2、vector查找14次,基本和unordered_map查找一次耗时相当(int和string做key差别不大)

3、string作key,vector查询100次,基本和map查询一次耗时相当;int作key,vector查询28次,基本和map查询一次耗时相当

4、boost的unordered_map和map与STL的效率基本相同


因此:抛弃map,用unordered_map吧。如果明确数据量小,比如小于14个,就用vector或数组,效率更高。


unordered_map<string,...>



unordered_map<int,...>



map<string, ...>



map<int,...>



测试代码:

  1. #include <windows.h>
  2. #include <string>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <map>
  6. #include <unordered_map>
  7. #include <boost/unordered_map.hpp>
  8. #include <boost/interprocess/containers/map.hpp>
  9. #include <algorithm>
  10. using namespace std;
  11. struct MyStruct
  12. {
  13. MyStruct() {}
  14. MyStruct(int x, string s) : i(x), str(s) {}
  15. int i;
  16. string str;
  17. };
  18. #define VECTOR_TEST_DEF std::vector<MyStruct*>
  19. //#define STRING_KEY
  20. #define MAP_TYPE std::map
  21. //#define MAP_TYPE std::unordered_map
  22. //#define MAP_TYPE boost::unordered_map
  23. //#define MAP_TYPE boost::interprocess::map
  24. #define MAP_TYPE_STR "std::map"
  25. //#define MAP_TYPE_STR "std::unordered_map"
  26. //#define MAP_TYPE_STR "boost::unordered_map"
  27. //#define MAP_TYPE_STR "boost::interprocess::map"
  28. #ifdef STRING_KEY
  29. #define MAP_TEST_DEF MAP_TYPE<string, MyStruct*>
  30. #define TARGET_VAL "100"
  31. #else
  32. #define MAP_TEST_DEF MAP_TYPE<int, MyStruct*>
  33. #define TARGET_VAL 28
  34. #endif
  35. #define DATA_COUNT 1000000
  36. #define LOOP_COUNT 10000
  37. LARGE_INTEGER m_counterFreq;
  38. MyStruct* vectorRet;
  39. MyStruct* mapRet;
  40. string ToString(int d)
  41. {
  42. char szBuf[8];
  43. sprintf_s(szBuf, "%d", d);
  44. return string(szBuf);
  45. }
  46. LONGLONG GetMicroSecCounter()
  47. {
  48. LARGE_INTEGER counter = { 0 };
  49. QueryPerformanceCounter(&counter);
  50. return counter.QuadPart * 1000000 / m_counterFreq.QuadPart;
  51. }
  52. string GetTimeDiffMillSecStr(LONGLONG microCounterBegin, LONGLONG micoCounterEnd)
  53. {
  54. double dblDiff = (micoCounterEnd - microCounterBegin) / (double)1000;
  55. char szBuf[32];
  56. sprintf_s(szBuf, "%.3fms", dblDiff);
  57. return szBuf;
  58. }
  59. void TestVectorMap()
  60. {
  61. VECTOR_TEST_DEF vecTest;
  62. MAP_TEST_DEF mapTest;
  63. QueryPerformanceFrequency(&m_counterFreq);
  64. vecTest.resize(DATA_COUNT);
  65. for (int i = 0; i < DATA_COUNT; i++)
  66. {
  67. string str = ToString(i);
  68. MyStruct* t = new MyStruct(i, str);
  69. vecTest[i] = t;
  70. #ifdef STRING_KEY
  71. mapTest[str] = t;
  72. #else
  73. mapTest[i] = t;
  74. #endif // STRING_KEY
  75. }
  76. LONGLONG t1 = HighPreciseTickCounter::GetMicroSecCounter();
  77. VECTOR_TEST_DEF::iterator iterVec;
  78. for (int i = 0; i < LOOP_COUNT; i++)
  79. {
  80. iterVec = vecTest.begin();
  81. for (; iterVec != vecTest.end(); iterVec++)
  82. {
  83. #ifdef STRING_KEY
  84. if (!strcmp((*iterVec)->str.c_str(), TARGET_VAL))
  85. #else
  86. if ((*iterVec)->i == TARGET_VAL)
  87. #endif // STRING_KEY
  88. {
  89. vectorRet = *iterVec;
  90. break;
  91. }
  92. }
  93. }
  94. LONGLONG t2 = HighPreciseTickCounter::GetMicroSecCounter();
  95. MAP_TEST_DEF::iterator iterMap;
  96. for (int i = 0; i < LOOP_COUNT; i++)
  97. {
  98. #ifdef STRING_KEY
  99. iterMap = mapTest.find(TARGET_VAL);
  100. #else
  101. iterMap = mapTest.find(TARGET_VAL);
  102. #endif // STRING_KEY
  103. if (iterMap != mapTest.end())
  104. mapRet = iterMap->second;
  105. }
  106. LONGLONG t3 = HighPreciseTickCounter::GetMicroSecCounter();
  107. #ifdef STRING_KEY
  108. string keyType = "<string, MyStruct*>";
  109. #else
  110. string keyType = "<int, MyStruct*>";
  111. #endif // STRING_KEY
  112. std::cout << setiosflags(ios::left);
  113. std::cout << setw(20) << "Find Target Val: " << TARGET_VAL << std::endl;
  114. std::cout << setw(20) << "Find Loop Count: " << LOOP_COUNT << std::endl;
  115. std::cout << setw(20) << "Find Cost Vector: " << GetTimeDiffMillSecStr(t1, t2) << std::endl;
  116. std::cout << setw(20) << "Find Cost Map: " << GetTimeDiffMillSecStr(t2, t3) << "   " << MAP_TYPE_STR << keyType << std::endl;
  117. cout << setw(20) << "Vector Find: " << vectorRet->str << endl;
  118. cout << setw(20) << "Map Find: " << mapRet->str << endl;
  119. for (int i = 0; i < DATA_COUNT; i++)
  120. {
  121. MyStruct* t = vecTest[i];
  122. delete t;
  123. }
  124. }

但经过小编测试,1000000个数据,100000次搜索

Find Target Val:    50098

Find Vector(Int) Cost  : 0.053ms //因为int比较很快,所以仅查找int肯定是vector胜出,因此以此为基准对比

Find Vector(Str) Cost  : 3.872ms //不知道是不是因为小编的编译器问题,字符串对比非常慢,此处将查找次数改成了100,否则根本无法使用

Find Map(Int) Cost     : 0.241ms  //Map的Int查找还可以,为基准的5倍

Find Map(String) Cost : 0.748ms //Map的string查找为基准的15倍,但比vector查找字符串要快的多

UnorderMap(Int) Cost : 0.083ms //Unordered Map果然速度优秀,int索引仅为基准的1.6倍,速度基本没差

UnorderMap(Str) Cost : 0.107ms //Unordered Map的字符串搜索也非常优秀,仅为基准的2倍,和int相差无几,证明hash表搜索堪称极速

Index Vector Cost      : 0.002ms

Index Vector(at) Cost  : 0.001ms

Index Vector(it) Cost  : 0.066ms


(进程 16768)已退出,代码为 0。

要在调试停止时自动关闭控制台,请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口. . .


扩展阅读
© CopyRight 2010-2021, PREDREAM.ORG, Inc.All Rights Reserved. 京ICP备13045924号-1