简单的map性能评测

   map是编程中常用的数据结构之一，map在检索的时候的时间复杂度一般为logN,下面这个简单的测试程序能确实证实这一点。当二维数组的大小为6400时，二者的速度相差为15倍左右。

     以下为测试代码：

/************************************************************** 

*    

*   Author: Chaos Lee 

*   Date: 2012-05-14 

*   Description: By traverse a big array, we can draw the  

*           draw the conclusion that what speedup 

*           we can achieve just replacing a simple 

*           data structure. 

***************************************************************/ 

#include<map> 

#include<iostream> 

#include<sys/time.h> 

using namespace std; 

class Integer 

{ 

public: 

    Integer(int i):_i(i){} 

    void set(int i){_i = i;} 

    int get(){return _i;} 

private: 

    int _i; 

}; 

#define M 800 

#define N 8 

#define OFFSET 1000 

int main(int argc,char *argv[]) 

    map<int,Integer *> _map; 

    Integer *** ptr = new Integer**[M]; 

    for(int i=0;i<M;i++) 

    { 

        ptr[i] = new Integer*[N]; 

        for(int j=0;j<N;j++) 

        { 

            ptr[i][j] = new Integer(i*N+j); 

            _map.insert(pair<int,Integer*>(i*OFFSET+j,ptr[i][j])); 

        } 

    } 

    struct timeval start,end; 

    gettimeofday(&start,NULL); 

            ptr[i][j]->set(i*N+j+1); 

    gettimeofday(&end,NULL); 

    unsigned long elapsed1 = (end.tv_sec - start.tv_sec )* 1000000 + end.tv_usec - start.tv_usec; 

    cout<<elapsed1<<endl; 

            map<int,Integer*>::iterator iter = _map.find(i*OFFSET + j); 

            if(iter == _map.end()) 

            { 

                cout<<"error.\n"<<endl; 

                exit(-1); 

            } 

            iter->second->set(i*N+j); 

    unsigned long elapsed2 = (end.tv_sec - start.tv_sec )* 1000000 + end.tv_usec - start.tv_usec; 

    cout<<elapsed2<<endl; 

    cout<<"speedup ratio is "<<(float)elapsed2 / elapsed1<<endl; 

    return 0; 

} 

    接下来为测试结果：

[lichao@sg01 Performance]$ ./test 

162 

2988 

speedup ratio is 18.4444 

136 

2982 

speedup ratio is 21.9265 

2966 

speedup ratio is 18.3086 

151 

3047 

speedup ratio is 20.1788 

193 

2953 

speedup ratio is 15.3005 

149 

2950 

speedup ratio is 19.7987 

本文转自hipercomer 51CTO博客，原文链接:http://blog.51cto.com/hipercomer/863347