[转]Flash高性能开发基础系列―数据容器

http://uh.9ria.com/space-109929-do-blog-id-7583.html

这节内容其实是AS版数据结构与算法,在AS中性能瓶颈在主要渲染,所以大部分开发人把优化精力放在渲染从而忽略在数据层的优化。不同的数据组织（数据结构）直接影响你的数据操作效率,在大多量语言中都提供丰富的对象容器，比如java中的Set,Map,Array,Queue等等，其中封装了大量的针对于某种数据结构的操作方法,从而大大提高了数据操作效率和开发效率，在as3中内置的线性结构只有Array一种，大家也别无选择。在数据量不是很大的时候数组和其它数据结构的差异体现的不是很明显,但是如果你对大量数据进行删除和插入,这时候你的可能需要考虑其它的数据结构，比如:链表。

我们来了解一个不同的数据结构有什么不同的特性，如果你大学学的数据结构没有遗忘的话你可以不用看这一段文字。任何一种存储结构都有他的优点和缺点.下面我们来具体的特性:

数据结构	优点	缺点
数组	随机存储快	查找和删除慢
有序数组	相对无序查找快	删除和插入慢
栈	后进先出方式操作很快	其它操作慢
队列	先进先出方式操作很快	其它操作慢
链表	删除和插入快	查找慢
二叉树	删除和插入,查找都很快	如果非平衡就很慢
堆	对最大数据项删除和插入很快	其它很慢

 

AS3没有内置这些数据结构,但是我们可以选择第三方库,最著名的就是国外一个人写的polygonal，但是polygonal存在一些严重问题，我的有一篇日志详细说明(http://uh.9ria.com/space-109929-do-blog-id-7310.html),我们采用另一款数据结构库ASDS做demo(这里下载http://code.google.com/p/dsforas/)。

    我来举一个简单的游戏实例来说明游戏中数据组织的重要性,假如我们在斗地主游戏中服务器给我们发牌或出牌我们必须保证手中的牌都是有须的，如3,4,5,6,........;我们一般的做法只就是将所有的牌存在一个数据中，然后将向数组中进行插入数据。

 public function insert(index:uint,o:*):Void{

            var size:int=_array.length;

          if(index>size) return;

          for(var i:int=size;i>index;i--){

              _array[i]=_array[i-1];

          }

         _array[index]=o;

}

在数组中每做一次插入是将插入位置以后的数据向后移动腾出空间后再写入指定数据,在移动数据的过程中消耗了大量时间。

 

 

假如我们采用链表的存储方式,由于链表(如果不知道什么是链表可以去百度是查一下，我这里不重复)的结构特性所以插入效率非常高，具体的我看图吧.

 

 

以上只是理论，我们来做一个效率测试吧.

package {

       import asds.list.LinkedList;

       import flash.display.Sprite;

       public class Demo extends Sprite{

            private var _array:Array=[]

            private var _linked:LinkedList=new LinkedList(10000);

            public function Demo(){

                for(var i:int=0;i<10000;i++){

                    linked();

                    array()

                }

            }

            private function linked():void{

                _linked.addAtFirst(0);

            }

           private function array():void{

               insert(0,0);

           }

           public function insert(index:uint,o:*):void{

               var size:int=_array.length;

              if(index>size) return;

              for(var i:int=size;i>index;i--){

                  _array[i]=_array[i-1];

              }

            _array[index]=o;

        }

   }

}

以上是一个插入测试,分别对数组和对链表进行1w次插入0到0位置,在profile中可以看到调用array()和linked()消耗总时间分别为24980毫秒和102毫秒,做这种操作linked快24倍(大家可以自行测试，不同的电脑硬/软件环境测试的结果可能不一样)。

以上对数据结构所讲的非常浅,如果大家要深入的学习数据结构，请买一本书好好研究一翻,这篇文章的目的是呼吁大家重视数据结构基础的学习。在我对我面试的一些人和身边的同事中了解得知大部分人对这些基础知识学习和使用经验非常少.如果要把握工程的整体性能，就应该把握好每个环节,并不是在某些方面做的非常突出，而在某些方面又做的不好，从而造成性能瓶颈。

Flash高性能开发基础系列 ― 内存篇【上】

Flash高性能开发基础系列 ― 内存篇【下】