Shell&JS: 簡單的集合運算

簡單的集合運算

結論:

// A 與 B 目錄下的檔案
> ls A B
// A:
// apple  book  can  cup  chair
// 
// B:
// book  cup  dog  hat  table
//

// 交集: A&B
> (ls A;ls B) | sort | uniq -d 
// book
// cup

// 聯集: A|B
> (ls A;ls B) | sort | uniq 
// apple
// book
// can
// cup
// chair
// dog
// hat
// table

//差集: A-B , 注意 `ls B` 重複兩次, 不是筆誤.
> (ls B;ls B;ls A) | sort | uniq -u
// apple
// can
// chair

//對稱差: A^B = (A-B)|(B-A), A^B = (A|B)-(A&B)
> (ls A;ls B) | sort | uniq -u
// apple
// can
// chair
// dog
// hat
// table

廢話:

集合在數學中占有很大的分量, 但基礎是簡單的. 在程式中也經常需要用到. 使用程式語言時, 只要使用 for 跟 if, 應該就能簡單的達成交集, 聯集和差集的運算. 但有時候特地去寫程式之類, 還是算了吧.

在 shell 中利用 sort 跟 uniq 也能達成簡單的集合運算. 以下分別舉例來說明如何達成集合最基本的運算.

正文:

• 交集: 兩個集合中相同的元素. 使用 JS 陣列時, 可以如下處理,

var A = ['apple', 'book', 'can', 'cup', 'chair'];
var B = ['book', 'cup', 'dog', 'hat', 'table'];
var S = [];

for (var i = 0; i < A.length; i++){
    var p = A[i];
    for (var j = 0; j < B.length; j++){
        var q = B[j];
        if (p == q) {           
            S.push(q);
            break;
        }
    }
}
console.log(S);
// [ 'book', 'cup' ]

同樣的假設 A 和 B 目錄下各有數個檔案. 如下, A 有 ‘apple’, ‘book’, ‘can’, ‘cup’, ‘chair’ B 有 ‘book’, ‘cup’, ‘dog’, ‘hat’, ‘table’ 使用 shell 指令來處理,

> (ls A;ls B) | sort | uniq -d
// book
// cup

使用 sort 是因為 uniq 的輸入必須是已經被排序的. 如果給 uniq 一個不是排序的資料, 將會得到錯誤的結果. 且 uniq -d 是列出重複的資料. 整個命令的意思是說: 列出A目錄跟B目錄下的檔案, 把他們放在一起, 丟給sort排序, 然後再列出重複的資料.

利用同樣的思路, 改用 JS 來處理, 如下

var A = ['apple', 'book', 'can', 'cup', 'chair'];
var B = ['book', 'cup', 'dog', 'hat', 'table'];
var X = A.concat(B);
var S = {};

for (var i=0; i< X.length; i++){
    S[X[i]] = (S[X[i]] || 0) + 1;    
}
// 上面的 JS 以計算重複次數代替判斷重複, 需要遍歷整個陣列 X,
// 所以有無排序不影響結果.

for (obj in S){
    if (S[obj] > 1) {
        console.log(obj);
    }
}
// book
// cup

• 聯集: 有出現在兩個集合中元素.

var X = A.concat(B);
var S = {};

X.forEach(function(obj){
    S[obj] = (S[obj] || 0) + 1;
});
// 改用 Array 的 `forEach` 方法來計算重複次數

for (obj in S){
    console.log(obj);    
}
// 因在計算重複次數時, 已將相同的元素合併計算次數, 
// 所以只要將 S 的所有元素印出, 即可.
// apple
// book
// can
// cup
// chair
// dog
// hat
// table

而使用 shell 指令來處理, 就更簡單, 只要下 (ls A;ls B) | sort | uniq 就行了.

• 差集: 有出現在其中一個集合並不出現在另一個集合的元素. 下面是可用的 JS 程式碼,

var S = [];

for (var i = 0; i < A.length; i++){
    var p = A[i];
    S.push(p);
    for (var j = 0; j < B.length; j++){
        var q = B[j];
        if (p == q) {                       
            S.pop();
            break;
        }
    }
}
console.log(S);
// [ 'apple', 'can', 'chair' ]

實作上程式的邏輯有許多方式, 這裡採用先將 A 陣列的元素放入一個容器後, 再用迴圈判斷是否存在 B 陣列中, 如果存在就再將他移出的. 好處是可以省去使用判斷是否存在 B 陣列旗標.

在 Shell 中, 要達成差集必須要有一點巧思. 我們知道差集是 A 集合減去 B 集合剩下來的元素, 所以該差集 不會 包含 B 集合的元素. 而利用uniq -u 可以列出不重複的資料, 故 (ls B;ls B) | sort | uniq -u 應該不會傳回任何資料, 因為 B 目錄下的檔案全部被重複了兩遍. 同理, 當使用(ls B;ls B;ls A) | sort | uniq -u 時, 傳回的就會是 A 目錄中不與 B 重複的檔案. 因為 A 跟 B 重複的元素, 必定也是 B 的元素, 而已經重複兩次 B 元素再加 A 重複 B 的元素還是重複, 都會被 uniq -u 消除掉. 所以在這裡 ls B 要重複兩次. 如果只是單純的(ls B;ls A) | sort | uniq -u 則會列出 A 和 B 目錄下的不重複的檔案. 也就是 A 目錄下的檔案加上 B 目錄的下的檔案再減去 A 和 B 目錄下都有的檔案, 也就是 A 跟 B 的對稱差.

根據這個思路, 改寫 JS 如下,

var X = A.concat(B).concat(B);
var S = {};

X.forEach(function(obj){
    S[obj] = (S[obj] || 0) + 1;
});

for (obj in S){
    if (S[obj]==1) {
        console.log(obj);    
    }
}
// 印出只出現一次的元素
// apple
// can
// chair

其實, 集合的運算是可以類比如位元的運算. 重新整理上面的案例, 將資料整理, 賦予每一個元素一個數值, 如下,

// apple=1, book=2, can=4, cup=8, chair=16, dog=32, hat=64, table=128;
// A = ['apple', 'book', 'can', 'cup', 'chair'] => [1, 2, 4, 8, 16]
// B = ['book', 'cup', 'dog', 'hat', 'table'] => [2, 8, 32, 64, 128]

//將 A, B 改用數值表示
  var A = 1 + 2 + 4 + 8 + 16;
// A, 十進位:  31,  二進位: 1 1111

  var B = 2 + 8 + 32+ 64+ 128;
// B, 十進位: 234,  二進位: 1110 1010

// 交集: A&B
  var x = A & B;
// 10  
// 十進位:  10,  二進位: 1010
// 10 => 2 + 8 => book, cup

// 聯集: A|B
  var x = A | B;
// 255
// 十進位:  255,  二進位: 1111 1111
// 255 => 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 
// => apple, book, can, cup, chair, dog, hat, table

// 差集: A-B?
  var x = (A|B) - B;  
// 21
// 十進位:  21,  二進位: 0001 0101
// 21 => 1 + 4 + 16 => apple, can, chair
// A集合去掉B集合的元素可表示為 A 與 B 的聯集(A|B)再去掉 B 集合, 
// 這樣就只會剩下沒有 B 集合元素的 A 集合元素.
// 這裡沒辦法直接 `A-B` 是因為若有一 B 集合元素不在 A 集合中, 
// 則會變成空集合減扣掉某一元素, 在這邊就沒辦法正確表示.

// 對稱差: A ^ B
  var x = A ^ B;
// 245 
// 十進位:  245,  二進位: 1111 0101 
// 245 = 1 + 4 + 16 + 32 + 64 + 128 =>apple, can, chair, dog, hat, table

不過 JS 的位元運算並不像 C 語言一樣有較高的效率. 雖說在運算上簡單不需要迴圈, 但要將結果轉回對映的元素, 仍要進行一串二進位運算. 總的來說, 程式碼也不算特別簡潔. 不過, 在一些特殊的運用場合仍有其用途.

所以集合運算可對應位元運算如下,

• 交集: A&B, and 運算.
• 聯集: A|B, or 運算.
• 差集: (A|B)-B, 特殊條件下的減法運算.
• 對稱差: A^B, xor 運算.