测试map与vector的查询效率边界

freeeyes

今天由于需要，在这里做了一段测试代码。
测试vector和map的效能边界在哪里。
代码如下：

1. // STLTest.cpp : 定义控制台应用程序的入口点。
2. //
4. #include "stdafx.h"
5. #include <map>
6. #include <vector>
7. #include <time.h>
9. using namespace std;
11. int GetRandom(int nMinNumber, int nMaxNumber)
12. {
13.         return nMinNumber + (int)rand()%(nMaxNumber - nMinNumber);
14. }
16. int _tmain(int argc, _TCHAR* argv[])
17. {
18.         typedef vector<int> vecData;
19.         typedef map<int, int> mapData;
21.         vecData m_vecData;
22.         mapData m_mapData;
24.         for(int i = 0; i < 10000; i++)
25.         {
26.                 m_vecData.push_back(i);
28.                 m_mapData.insert(mapData::value_type(i, i));
29.         }
31.         srand((unsigned)time(NULL));
33.         int nBase = 10;
34.         for(int k = 0; k < 5; k++)
35.         {
36.                 nBase = nBase * 10;
37.                 printf_s("**************(%d)*************\n", nBase);
38.                 //计算vector统计成本
39.                 clock_t ckStart;
40.                 clock_t ckEnd;
42.                 ckStart = clock();
43.                 //随机找100万次查询
44.                 for(int i = 0; i < nBase; i++)
45.                 {
46.                         int nKey = GetRandom(0, 9999);
47.                         for(int j = 0; j < 10000; j++)
48.                         {
49.                                 if(m_vecData[j] == nKey)
50.                                 {
51.                                         break;
52.                                 }
53.                         }
54.                 }
55.                 ckEnd = clock();
56.                 double ttime =  (double)(ckEnd - ckStart) / CLOCKS_PER_SEC;
57.                 printf_s("[vector]nBase = %d, timecost=%lf.\n", nBase, ttime);
59.                 //计算map统计成本
60.                 ckStart = clock();
61.                 //随机找100万次查询
62.                 for(int i = 0; i < 1000000; i++)
63.                 {
64.                         int nKey = GetRandom(0, 9999);
65.                         mapData::iterator f = m_mapData.find(nKey);
66.                         if(f == m_mapData.end())
67.                         {
68.                                 printf_s("[map]No Find(%d).\n", nKey);
69.                         }
70.                 }
71.                 ckEnd = clock();
72.                 ttime =  (double)(ckEnd - ckStart) / CLOCKS_PER_SEC;
73.                 printf_s("[map]nBase=%d, timecost=%lf.\n", nBase, ttime);
74.                 printf_s("***************************\n");
75.         }
78.         getchar();
79.         return 0;
80. }

复制代码

输出如下：
**************(100)*************
[vector]nBase = 100, timecost=0.001000.
[map]nBase=100, timecost=0.160000.
***************************
**************(1000)*************
[vector]nBase = 1000, timecost=0.008000.
[map]nBase=1000, timecost=0.157000.
***************************
**************(10000)*************
[vector]nBase = 10000, timecost=0.050000.
[map]nBase=10000, timecost=0.164000.
***************************
**************(100000)*************
[vector]nBase = 100000, timecost=0.482000.
[map]nBase=100000, timecost=0.144000.
***************************
**************(1000000)*************
[vector]nBase = 1000000, timecost=4.485000.
[map]nBase=1000000, timecost=0.149000.
***************************

看来边界值在10000左右，知道这个边界，就知道怎么更好的利用容器了。

winston

你这个测试是有问题的啊。
stl的设计，是遵循最优原则的。vector本质上是数组，所以查找只能遍历。map是树，还有hash_map，检索采用的算法是不同的。

sevencat

有的时候还取决于你的key的比较的复杂度，比如说你用string来做key试试？估计边界就只有几百了。

freeeyes

我知道一个是数组，一个是hash命中。
我找的是，什么条件下用vector较好，什么条件下用map较好。
算法不通带来的差异也会不同。看需求了。

minchieh

freeeyes 发表于 2014-7-21 15:54
我知道一个是数组，一个是hash命中。
我找的是，什么条件下用vector较好，什么条件下用map较好。
算法不通 ...

map是红黑树   逻辑平衡二叉树

minchieh

你这个是 遍历*1次operator ==() 和  折半*2次operator <()   之间的性能比较
map的时间复杂度是   n根号2 *2次<比较      vector 是 n*1次==比较   
当 (n根号2 *2)  == (n)  是极值
明显当n越大   左边数据(时间复杂度)会越小

freeeyes

呵呵，恩。说道点上了。