论坛 › 服务器端程序开发 › 测试map与vector的查询效率边界

freeeyes 发表于 2014-7-17 10:07:36

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

今天由于需要，在这里做了一段测试代码。
测试vector和map的效能边界在哪里。
代码如下：
// STLTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <map>
#include <vector>
#include <time.h>

using namespace std;

int GetRandom(int nMinNumber, int nMaxNumber)
{
        return nMinNumber + (int)rand()%(nMaxNumber - nMinNumber);
}

int _tmain(int argc, _TCHAR* argv[])
{
        typedef vector<int> vecData;
        typedef map<int, int> mapData;

        vecData m_vecData;
        mapData m_mapData;

        for(int i = 0; i < 10000; i++)
        {
                m_vecData.push_back(i);

                m_mapData.insert(mapData::value_type(i, i));
        }

        srand((unsigned)time(NULL));

        int nBase = 10;
        for(int k = 0; k < 5; k++)
        {
                nBase = nBase * 10;
                printf_s("**************(%d)*************\n", nBase);
                //计算vector统计成本
                clock_t ckStart;
                clock_t ckEnd;

                ckStart = clock();
                //随机找100万次查询
                for(int i = 0; i < nBase; i++)
                {
                        int nKey = GetRandom(0, 9999);
                        for(int j = 0; j < 10000; j++)
                        {
                                if(m_vecData == nKey)
                                {
                                        break;
                                }
                        }
                }
                ckEnd = clock();
                double ttime =(double)(ckEnd - ckStart) / CLOCKS_PER_SEC;
                printf_s("nBase = %d, timecost=%lf.\n", nBase, ttime);

                //计算map统计成本
                ckStart = clock();
                //随机找100万次查询
                for(int i = 0; i < 1000000; i++)
                {
                        int nKey = GetRandom(0, 9999);
                        mapData::iterator f = m_mapData.find(nKey);
                        if(f == m_mapData.end())
                        {
                                printf_s("No Find(%d).\n", nKey);
                        }
                }
                ckEnd = clock();
                ttime =(double)(ckEnd - ckStart) / CLOCKS_PER_SEC;
                printf_s("nBase=%d, timecost=%lf.\n", nBase, ttime);
                printf_s("***************************\n");
        }


        getchar();
        return 0;
}
输出如下：
**************(100)*************
nBase = 100, timecost=0.001000.
nBase=100, timecost=0.160000.
***************************
**************(1000)*************
nBase = 1000, timecost=0.008000.
nBase=1000, timecost=0.157000.
***************************
**************(10000)*************
nBase = 10000, timecost=0.050000.
nBase=10000, timecost=0.164000.
***************************
**************(100000)*************
nBase = 100000, timecost=0.482000.
nBase=100000, timecost=0.144000.
***************************
**************(1000000)*************
nBase = 1000000, timecost=4.485000.
nBase=1000000, timecost=0.149000.
***************************

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

winston 发表于 2014-7-18 10:55:31

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

sevencat 发表于 2014-7-21 08:57:40

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

freeeyes 发表于 2014-7-21 15:54:15

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

minchieh 发表于 2014-8-25 22:12:47

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

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

minchieh 发表于 2014-8-25 22:32:05

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

freeeyes 发表于 2014-8-26 14:58:00

呵呵，恩。说道点上了。

查看完整版本: 测试map与vector的查询效率边界