143

AとBを 2 組とします。それらの間のセットの差（または、好みに応じて）を計算するための本当に高速またはエレガントな方法を探しています。タイトルが示すように、2 つのセットは Javascript 配列として格納され、操作されます。A - BA \B

ノート：

  • Gecko 固有のトリックは問題ありません
  • 私はネイティブ関数に固執したいと思います（ただし、軽量ライブラリの方が高速な場合は、それを受け入れます）
  • 私は見たが、テストしていないJS.Set (前のポイントを参照)

編集:重複する要素を含むセットに関するコメントに気付きました。「セット」と言うときは、数学的な定義を指しています。つまり、(とりわけ) 重複する要素が含まれていないことを意味します。

4

12 に答える 12

15

user187291 の回答のように、オブジェクトをマップとして使用して、B各要素の線形スキャンを回避できます。A

function setMinus(A, B) {
    var map = {}, C = [];

    for(var i = B.length; i--; )
        map[B[i].toSource()] = null; // any other value would do

    for(var i = A.length; i--; ) {
        if(!map.hasOwnProperty(A[i].toSource()))
            C.push(A[i]);
    }

    return C;
}

一意のプロパティ名を取得するために非標準のtoSource()方法が使用されます。すべての要素がすでに一意の文字列表現を持っている場合 (数字の場合のように)、toSource()呼び出しを削除することでコードを高速化できます。

于 2009-11-12T16:37:18.923 に答える
6

配列 B をハッシュしてから、配列 A の値を B に存在しないようにします。

function getHash(array){
  // Hash an array into a set of properties
  //
  // params:
  //   array - (array) (!nil) the array to hash
  //
  // return: (object)
  //   hash object with one property set to true for each value in the array

  var hash = {};
  for (var i=0; i<array.length; i++){
    hash[ array[i] ] = true;
  }
  return hash;
}

function getDifference(a, b){
  // compute the difference a\b
  //
  // params:
  //   a - (array) (!nil) first array as a set of values (no duplicates)
  //   b - (array) (!nil) second array as a set of values (no duplicates)
  //
  // return: (array)
  //   the set of values (no duplicates) in array a and not in b, 
  //   listed in the same order as in array a.

  var hash = getHash(b);
  var diff = [];
  for (var i=0; i<a.length; i++){
    var value = a[i];
    if ( !hash[value]){
      diff.push(value);
    }
  }
  return diff;
}
于 2009-11-12T17:04:43.547 に答える
5

Christoph からのアイデアを取り入れ、配列とオブジェクト/ハッシュ (およびその仲間) に対していくつかの非標準の反復メソッドを想定するとeach、合計約 20 行で集合差、結合、交差を線形時間で取得できます。

var setOPs = {
  minusAB : function (a, b) {
    var h = {};
    b.each(function (v) { h[v] = true; });
    return a.filter(function (v) { return !h.hasOwnProperty(v); });
  },
  unionAB : function (a, b) {
    var h = {}, f = function (v) { h[v] = true; };
    a.each(f);
    b.each(f);
    return myUtils.keys(h);
  },
  intersectAB : function (a, b) {
    var h = {};
    a.each(function (v) { h[v] = 1; });
    b.each(function (v) { h[v] = (h[v] || 0) + 1; });
    var fnSel = function (v, count) { return count > 1; };
    var fnVal = function (v, c) { return v; };
    return myUtils.select(h, fnSel, fnVal);
  }
};

eachこれは、とfilterが配列に対して定義されていること、および 2 つのユーティリティ メソッドがあることを前提としています。

  • myUtils.keys(hash): ハッシュのキーを持つ配列を返します

  • myUtils.select(hash, fnSelector, fnEvaluator)fnEvaluator : true を返すキーと値のペアを 呼び出した結果の配列をfnSelector返します。

はselect()Common Lisp から大まかに着想を得たもので、単純filter()にmap()1 つにまとめられています。(上で定義したほうがよいのですObject.prototypeが、そうすると jQuery が台無しになるので、静的なユーティリティ メソッドを使用することにしました。)

パフォーマンス: テスト

var a = [], b = [];
for (var i = 100000; i--; ) {
  if (i % 2 !== 0) a.push(i);
  if (i % 3 !== 0) b.push(i);
}

50,000 要素と 66,666 要素の 2 つのセットが得られます。これらの値では、AB は約 75 ミリ秒かかりますが、ユニオンと交差はそれぞれ約 150 ミリ秒かかります。(Mac Safari 4.0、タイミングに Javascript Date を使用)

これは、20 行のコードで十分な見返りだと思います。

于 2009-11-12T16:44:47.970 に答える
5

Underscore.js (関数型 JS のライブラリ) の使用

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]
于 2017-01-02T12:32:17.100 に答える
1

これは機能しますが、別のものははるかに短く、エレガントでもあると思います

A = [1, 'a', 'b', 12];
B = ['a', 3, 4, 'b'];

diff_set = {
    ar : {},
    diff : Array(),
    remove_set : function(a) { ar = a; return this; },
    remove: function (el) {
        if(ar.indexOf(el)<0) this.diff.push(el);
    }
}

A.forEach(diff_set.remove_set(B).remove,diff_set);
C = diff_set.diff;
于 2009-11-12T16:07:59.367 に答える