比對次數大約從 N平方降低到 N

假設, 有2個陣列的資料內容要做比對,
陣列1的資料 {1,2,3,4,5,6,7,8,9,10}
陣列2的資料 {6,7,8,9,10}

一般的資料比對的程式如下:

for(var iDataFind=0; iDataFind<array_find.length; iDataFind++){
    var j = 0;
    while (j < originalArray.length) {
        if (originalArray[j] == itemToRemove) {
            //...
            break;
        } else { j++; }
    }
}

陣列2的資料6, 總共比對 6次,
陣列2的資料7, 總共比對 7次,
陣列2的資料8, 總共比對 8次,
陣列2的資料9, 總共比對 9次,
陣列2的資料10, 總共比對 10次,

假設陣列1 + 陣列2都是 "已排序" 過的資料, 所以不需要從頭做比對, 程式如下:

var last_jPos=0;
for(var iPos=0; iPos < listSelectedArray.length; iPos++){
    var itemToDetect=listSelectedArray[iPos];
    var jPos = 0;
    if(final_array.length > 0 ){
        for(var jPos=last_jPos; jPos < final_array.length; jPos++){
            if (final_array[jPos] == itemToDetect) {
                final_array[jPos] = [final_array[jPos], 'X'].join("");
                last_jPos=jPos+1;
                break;
            }
        }
    }
}

陣列2的資料6, 總共比對 6次,
陣列2的資料7, 總共比對 1次,
陣列2的資料8, 總共比對 1次,
陣列2的資料9, 總共比對 1次,
陣列2的資料10, 總共比對 1次,

結論, 比對次數大約從 N平方降低到 N.

一般的陣列互相移除, 程式:

function array_remove_from_array(array_all, array_find){
    if(array_find.length>0){
        for(var iDataFind=0; iDataFind<array_find.length; iDataFind++){
            arrayRemove(array_all, array_find[iDataFind]);
        }
    }
}

function arrayRemove(originalArray, itemToRemove) {
    var j = 0;
    while (j < originalArray.length) {
        if (originalArray[j] == itemToRemove) {
            originalArray.splice(j, 1);
            // remove first.
            break;
        } else { j++; }
    }
}

說明: 這個可能會跑到 N平方次.

已排序過的資料, 請使用這一個副程式:

function array_remove_from_array_sorted(array_all, array_find){
    if(array_find.length>0){
        var last_jPos=0;
        for(var iDataFind=0; iDataFind<array_find.length; iDataFind++){
            var itemToDetect=array_find[iDataFind];
            for(var jPos=last_jPos; jPos < array_all.length; jPos++){
                if (array_all[jPos] == itemToDetect) {
                    last_jPos=jPos;
                    array_all.splice(jPos, 1);
                    break;
                }
            }
        }
    }
}

說明: 使用 last_jPos=jPos; 是因為 item 被移除了, 下一個 item 在比對時, 要從被移掉的位置來比對, 以上面的例子說來, 當6移掉後, 後面的 7 會移到 6的位置, 他的 index 是被移掉的位置.


我的個案是 陣列1筆數1萬筆, 陣列2筆數 5000筆, 假設你的電腦效能很好, 每1秒可以比對50萬次, 以舊方法比對需要 100秒, 改用新方法, 只需要比對1萬次, 0.02秒.