九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

为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,需要提醒的是因为用了aqtimelines处理特性,所以速度会有一定的降低,这里并不是要测试绝对速度,仅仅是与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,vectorpush_back快,不在于删除元素块,再快也没有list,vectorpop_back快,也不在于搜索速度快,再快也没有排序后的vectorlistfind快,从上面看来,map的迭代还是非常慢的,但是map为什么好用呢?甚至成为了构建python,lua等脚本语言中的结构。就在于其所有操作的平均的效率,都不差。

这点就像很多人批评C++一样,高不成低不就,但是还是有人使用C++,就在于同样的特性在使用的时候也可以是比C语言的抽象能力更强,比其他高级语言的速度更快,更接近底层。

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

其实个人感觉,真正可能会使C++成为历史的是将底层和上层完全分开的潮流,那样才会架空C++的空间。比如,底层与硬件打交道和要求速度非常快的部分交给C,然后上层逻辑全部交给Python等脚本语言,这才是C++最怕的事情。事实上使用过一些如python,mysql,luaAPI后就会发现,不仅仅是windows API,事实上世界上大部分应用程序在提供自己的扩展接口时,基本都是C接口,毕竟因为C++的特性,要提供一个兼容的类接口不是那么容易的,这就是世界的格局,C语言几乎不可能从软件世界消失,因为它是如英语一样的世界通用语言,虽然C++的社团不断的希望融入这个世界,mysql也有第3方封装的C++ 接口,lua也有众多C++绑定接口,boost.python库的出现就是更是使C++Python写扩展更加容易,但是要为世界所接受,仍然任重而道远。

很多人将python,lua等脚本语言称为胶水语言,我个人希望C++将来可以成为连接上层与下层的桥梁语言,可惜的是,这一点的实现已经越来越远,唯一的希望寄托在C++09x标准上了。

 

分类:  C++ 
标签:  C++  map 

Posted By 九天雁翎 at 九天雁翎的博客 on 2009年02月15日

分享到:

前一篇: 潜心开始学习网络编程的第一步 ,UNP(Unix Network Programming)第一章,时间服务器到windows的移植 后一篇: 以此纪念刚开始在linux上学习网络编程的失败-_-!