11RIA 闪客社区 - 专注Flash技术,做全球最大的Flash AS AIR及周边技术开发者社区

搜索
查看: 30|回复: 0

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

[复制链接]

签到天数: 6 天

连续签到: 1 天

发表于 2019-1-10 15:23:38 | 显示全部楼层 |阅读模式

【游客模式】——注册会员,加入11RIA 闪客社区吧!一起见证Flash的再次辉煌……

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 9RIA天地会2017 于 2019-1-10 15:36 编辑

转载: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)。

QQ截图20190110152055.png

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

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


QQ截图20190110152133.png

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不难看出,汽车在遍历的过程中做了不少无用功。


QQ截图20190110152308.png



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


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /2 下一条

感谢所有支持论坛的朋友(下面展示最新的5位捐款和充值的朋友……更多捐款和充值朋友的信息,请查看:时空传送门

sunarm_jk(49)、心羽(20)、雪原xy(1120)、z420013294(66)、1975655892(1296)

快速回复 返回顶部 返回列表