为C++的map翻案，map实际是排序并且迭代效率不低的
为C++的map翻案，map实际是排序并且迭代效率不低的
write by 九天雁翎(JTianLing) -- www.jtianling.com
人类都有对未知事物的恐惧，map的使用即是其一，因为RB-Tree实在是太过于复杂，相当的复杂，去实现一个就知道我在说什么了，所以，作为一个C++程序员天生的从C继承过来的那种不知道怎么实现的，就不敢用的天性，很多人不敢好好的使用map，因为，我们不知道它是怎么实现的。我这里不是要来讨论其实现，请参考数据结构相关书籍，我这里仅仅是从外部测试来证实其特性，这样花费的功夫是最少的。
首先是map的排序性，因为hash表的混淆，导致很多人认为map不是排序的，实际中我看我们总监都不能肯定这件事情，所以常常仅仅将map作为一个搜索结构，然后另外弄一个list去处理排序并迭代的事情，这样相当于将一个map可以做的事情拆开来做，并且每次增删操作都要同步处理两件事情-_-!
其次是其迭代的速度，因为map的插入速度接近O(logN)，删除速度接近O(logN)，搜索速度也接近O(logN)，所以出于好事不能让其占尽的原则，map总有个缺点吧，迭代速度就是其一，至于慢到什么地步，到了迭代100个元素需要10毫秒的地步？测试数据面前说话。以下测试程序就是见证了这个问题，写这个测试程序，来源于工作中我希望利用map的排序性和multimap的可重复键特性来简化工作，但是开会讨论的结果是因为大家对map,multimap不熟悉而不能确定，以下是确定的过程：
（单位，毫秒，结果来自aqtime5,机器酷睿E2140,需要提醒的是因为用了aqtime的lines处理特性，所以速度会有一定的降低，这里并不是要测试绝对速度，仅仅是与list做比较，假如有人说list的迭代都慢的不能接受，那么map的迭代自然也不能接受）
#include "stdafx.h"
#include <list>
#include <map>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
// Hit Count : 1
// Time : 0.00
// Time with Children : 0.01
multimap<int, int, greater<int>> goMMap;
// Hit Count : 1
// Time : 0.00
// Time with Children : 0.00
map<int, int, greater<int>> goMap;
// Hit Count : 1
// Time : 0.00
// Time with Children : 0.01
list<int> goList;
// 测试一，Map的排序，实际是搜索二叉树的前序遍历
// 实际上搜索二叉树本来就是排好序的，只是说到map比较容易和hashmap混淆
// hash表是不排序的，博客上有个哈希表的实现，可以看到，就是通过哈希算法
// 找到一个独特的位置，然后尽快搜索的过程
void TestMapOrder()
// Hit Count : 1
// Time : 0.20
// Time with Children : 35.69
{
// 有序的插入对于平衡搜索二叉树来说是效率最慢的一种
for(int i=0; i < 100; ++i)
{
goMap.insert(make_pair(i, 1));
}
for(map<int, int, greater<int>>::const_iterator lit = goMap.begin();
lit != goMap.end(); ++lit)
{
cout <<lit->first << " ";
}
cout <<endl;
// 有序的插入对于平衡搜索二叉树来说是效率最慢的一种
for(int i=0; i < 100; ++i)
{
goMMap.insert(make_pair(i-1, 1));
goMMap.insert(make_pair(i, 1));
goMMap.insert(make_pair(i+1, 1));
}
for(multimap<int, int, greater<int>>::const_iterator lit = goMMap.begin();
lit != goMMap.end(); ++lit)
{
cout <<lit->first << " ";
}
cout <<endl;
}
#define TEST_TIMES 100
void MapIterate()
// Hit Count : 1
// Time : 2.31
// Time with Children : 2.59
{
int j = 0;
for(int i=0; i < TEST_TIMES; ++i)
{
for(multimap<int, int, greater<int>>::const_iterator lit = goMMap.begin();
lit != goMMap.end(); ++lit)
{
j+=lit->first;
}
}
cout <<j <<endl;
}
void ListIterate()
// Hit Count : 1
// Time : 1.95
// Time with Children : 2.26
{
int j = 0;
for(int i=0; i < TEST_TIMES; ++i)
{
for(list<int>::const_iterator lit = goList.begin();
lit != goList.end(); ++lit)
{
j+=*lit;
}
}
cout <<j <<endl;
}
// 主要是前序遍历迭代时的速度，虽然插入，删除，搜索速度都快才是map的强项
// 但是实际使用中不能忍受太慢的迭代速度,这里和list做比较
void TestMapSpeed()
// Hit Count : 1
// Time : 0.02
// Time with Children : 5.01
{
for(int i=0; i < 100; ++i)
{
goList.push_back(i-1);
goList.push_back(i);
goList.push_back(i+1);
}
MapIterate();
ListIterate();
}
int _tmain(int argc, _TCHAR* argv[])
// Hit Count : 1
// Time : 0.00
// Time with Children : 40.71
{
TestMapOrder();
TestMapSpeed();
return 0;
}
速度在上面已经有输出了，300元素，迭代100次，list花费2.26秒，multimap花费2.59秒，multimap的迭代速度的确比list慢，但是慢的比率实在是不太多，没有到传言中不可接受的地步，下面会做一个加强版的测试，测试在元素非常多（2万）的情况下，multimap的迭代速度降低的影响。
以上程序输出：
99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73
72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 4
6 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
100 99 99 98 98 98 97 97 97 96 96 96 95 95 95 94 94 94 93 93 93 92 92 92 91 91 9
1 90 90 90 89 89 89 88 88 88 87 87 87 86 86 86 85 85 85 84 84 84 83 83 83 82 82
82 81 81 81 80 80 80 79 79 79 78 78 78 77 77 77 76 76 76 75 75 75 74 74 74 73 73
73 72 72 72 71 71 71 70 70 70 69 69 69 68 68 68 67 67 67 66 66 66 65 65 65 64 6
4 64 63 63 63 62 62 62 61 61 61 60 60 60 59 59 59 58 58 58 57 57 57 56 56 56 55
55 55 54 54 54 53 53 53 52 52 52 51 51 51 50 50 50 49 49 49 48 48 48 47 47 47 46
46 46 45 45 45 44 44 44 43 43 43 42 42 42 41 41 41 40 40 40 39 39 39 38 38 38 3
7 37 37 36 36 36 35 35 35 34 34 34 33 33 33 32 32 32 31 31 31 30 30 30 29 29 29
28 28 28 27 27 27 26 26 26 25 25 25 24 24 24 23 23 23 22 22 22 21 21 21 20 20 20
19 19 19 18 18 18 17 17 17 16 16 16 15 15 15 14 14 14 13 13 13 12 12 12 11 11 1
1 10 10 10 9 9 9 8 8 8 7 7 7 6 6 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 0 0 -1
1485000
1485000
有点乱，从前面几排可以看出map是排序的，迭代可以按顺序输出。
后面的也证实，multimap也是同样。
最后的两排证明list,multmap的确经过了同样的迭代。
另外，经过一些反汇编分析的学习后，我不再完全相信VS了，因为其在release版本下有可能进行不可思议的省略优化，比如这里，最后的程序最后可能仅仅是直接保存了1485000并进行输出-_-!呵呵，那也不可能需要2毫秒。。。。看了反汇编代码确定，的确map,list都有完整的迭代过程。
其实从实现上考虑，可以想到，随着元素的增加，list的迭代速度是不会变慢的，但是map作为二叉树，树越大，其遍历的速度会越来越慢，这里为了看看到底会有多慢，将元素的个数扩大到一个实际中有可能会碰到的数值，3万，再来测试迭代速度。
Routine Name Time Time with Children Shared Time Hit Count
MapIterate 1.15 1.57 73.18 1
ListIterate 0.25 0.51 49.40 1
#define TEST_TIMES 100
void MapIterate()
// Hit Count : 1
// Time : 1.15
// Time with Children : 1.57
{
int j = 0;
for(multimap<int, int, greater<int>>::const_iterator lit = goMMap.begin();
lit != goMMap.end(); ++lit)
{
j+=lit->first;
}
cout <<j <<endl;
}
void ListIterate()
// Hit Count : 1
// Time : 0.25
// Time with Children : 0.51
{
int j = 0;
for(list<int>::const_iterator lit = goList.begin();
lit != goList.end(); ++lit)
{
j+=*lit;
}
cout <<j <<endl;
}
3万应该是我们公司游戏中我做的专卖店模块可能碰到的最大值了，这里map的迭代已经比list慢了3倍了，的确是慢的太多，看来这个世界上流言也不是无缘无故的有的，还是略有其事。至于慢3倍的迭代能不能接受，这个就可能得考虑一下了。不用multimap用什么呢？
用一个map来做搜索，然后再维护一个list用来遍历？维护两个容器的复杂度自然要比维护一个容器的复杂度高的多-_-!而且速度快很多吗？需要接受的是添加，删除时候的速度要慢一倍以上，也许还要远大于1倍，问题出在list到底排不排序？不排序，那删除的时候估计够呛，排序？那添加的时候呢？呵呵，map的优势不在于增加元素快，再快也没有list,vector的push_back快，不在于删除元素块，再快也没有list,vector的pop_back快，也不在于搜索速度快，再快也没有排序后的vector，list的find快，从上面看来，map的迭代还是非常慢的，但是map为什么好用呢？甚至成为了构建python,lua等脚本语言中的结构。就在于其所有操作的平均的效率，都不差。
这点就像很多人批评C++一样，高不成低不就，但是还是有人使用C++，就在于同样的特性在使用的时候也可以是比C语言的抽象能力更强，比其他高级语言的速度更快，更接近底层。
write by 九天雁翎(JTianLing) -- www.jtianling.com
其实个人感觉，真正可能会使C++成为历史的是将底层和上层完全分开的潮流，那样才会架空C++的空间。比如，底层与硬件打交道和要求速度非常快的部分交给C，然后上层逻辑全部交给Python等脚本语言，这才是C++最怕的事情。事实上使用过一些如python,mysql,lua的API后就会发现，不仅仅是windows API，事实上世界上大部分应用程序在提供自己的扩展接口时，基本都是C接口，毕竟因为C++的特性，要提供一个兼容的类接口不是那么容易的，这就是世界的格局，C语言几乎不可能从软件世界消失，因为它是如英语一样的世界通用语言，虽然C++的社团不断的希望融入这个世界，mysql也有第3方封装的C++ 接口，lua也有众多C++绑定接口,boost.python库的出现就是更是使C++为Python写扩展更加容易，但是要为世界所接受，仍然任重而道远。
很多人将python,lua等脚本语言称为胶水语言，我个人希望C++将来可以成为连接上层与下层的桥梁语言，可惜的是，这一点的实现已经越来越远，唯一的希望寄托在C++09x标准上了。
Posted By 九天雁翎 at 九天雁翎的博客 on 2009年02月15日