配列で順序を保ったまま集合算をする
「JSの配列で集合算を考えてみた - IIJIMASの日記」の続きです。
配列が2つ与えられたとき、重複を省きつつ、和集合、共通部分、差集合などを表す配列を計算するアルゴリズムで、ループ回数をなるべく少なくしたものを考えます。
以前のエントリのやり方だと、順序が保存されないので、今回は順序が保存されるのを考えてみました。とりあえず考えたアルゴリズムでは対称差(XOR)だけ余計にループが必要となってしまいました。それ以外は、ループは2回で済みます。冒頭部分の演算によって引数の順番を交換しているところは、再帰で書いた方がすっきりするかもしれませんがわかりにくくなると思います。
//演算の種類を表す定数。値に意味はなし、互いに異なればOK MathSet.Operator.Union = 1; MathSet.Operator.Intersection = 2; MathSet.Operator.DiffLR = 3; MathSet.Operator.DiffRL = 4; MathSet.Operator.SymmDiff = 5; MathSet.OperationWithOrdering = function (arrayA, arrayB, operator) { var set = {}; switch (operator) { case MathSet.Operator.DiffLR: case MathSet.Operator.Intersection: case MathSet.Operator.SymmDiff: a1 = arrayB; a2 = arrayA; break; case MathSet.Operator.Union: case MathSet.Operator.DiffRL: default: a1 = arrayA; a2 = arrayB; } var val; var newArray = []; for (var i = 0; i < a1.length; i++) { val = a1[i]; if (set[val] == null) { set[val] = 1; if (operator == MathSet.Operator.Union) { newArray.push(val); } } } for (var j = 0; j < a2.length; j++) { val = a2[j]; if (set[val] == 1) { set[val] = 3; if (operator == MathSet.Operator.Intersection) { newArray.push(val); } } else if (set[val] == null) { set[val] = 2; if (operator != MathSet.Operator.Intersection) { newArray.push(val); } } } if (operator == MathSet.Operator.SymmDiff) { for (var i = 0; i < a1.length; i++) { val = a1[i]; if (set[val] ==1) { set[val] = 4; newArray.push(val); } } } return newArray; };
以下のように使用します。(exec()をボタンのonclickなどで指定して、クリックで実行します。)
function exec() { result = ""; result += "arrayA:\t"; result += A; result += "\r\n"; result += "arrayB:\t"; result += B; result += "\r\n"; result += "\r\n"; result += "A∪B:\t"; result += MathSet.OperationWithOrdering(A, B, MathSet.Operator.Union); result += "\r\n"; result += "A∩B:\t"; result += MathSet.OperationWithOrdering(A, B, MathSet.Operator.Intersection); result += "\r\n"; result += "A-B:\t"; result += MathSet.OperationWithOrdering(A, B, MathSet.Operator.DiffLR); result += "\r\n"; result += "B-A:\t"; result += MathSet.OperationWithOrdering(A, B, MathSet.Operator.DiffRL); result += "\r\n"; result += "XOR:\t"; result += MathSet.OperationWithOrdering(A, B, MathSet.Operator.SymmDiff); result += "\r\n"; alert(result); }
結果:
arrayA: 100,3,1,2,3,2,1 arrayB: 8,12,6,2,3,5,6,3,2 A∪B: 100,3,1,2,8,12,6,5 A∩B: 3,2 A-B: 100,1 B-A: 8,12,6,5 XOR: 100,1,8,12,6,5
結果(順序が保存される)
同じ入力で以前のエントリのアルゴリズム(順序が保存されない)
もっと効率が良くて、短いもの、解かりやすいものを考えたならばぜひ教えてください。