【游客模式】——注册会员，加入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）。
把这些信息连成一条线，就形成了链条状的结构（图 14），所以这样的集合类型有个很形象的名称——链表，虽然它不是AS3的内置类，但我们完全可以自己实现它。
链表的特征就是其中的每个元素都记录着下一个元素的位置，所以它在遍历的过程中可以直接定位到下一元素，而无需像数组/Vector那样，每次循环都要重新回到马路的入口。
如果当前对象的下一个元素为空，那就意味着链表已经到达末尾，遍历完成（图 15）。
有时候我们需要反向遍历，那我们就可以把上一个元素的位置都记录下来，从而形成双向链表（图 16）。
如果想实现折返功能（即到达末尾的时候回到第一个对象），那么就可以将最后一个对象的下一元素指向到链表的开头，从而得到环状链表的效果（图 17，这个图有点偷懒了，没做好）。
下面我引用某高手用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, 下载次数: 3)
| 
/1 
发表于 2019-1-10 15:32:22
提升卡
置顶卡
变色卡
千斤顶
发表于 2019-1-10 18:29:11
发表于 2019-1-11 02:15:32