11RIA 闪客社区 - 最赞 Flash 论坛

搜索
查看: 136|回复: 2
上一主题 下一主题 打印

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

[复制链接]
发表于 2019-1-10 15:32:22 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 TKCB 于 2019-3-19 09:11 编辑

转载:9RIA游戏开发者社区(天地会)
作者:iloveas(大神)


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



(续上)

如果在汽车位于第N座建筑的时候,可以有一个方法直接前行到第N+1座建筑的话,那么汽车的运行效率一定可以得到很大程度的提升。所以这时候,我们希望能在第N座建筑中记录下第N+1座建筑到当前点的距离(图 13)。

QQ截图20190110152602.png

把这些信息连成一条线,就形成了链条状的结构(图 14),所以这样的集合类型有个很形象的名称——链表,虽然它不是AS3的内置类,但我们完全可以自己实现它。

QQ截图20190110152640.png

链表的特征就是其中的每个元素都记录着下一个元素的位置,所以它在遍历的过程中可以直接定位到下一元素,而无需像数组/Vector那样,每次循环都要重新回到马路的入口。

如果当前对象的下一个元素为空,那就意味着链表已经到达末尾,遍历完成(图 15)。


QQ截图20190110152705.png

有时候我们需要反向遍历,那我们就可以把上一个元素的位置都记录下来,从而形成双向链表(图 16)。

QQ截图20190110152742.png

如果想实现折返功能(即到达末尾的时候回到第一个对象),那么就可以将最后一个对象的下一元素指向到链表的开头,从而得到环状链表的效果(图 17,这个图有点偷懒了,没做好)。

QQ截图20190110152829.png

下面我引用某高手用AS3实现的链表代码。首先要有一个链表类:

[Actionscript3] 纯文本查看 复制代码
public class LinkedList {

    public firstNode:*;

    public function LinkedList() {

    }

}


然后链表中的每个元素都包含上一个和下一个的引用:

[Actionscript3] 纯文本查看 复制代码
public var nextNode:*;

public var prevNode:*;


具体的遍历代码可参阅下面的链接:

http://bbs.9ria.com/thread-55240-1-1.html(已失效)

不过,就我贴出来的代码而论,这个链表结构显然在类型转换方面存在一定的性能问题。不过作为一个通用的链表类,使用泛型也是仅有的办法。

在实际项目开发中,你可以按照这样的思路实现固定类型的链表:

[Actionscript3] 纯文本查看 复制代码
public class MySpriteLinkedList {

    public firstNode:MySprite;

    public function LinkedList() {

    }

}


[Actionscript3] 纯文本查看 复制代码
public class MySprite extends Sprite{

  public var nextNode:MySprite;

  public var prevNode:MySprite;

}


经过这样的优化以后,类型转换的效率就可以提高很多了,但是它只能构建元素类型为MySprite的链表,如果想要换成其他的类,那你还得按照上面的写法重新给别的类再写一遍,相当麻烦,这让我感到灰常蛋疼,如果能给我们自定义像Vector那样的类,比如LinkedList.<T>,那该有多完美啊!

可见,链表在遍历寻址和类型转换方面优化得相当不错,它充分吸取了Array和Vector最最精华的地方。

至于push/unshift一类的操作,链表类也能实现,而且效率绝对优于Array/Vector,因为操作都是简单的引用更改。我上面给出的链接已包含相关代码,这里就不再重复了。

不过,链表也并不是个万能的数据结构,因为它已经没有编号的概念了,所以,想要单独访问链表中的某一个元素,比如第5个的时候,就需要在AS层循环4次才能获得,如果编号值较大,那么访问的效率就反而不如Vector和Array了。

此外,for each...in形式的遍历可能在寻址方面已经做了一些针对性的优化操作(这估计也是导致在遍历里删除元素后,数据访问出错的原因之一),不过具体机制我还没搞清楚,欢迎各位发表下自己的看法。

所以在项目开发中,我们应根据实际情况,选择最合适的数据类型,如果1种类型无法兼顾多方面的优势,那大家还可以把它们结合在一起。举个栗子,比如一组元素既要进行遍历又要对个别元素进行访问,那么就可以把这批元素同时推入到链表和数组中,从而让各方面的执行效率都达到最优的状态。

(完)


最后,发出一个高清的 PDF版本(包含1-4片帖子的所有内容),喜欢的请收藏:
趣谈数组-Vector-Dictionary-链表的访问效率.pdf (1.15 MB, 下载次数: 0)
发表于 2019-1-10 18:29:11 | 显示全部楼层
真不容易!点赞!!支持!!!
回复 支持 反对

使用道具 举报

发表于 2019-1-11 02:15:32 | 显示全部楼层
写的很好!
回复 支持 反对

使用道具 举报

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

本版积分规则

感谢所有支持论坛的朋友:下面展示最新的5位赞助和充值的朋友……更多赞助和充值朋友的信息,请查看:永远的感谢名单

陈近南(65)、 542504578@qq.co(913)、 xxdmx712(19)、 流连弹(2217)、 jiqingxing(1707)

下面展示总排行榜的前3名和今年排行榜的前3名的朋友……更多信息,请查看:总排行榜今年排行榜

1367926921(962)、 MSANYL(1106)、 动画scz(1955)、 xxdmx712(19)

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