【9RIA—iloveas】— 【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(1-起)

iloveas

转载：9RIA游戏开发者社区（天地会）
作者：iloveas（大神）


目录：
【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(1)
【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(2)
【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(3)
【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(4)



本贴旨在以浅显形象的方式帮助大家理解数组等集合对象的效率及其访问机制，受表达能力所限，我所打的比方可能都不太合适，你们可以追究个中的细节，只要不影响你们的理解即可。

本人上学的时候没认真听C/C++的课，所以本贴的很多观点都建立于自己臆测出来的“理论”之上，可能漏洞百出，不堪一击，还望众大神批评指正。

废话说完了，开始进入正题。

在计算机中，程序里的对象都通过所谓的“寻址”方式进行定位和访问，“寻址”，顾名思义就是寻找地址，像大街或者马路上的门牌号就是地址的重要组成部分（图1）。



咦？好像没怎么见过0号的门牌哦。确实，想在大街上找个0号门牌确实难于上青天，但是在计算机的世界里，好多好多的东西都喜欢以0作为起始编号，或者叫做索引。为避免产生不必要的误解，我就把电脑里面的规矩都搬到街上去吧。另外，关于单双号分布于两侧的问题大家也不要纠结了。

很显然，世界上的马路远不止图1上的那条，所以为了区分不同马路，路牌名称自然也必不可少。这里我就命名为“殿堂之路”吧（图2）。



这时候，马路上各类建筑都坐落于殿堂之路，因此地址也就更加完整了。比如图2中的医院地址，就是殿堂之路1号。

每座建筑都归属于殿堂之路，它们之间以门牌号区分，于是就有个数组这样的结构：

[Actionscript3] 纯文本查看 复制代码

    var 殿堂之路:Array = [];
    殿堂之路[0] = new 民房;
    殿堂之路[1] = new 医院;
    殿堂之路[2] = new 银行;
    殿堂之路[3] = new 学校;

其中，数组的名称对应路名，而数组下标0,1,2,3则刚好对应门牌号。

要寻找数组中的某个元素，在程序中，往往通过所谓的“指针”来进行定位和寻址。在马路上就表现为一辆疾速飞驰的汽车了（图3）。它由一名大脑健全的司机负责驾驶，司机的左脑代表CPU，右脑代表内存。



要找到殿堂之路上的某座建筑，司机就得先找到殿堂之路。由于偷懒，司机平时没有记住指定建筑的具体位置，而只记得殿堂之路的入口位置，所以不管他的出发点在哪里，它都会规规矩矩地开到殿堂之路的门牌处，也就是0号建筑，民房的旁边。

比如，现在要求找到银行（2号），但不需要关心开车途中都经过哪些地方，只要到达目的地就算完成任务。所以聪明的司机此时调出了地图（地图也是内存的一部分了），看一下0号和1号都是什么建筑，分别占据马路多少的长度。

民居占据了道路10米，而医院则占了18米（图4），也就是说，银行跟当前位置的距离是10+18=28米，司机算好以后，按下计程表，踩下油门，一口气前进了28米，至于民房里住的是男是女，今天医院的生意如何，他都完全无视，所以开车所花的时间特别短。



司机的时间大部分都浪费在测量和计算距离等事情上。而且，编号值越大，运算量也就越大。比如要找殿堂之路10000号（虽然门牌号到10000的情况相当罕见，但数组的长度过10000却一点都不足为奇）所在的位置，那就需要给这10000个数一个一个地加到总路程上（图5，图6）。



数组就像这样的一条马路，它可以容纳各种类型的元素，而且它们所占的字节长度可能都不一致，所以，程序想要定位到某个下标较大的元素，耗时就好长好长了。

再者，由于马路上的建筑往往缺乏统一的物业管理，因此在某些建筑需要拆迁或者转型的时候，部分门牌号就很可能会丢失，编号的连续性受到破坏，导致计算路程的时候需要额外考虑更多的外在因素。同样，数组中的索引也不连续，这多少也影响了运行效率。



下一贴：
【性能优化讨论】趣谈数组/Vector/Dictionary/链表的访问效率(2)

雪原xy

图片很形象！！大力支持！

sunarm_jk

祝11ria 越办越好