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

iloveas

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


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




（续上）

不过，并非所有的路边建筑都分布得如此错落有致。比如像图 7那样的住宅小区，只要开发商不在布局方面搞啥创意的话，每栋楼的宽高就能保持基本一致，而且间距也相等。



对于那个有点偷懒又似乎有点小聪明的司机来说，这次的路程计算就轻松多了，知道每幢楼之间都占地15米，那10000号就在距离0号10000*15=150000米处的位置，比逐个相加要快N多倍了。

于是，AS3引入了可指定元素类型的数组Vector：

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

var 天堂之路:Vector.<楼房> = new Vector.<楼房>;
天堂之路[0] = new楼房;
天堂之路[1] = new楼房;
天堂之路[2] = new楼房;
天堂之路[3] = new楼房;

你不可以写成

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

天堂之路[2] = new 医院;

否则代码在编译的时候就报错。

由于每座大厦所占用的字节数相等，所以访问地址的时候，就可以像司机刚才那样，做一道乘法计算题即可，所以它的访问速度比数组要快得多。

不过事实往往没有这么简单，就算同为大厦，它们的占地面积也不一定相等（而且这种情况还占绝大多数），此外，用各种变相的方式，也可以把类型不甚一致的元素统一起来：

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

var 天堂之路:Vector.<建筑> = new Vector.<建筑>;
天堂之路[0] = new 民房;
天堂之路[1] = new 医院;
天堂之路[2] = new 银行;
天堂之路[3] = new 学校;

所有元素都是建筑的子类，所以以上的Vector创建成功，但是用乘法来定位在这里已经不好使了。

笔者可以大胆地说，在AS3中，大部分的数据类型都不等长。比如Sprite，你可以在graphics绘制很多很多的矢量图形，还能用addChild添加好多好多的子对象，所以不同的Sprite，占用的字节数一般都不同。此外，可以被继承的类也不可能保证长度固定。同理，接口也不能用来构建等长的Vector。

综上所述，要保证Vector内的元素有固定的占用空间，就要保证类型是个类，而且不能被继承。那什么类不能被继承呢？就是加入了final修饰的类。

然后，这个类也不能太复杂，比如刚才提到的Sprite，即使加了final标记，它的占用空间也要视Sprite的具体内容而定。所以在AS3中，只有除String以外的简单数据类型（简单or复杂，这定义业界似乎一直都有争议），比如int，Boolean，Number等，才能在寻址方面提升效率。

这就可以解释为什么Stage3D中的那些顶点缓冲，索引缓冲等信息都要以Vector.<Number>或者Vector.<int>来存储了，本来用Vector.<Point>这样的类型可以很大程度上提高可读性并降低查错难度，但Stage3D本身就为性能而生，所以一切都以执行速度优先。

另外像Flash10推出的drawTriangles，drawPath等函数也采用了类似的方式，不过考虑到这些绘图API并未受到太多的关注，我就不给大家啰嗦了。

Vector跟数组另一个区别就在于Vector的索引始终连续，这是保证乘法运算寻址成功的另一个必要条件。

尽管Vector在大多数类型面前发挥不出寻址方面的优势，我们也仍然提倡多用Vector，除了代码提示好很多以外，Vector固定的类型也有助于提升程序的执行速度。

现在不探讨地址定位的问题了，所以我换一个例子。

假设有两个鱼塘，一个塘的鱼种类繁多，而另一个则是清一色的草鱼，可见前者用数组存储较为合适，而后者则是Vector.<草鱼>。

现在要求你从这两个塘里分别钓出一条草鱼，显然，在鱼的反侦查能力和密度都相近的情况下，第一个鱼塘里钓出草鱼的难度要大很多，因为即使给你钓到了，你还要检查一下钓回来的是不是草鱼，不是的话就还得重新钓过（图 8），在运行的时候吗，遇到这样的情况就直接报错。




至于第二个塘，钓起来就轻松多了，只要有鱼上钩，那就一定是草鱼（图 9）。因为这个塘只允许草鱼的存在，你可以假设人们在投放到该鱼塘之前都仔细地检查过每一条鱼了。而Vector确实具有这样的特性。




也就是说，Vector不需要在运行的时候再次检查类型，因为编译器已经帮我们检查好了，而检查类型也比较耗时，所以改用Vector后，运行的速度会有所加快。即使寻址方面两者无太大的差别，Vector的效率还是比Array高出不少：

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

var 鱼塘:Array = [];
鱼塘.加入100条鱼
var 一条草鱼:草鱼 = 鱼塘[int(Math.random() * 100)];
var 草鱼塘:Vector.< = [];
草鱼塘.加入100条草鱼
var 一条草鱼:草鱼 = 草鱼塘[int(Math.random() * 100)];

如前所述，用下标赋值的方法给Vector添加元素，编译器会检查数据类型：

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

for(var i:int = 0; i < 100; i ++)
{
  草鱼塘 = new 草鱼; //编译器会检查赋值的类型是否为草鱼
  草鱼塘 = new 鲤鱼; //编译器会抛出错误，从而避免运行时重复检测
}

但灰常蛋疼的是，Vector的一些方法没有做严格的类型检测，比如用push就可以逃过编译器的法眼，偷偷地在草鱼池里投放其他物种：

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

for(var i:int = 0; i < 100; i ++)
{
  草鱼塘.push(new 鲤鱼); //编译器不抛错
}

编译通过之后，检查的工作就交给播放器在运行的时候来做了，所以Vector的push每次都要判断类型，执行效率就被拖慢了，所以Array的push方法反而比Vector快，因为Array无视类型，啥样的鱼投进来它都不关心。



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