C++中各种关联方式的速度对比

  把<string,T>(T为任意类型)关联起来,是很常见的需求。如笔者最近要做一个贝叶斯算法的垃圾邮件过滤器,就需要把每个单词与频率对应起来,做成一个表。而当单词很多时,对于每个单词做一遍O(N)的枚举,效率实在不尽人意。而下文讲到的一些关联容器或函数,都可以吧时间复杂度降至O(log2n)或更低。

  本文对比4种方法,以实验的方法得到数据,四种方法分别是:map,unordered_map,二分查找(递归),二分查找(非递归)。

  实验的源码可在下面的地址下载(Code::Blocks工程类型):maptest.zip(注:代码中引用的“tr1/unordered_map”在不支持C++0X的编译器上可能没有,这时候只需修改引用为“boost/unordered_map.hpp”并把命名空间部分改为boost::unordered_map即可)

  实验得出的结果如下(测试环境:Mingw4.8.2,CPU:E3-1230V2,数据N=5000000):

耗时(单位:CPU时钟) unordered_map map 二分查找(非递归) 二分查找(递归)
  6586 19219 12792 13182

  很显然可以看出,四种方法的效率相差甚远(unorered_map>二分查找(非递归)>二分查找(递归)>map)。然而,推测一下便可知,其中二分查找系列的方法,内存肯定是最小的(辅助空间为O(logn)),map与unordered_map应该差不多。所以,我们可以得出一下结论:

  • 在数据排好序时,最好用非递归版的二分查找(实验中二分查找的排序时间也算入了总时间内)
  • 在数据无序时,小数据可以使用map,大数据则使用unordered_map(当N=50000时,map与unordered_map的耗时相差无几)。
上一篇:jquery使用FormData提交数据


下一篇:web app变革之rem(转载)