How to Compare Two Array

以下轉自ptt flash版

作者  cjcat2266 (CJ Cat)                                         看板  Flash
 標題  Re: [問題] 我想比較兩個陣列的不同?
 時間  Sat Oct  9 21:02:33 2010
───────────────────────────────────────

※ 引述《kaiyine (yumi)》之銘言：
: 陣列a是5,2,6,8,4
: 陣列b是0,1,2,3,4,5,6,7,8,9,10
: 我要如何列出陣列a缺少0,1,2,3,7,9,10呢?

這就是"集合"的問題了
同上一篇回文所說的，可以用associative array
(如果是AS3就可以用Dictionary class，相當於C++的map class)

其實可以更簡短的寫
(以下code未經過測試，可能有錯字)

        var a:Array = [5, 2, 6, 8, 4];
        var b:Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

        //集合物件
        var obj:Object = new Object();

        var i:Number, len:Number;

        //讓a的元素作為key，跟true值產生關連

        for (i = 0, len = a.length; i < len; ++i) {

                obj[a[i]] = true;

        }

        //尋找"a沒有，b有的元素"

        for (i = 0, len = b.length; i < len; ++i) {

                //若obj[b[i]]沒有關聯值，那就是undefined，!undefined == true

                if (!obj[b[i]]) {

                        trace("a沒有含" + b[i]);

                }

        }

==========================================================

作者  etrexetrex (moonet)    

也可以存 inverse A，不過其實是一樣的

多花了點記憶體，得到了一些加速

假設：

  A陣列中沒有重複出現相同的值

程式：

var i:Number;

var a:Array = [5, 2, 6, 8, 4];

var b:Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

var aLength : Number = a.length;

var bLength : Number = b.length;

//建立A的反向表 此處inverseA的型態是陣列

var inverseA:Array = [];

for (i = 0 ; i < aLength; i++ )

    inverseA[a[i]] = i;

var inverseALength : Number = inverseA.length;

//多花的記憶體在 inverseA

trace("aLength = " + aLength);                  //aLength = 5

trace("bLength = " + bLength);                  //bLength = 11

trace("inverseALength = " + inverseALength);    //inverseALength = 9

//尋找"a沒有，b有的元素"

for (i = 0; i < bLength; i++ )

{

    //加速在這裡

    if(b[i] >= inverseALength)

        trace("a沒有含" + b[i]);

    //基本上 Array 的存取也會比 Object 快些

    else if(inverseA[b[i]] == undefined)

        trace("a沒有含" + b[i]);

}

為了確認Array 的空值是 undefined

只好打開 flash cs4

所以上面的程式已經測過了

========================================================

作者  cjcat2266 (CJ Cat)   

※ 引述《etrexetrex (moonet)》之銘言：

:     //加速在這裡

:     if(b[i] >= inverseALength)

補充說明一下

其實這裡不一定會完全加速喔

:     //基本上 Array 的存取也會比 Object 快些

要看你的array是不是sparse array

意思就是你是否每一個element都有明確給值

一個Array物件內部底層其實分成一個陣列和一個binary search tree (dictionary)

從第0個開始的元素到最後一個連續的元素，是存在陣列

剩下的元素則是存在binary search tree裡面

這樣才不會浪費記憶體去存取undefined元素

如以下的code

        a[0] = 0;

        a[1] = 1;

        a[2] = 2;

那麼三個連續元素是儲存在底層陣列沒錯

存取起來速度會很快

但是以下code

        a[0] = 0;

        a[10] = 1;

        a[12] = 2;

只有a[0]是存在底層陣列

a[10]和a[12]是存在底層的binary search tree

存取起來的效能量級就是跟Object和Dictionary一樣的

再如

        a[10000] = 1;

所消耗的記憶體不是10000個Number

而是只有一個Number而已，是用底層的binary search tree在存

所以如果真的要龜毛

你應要一開始把aInverse的所有元素都先初始化成-1或其他值

才可以真正得到array效能上的優勢

我記得以上豆知識是在Senocular的blog上看到的 :)

p.s. 我找不到Spare Array 在AS3的底層是以BST實作的證實.