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

     以下为测试代码：

1. /************************************************************** 
2. *    
3. *   Author: Chaos Lee 
4. *   Date: 2012-05-14 
5. *   Description: By traverse a big array, we can draw the  
6. *           draw the conclusion that what speedup 
7. *           we can achieve just replacing a simple 
8. *           data structure. 
9. ***************************************************************/ 
10. #include<map> 
11. #include<iostream> 
12. #include<sys/time.h> 
13.  
14. using namespace std; 
15.  
16. class Integer 
17. { 
18. public: 
19.     Integer(int i):_i(i){} 
20.     void set(int i){_i = i;} 
21.     int get(){return _i;} 
22. private: 
23.     int _i; 
24. }; 
25.  
26.  
27. #define M 800 
28. #define N 8 
29. #define OFFSET 1000 
30. int main(int argc,char *argv[]) 
31. { 
32.     map<int,Integer *> _map; 
33.     Integer *** ptr = new Integer**[M]; 
34.     for(int i=0;i<M;i++) 
35.     { 
36.         ptr[i] = new Integer*[N]; 
37.         for(int j=0;j<N;j++) 
38.         { 
39.             ptr[i][j] = new Integer(i*N+j); 
40.             _map.insert(pair<int,Integer*>(i*OFFSET+j,ptr[i][j])); 
41.         } 
42.     } 
43.     struct timeval start,end; 
44.     gettimeofday(&start,NULL); 
45.     for(int i=0;i<M;i++) 
46.     { 
47.         for(int j=0;j<N;j++) 
48.         { 
49.             ptr[i][j]->set(i*N+j+1); 
50.         } 
51.     } 
52.     gettimeofday(&end,NULL); 
53.     unsigned long elapsed1 = (end.tv_sec - start.tv_sec )* 1000000 + end.tv_usec - start.tv_usec; 
54.     cout<<elapsed1<<endl; 
55.     gettimeofday(&start,NULL); 
56.     for(int i=0;i<M;i++) 
57.     { 
58.         for(int j=0;j<N;j++) 
59.         { 
60.             map<int,Integer*>::iterator iter = _map.find(i*OFFSET + j); 
61.             if(iter == _map.end()) 
62.             { 
63.                 cout<<"error.\n"<<endl; 
64.                 exit(-1); 
65.             } 
66.             iter->second->set(i*N+j); 
67.         } 
68.     } 
69.     gettimeofday(&end,NULL); 
70.     unsigned long elapsed2 = (end.tv_sec - start.tv_sec )* 1000000 + end.tv_usec - start.tv_usec; 
71.     cout<<elapsed2<<endl; 
72.     cout<<"speedup ratio is "<<(float)elapsed2 / elapsed1<<endl; 
73.     return 0; 
74. } 

    接下来为测试结果：

     

1. [lichao@sg01 Performance]$ ./test 
2. 162 
3. 2988 
4. speedup ratio is 18.4444 
5. [lichao@sg01 Performance]$ ./test 
6. 136 
7. 2982 
8. speedup ratio is 21.9265 
9. [lichao@sg01 Performance]$ ./test 
10. 162 
11. 2966 
12. speedup ratio is 18.3086 
13. [lichao@sg01 Performance]$ ./test 
14. 151 
15. 3047 
16. speedup ratio is 20.1788 
17. [lichao@sg01 Performance]$ ./test 
18. 193 
19. 2953 
20. speedup ratio is 15.3005 
21. [lichao@sg01 Performance]$ ./test 
22. 149 
23. 2950 
24. speedup ratio is 19.7987 

 

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