Pertanyaan Apa cara tercepat atau paling elegan untuk menghitung satu set perbedaan menggunakan javascript array?


Membiarkan A dan B menjadi dua set. Saya mencari sangat cara cepat atau elegan untuk menghitung perbedaan yang ditetapkan (A - B atau A \B, tergantung pada preferensi Anda) di antara mereka. Kedua set disimpan dan dimanipulasi sebagai array Javascript, seperti yang dikatakan judul.

Catatan:

  • Gecko-spesifik trik baik-baik saja
  • Saya lebih suka menempel pada fungsi asli (tapi saya terbuka untuk pustaka ringan jika itu lebih cepat)
  • Saya telah melihat, tetapi tidak diuji, JS.Set (lihat poin sebelumnya)

Edit: Saya melihat komentar tentang set yang berisi elemen duplikat. Ketika saya mengatakan "set" saya mengacu pada definisi matematika, yang berarti (antara lain) bahwa mereka tidak mengandung elemen duplikat.


75
2017-11-12 15:42


asal


Jawaban:


jika tidak tahu apakah ini yang paling efektif, tapi mungkin yang terpendek

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(function(x) { return B.indexOf(x) < 0 })

console.log(diff);

Diperbarui ke ES6:

A = [1, 2, 3, 4];
B = [1, 3, 4, 7];

diff = A.filter(x => B.indexOf(x) < 0 );

console.log(diff);


137
2017-11-12 15:50



Nah, 7 tahun kemudian, dengan Set ES6 objek itu cukup mudah (tapi masih tidak sekompel piton A - B), dan dilaporkan lebih cepat dari indexOf untuk array besar:

let a = new Set([1,2,3,4]);
let b = new Set([5,4,3,2]);

console.log(new Set([...a].filter(x => !b.has(x)))); //a\b => {1}
console.log(new Set([...b].filter(x => !a.has(x)))); //b\a => {5}
console.log(new Set([...a].filter(x => b.has(x))));  //a∩b => {2,3,4}

44
2018-04-08 16:27



Anda dapat menggunakan objek sebagai peta untuk menghindari pemindaian linier B untuk setiap elemen A seperti dalam jawaban pengguna187291:

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;
}

Yang tidak standar toSource() metode digunakan untuk mendapatkan nama properti yang unik; jika semua elemen sudah memiliki representasi string unik (seperti halnya dengan angka), Anda dapat mempercepat kode dengan menjatuhkannya toSource() invokasi.


16
2017-11-12 16:37



Yang terpendek, menggunakan jQuery, adalah:

var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = $(A).not(B);

console.log(diff.toArray());
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>


9
2017-10-16 07:13



Saya akan hash array B, kemudian menyimpan nilai dari array A tidak ada di 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;
}

5
2017-11-12 17:04



Menggabungkan ide dari Christoph dan mengasumsikan beberapa metode iterasi non-standar pada array dan objek / hash (each dan teman-teman), kita bisa menetapkan perbedaan, penyatuan dan perpotongan dalam waktu linier dalam total sekitar 20 baris:

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);
  }
};

Ini mengasumsikan itu each dan filter didefinisikan untuk array, dan bahwa kita memiliki dua metode utilitas:

  • myUtils.keys(hash): mengembalikan an larik dengan kunci hash

  • myUtils.select(hash, fnSelector, fnEvaluator): mengembalikan larik dengan hasil panggilan fnEvaluator pada pasangan kunci / nilai untuk yang mana fnSelector mengembalikan nilai true.

Itu select() secara longgar terinspirasi oleh Common Lisp, dan hanya filter() dan map() dijadikan satu. (Akan lebih baik jika mereka mendefinisikannya Object.prototype, tetapi melakukan kerusakan dengan jQuery, jadi saya memutuskan untuk metode utilitas statis.)

Kinerja: Pengujian dengan

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

memberikan dua set dengan 50.000 dan 66.666 elemen. Dengan nilai-nilai ini A-B membutuhkan waktu sekitar 75ms, sementara union dan intersection masing-masing sekitar 150ms. (Mac Safari 4.0, menggunakan Tanggal Javascript untuk pengaturan waktunya.)

Saya pikir itu hasil yang layak untuk 20 baris kode.


4
2017-11-12 16:44



Menggunakan Underscore.js (Perpustakaan untuk JS fungsional)

>>> var foo = [1,2,3]
>>> var bar = [1,2,4]
>>> _.difference(foo, bar);
[4]

3
2018-01-02 12:32



Ini berfungsi, tetapi saya pikir yang lain jauh lebih pendek, dan juga elegan

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;

1
2017-11-12 16:07



Adapun cara berpuasa, ini tidak begitu elegan tapi saya sudah menjalankan beberapa tes untuk memastikan. Memuat satu larik sebagai objek jauh lebih cepat untuk diproses dalam jumlah besar:

var t, a, b, c, A;

    // Fill some arrays to compare
a = Array(30000).fill(0).map(function(v,i) {
    return i.toFixed();
});
b = Array(20000).fill(0).map(function(v,i) {
    return (i*2).toFixed();
});

    // Simple indexOf inside filter
t = Date.now();
c = b.filter(function(v) { return a.indexOf(v) < 0; });
console.log('completed indexOf in %j ms with result %j length', Date.now() - t, c.length);

    // Load `a` as Object `A` first to avoid indexOf in filter
t = Date.now();
A = {};
a.forEach(function(v) { A[v] = true; });
c = b.filter(function(v) { return !a[v]; });
console.log('completed Object in %j ms with result %j length', Date.now() - t, c.length);

Hasil:

completed indexOf in 1219 ms with result 5000 length
completed Object in 8 ms with result 5000 length

Namun, ini berfungsi dengan string saja. Jika Anda berencana membandingkan set bernomor, Anda pasti ingin memetakan hasilnya parseInt.


1
2018-01-11 04:21



Anda bisa menggunakan yang ringan ini array-diff komponen sumber terbuka.

Contoh:

diff([1,2,3], [1,2,3,4,5]) // => [4,5]

Ia bekerja dengan menggabungkan dua larik yang dilewatkan dan menyaring termasuk vals, mengembalikan larik yang mewakili perbedaan antara dua larik:

function diff(firstArray: any[], secondArray: any[]): any[] {
  return firstArray.concat(secondArray).filter((val) => {
    return !(firstArray.includes(val) && secondArray.includes(val));
  });
};

1
2018-05-23 08:27