簡單的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