簡單的集合運算
結論:
// 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 運算.
