C++中各种<string,T>关联方式的速度对比
2024-10-09 21:09:21
把<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的耗时相差无几）。
最新文章
- C#读取文件为byte[]
- Thinkphp3.2中的模板继承
- 网页爬虫--scrapy进阶
- redis AND memcache
- Linux远程管理
- qwt6在Windows下Qt5的编译，安装，初步使用
- [Lua]Mac系统上安装Lua环境
- MySQL写压力性能监控与调优
- 通过java代码往mysql数据库中写入日期相关数据少13个小时
- mkfs.ext4快速格式化大容量硬盘
- php学习----基本介绍及数据类型
- VUE学习第一天，安装
- Python RabbitMQ RPC实现
- PHP开发小技巧②—实现二维数组根据key进行排序
- 算法笔记_199:第二届蓝桥杯软件类决赛真题(C语言本科)
- SQL与NOSQL
- pycharm 修改新建文件时的头部模板
- 远程连接软件TeamViewer
- awk基础03-分支和循环语句
- CentOS6安装各种大数据软件 第一章：各个软件版本介绍