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

iloveas

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


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



（续上）

类似的还有unshift，这俩方法有时真心让我纠结——Adobe的编译器怎么就不能做完善点，这种错误在编译前检测一下，对你们来说也不会太麻烦吧，估计也就多个元素同时被push/unshift的时候要做的事情多一点。好吧，都怪我多嘴，连编译器机制都没搞清楚，我还瞎扯个毛啊。

用草鱼塘[草鱼塘.length – 1]代替push可以一定程序上提高效率，但是length属性也是个高级方法，所以执行的耗时也比较长。如果有变量记录着当前的长度（比如前面for循环的i变量），那么直接使用自定义变量作为下标将是最佳的选择。

综上所述，Array和Vector都有一定的缺陷，所以在实际应用中的局限性有点大。

Vector寻址的优势只在简单数据类型中才能有所体现，但诸如Vector.<Sprite>这样的集合，想用简单类型来替代，往往都不太现实，这种情况下，无论使用Array还是Vector都相当蛋疼，Vector的push和shift比Array慢，但Array在类型检测方面又不如Vector，鱼与熊掌难以兼得。

绕了这么久，其实最最关键的问题还在于寻址方面的效率。于是司机勉为其难地在地图上记录下每座建筑的具体位置，也就是建筑到马路入口处的距离（图 10）。



这就是典型的以内存换CPU的思想，在GPU加速诞生之前，AS3开发人员都倾向于用此法实现性能方面的优化，毕竟跟CPU相比，内存实在是太便宜了。

这个集合在AS3中也有内置的类，它就是大家所熟知的Dictionary（最原始的Object也勉强算这类型吧），用内存记录下每个元素的地址以后，门牌号可以不是连续的数字了，它甚至可以是字符串乃至复杂类型所构建的对象（图 11）。




PS：Array也可以用字符串来做Key，但笔者尚未搞清楚（或者说臆测到）底层的实现机制。

本以为自己的内存换CPU理论已经天衣无缝，没有半点破绽。直到某高手对我的这一观点表示高度质疑以后，我才恍然大悟——他说既然我认为内存把每栋楼的位置都记录下来了，那这些位置的信息都存储在什么地方？总不可能直接标在建筑上面吧，因为你都还没找到这座楼，又怎么能看见标注在它上面的位置信息呢？

因此，每座楼的位置信息都必须在马路的入口处就能获取得到，所以我们需要一个Array或者Vector进行记录。但由于门牌号可以不连续，且能容纳复杂类型，所以Vector需要排除。而使用Array的话，又要重新面对数组的性能问题。

笔者后来专门查阅了Java里面的Dictionary源码，结果让我彻底惊呆了——Dictionary的底层实现原来还是基于数组，key（门牌号）和value（具体位置）的映射居然还需要通过遍历数组的方法才得以实现。

如果AS3底层的实现机制也是如此，那么Dictionary就真要跪倒在Array和Vector之下了。不过经笔者测试，Dictionary的效率并没有想象中的差。究其原因，可能是AS3底层的实现机制跟Java的Dictionary不甚一致，也可能只是底层遍历的效率比AS3表层要高一些的缘故。但由于笔者并未阅读过AVM2的源码，所以此处不敢轻易下结论。欢迎有兴趣的朋友跟笔者一起探讨这一问题。

抛开寻址机制不说，Dictionary还有一个严重的缺陷，就是不能指定元素的类型，因此Dictionary一样存在无法突破的性能瓶颈。

PS：这方面Java的Dictionary就做得比AS3好，而且还支持给Key设置类型。

至此，AS3中常用的集合类型的寻址与类型转换就介绍得差不多了，下面讲一下遍历。

跟单个对象寻址的汽车相比，遍历更像一辆旅游观光巴士。为了令沿途风光尽收眼底，司机有意把车速放慢，但就始终保持着前进的状态。

然而，如果用数组/Vector的飞车模式来遍历，那么指针的走向将会让人哭笑不得，因为在数组/Vector的寻址过程中，无论车的当前位置在哪里，它都要先回到马路的出口处才能继续寻找下一个对象。从图 12不难看出，汽车在遍历的过程中做了不少无用功。






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