Frank's Blog

最近看了些文章, 剛好看到一個還不錯的演算法
相信許多人曾經有過把一些東西存在容器或是陣列裡頭
然後要一一比對是內容是否與該容器裡頭的任一個相同
通常比較常見的, 是用雙迴圈(巢式)來處理掉它,
但…. 往往這個過程會付出二倍以上的效能
在一個容器裡頭, 裝了 6 個物件
分別要比對這 6 個物件, 或許我們常看到的做法是像這樣

object_length = 6;

for(i=0; i<object_length; i++) {

    objA = objAry[i];

    for(j=0; j<object_length; j++) {

        objB = objAry[j];

        if(objA == objB) {

            // 比對相同時, 處理的程序

        }

    }

}

上述的作法, 看來似乎很合理, 總共需執行 6 * 6 = 36 次的比對分析
但… 事實上存在了二個大問題
1. 是否該與自己比對 ?
2. i=1, j=2 比對完後, i=2, j=1 是否該再比對一次 ??
倘若考慮到這二個問題的話, 接下來我們分別一個一個處理掉它 !!

當程式一進入時, i=0, j=0, 就會先遇到第一個問題點 『自己與自己比對』
既然我們不需要與自己比對, 所以程式可修正成如下

object_length = 6;

for(i=0; i<object_length; i++) {

    objA = objAry[i];

    for(j=0; j<object_length; j++) {

        objB = objAry[j];

        if(i != j && objA == objB) {

            // 比對相同時, 處理的程序

        }

    }

}

如此一來, 我們已先減掉了 6 次的與自己比對, 剩下 30 次的比對方式
底下是執行的結果
obj0 with obj1, obj2, obj3, obj4, obj5
obj1 with obj0, obj2, obj3, obj4, obj5
obj2 with obj0, obj1, obj3, obj4, obj5
obj3 with obj0, obj1, obj2, obj4, obj5
obj4 with obj0, obj1, obj2, obj3, obj5
obj5 with obj0, obj1, obj2, obj3, obj4

但… 上述的結果還是比對太多,
原因是 obj0 with obj1 跟 obj1 with obj0 是相同的結果, 不需要再重複進行比對一次
我們所需要的結果應為如下
obj0 with obj1, obj2, obj3, obj4, obj5
obj1 with obj2, obj3, obj4, obj5
obj2 with obj3, obj4, obj5
obj3 with obj4, obj5
obj4 with obj5
obj5 with nothing !!

所以我們最終的程式修改成如下

object_length = 6;

for(i=0; i<object_length-1; i++) {

    objA = objAry[i];

    for(j=i+1; j<object_length; j++) {

        objB = objAry[j];

        if(objA == objB) {

            // 比對相同時, 處理的程序

        }

    }

}

最後程式的比對運算只剩 15 次, 比一開始的 36 次比對
足足少了一半之多, 這也是剛說為什麼會付出 2 倍以上的時間的意思了 !!