two - subtract array javascript




Como obter a diferença entre duas matrizes em JavaScript? (20)

Abordagem funcional com o ES2015

A computação da difference entre duas matrizes é uma das operações do Set . O termo já indica que o tipo Set nativo deve ser usado para aumentar a velocidade de pesquisa. De qualquer forma, existem três permutações quando você calcula a diferença entre dois conjuntos:

[+left difference] [-intersection] [-right difference]
[-left difference] [-intersection] [+right difference]
[+left difference] [-intersection] [+right difference]

Aqui está uma solução funcional que reflete essas permutações.

difference esquerda:

// small, reusable auxiliary functions

const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// left difference

const differencel = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? false
     : true
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run the computation

console.log( differencel(xs) (ys) );

difference correta:

differencer é trivial. É apenas differencel com argumentos invertidos. Você pode escrever uma função por conveniência: const differencer = flip(differencel) . Isso é tudo!

difference simétrica:

Agora que temos a esquerda e a direita, implementar a difference simétrica também se torna trivial:

// small, reusable auxiliary functions

const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const concat = y => xs => xs.concat(y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// left difference

const differencel = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? false
     : true
  ) (xs);
};


// symmetric difference

const difference = ys => xs =>
 concat(differencel(xs) (ys)) (flip(differencel) (xs) (ys));

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run the computation

console.log( difference(xs) (ys) );

Eu acho que este exemplo é um bom ponto de partida para obter uma impressão do que significa programação funcional:

Programando com blocos de construção que podem ser conectados de várias maneiras diferentes.

Existe uma maneira de retornar a diferença entre duas matrizes em JavaScript?

Por exemplo:

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];

// need ["c", "d"]

Qualquer conselho muito apreciado.


JavaScript simples

Existem duas possíveis interpretações para "diferença". Eu vou deixar você escolher qual deles você quer. Diga que você tem:

var a1 = ['a', 'b'     ];
var a2 = [     'b', 'c'];
  1. Se você quiser obter ['a'] , use esta função:

    function difference(a1, a2) {
      var result = [];
      for (var i = 0; i < a1.length; i++) {
        if (a2.indexOf(a1[i]) === -1) {
          result.push(a1[i]);
        }
      }
      return result;
    }
  2. Se você deseja obter ['a', 'c'] (todos os elementos contidos em a1 ou a2 , mas não em ambos - a chamada diferença simétrica ), use esta função:

    function symmetricDifference(a1, a2) {
      var result = [];
      for (var i = 0; i < a1.length; i++) {
        if (a2.indexOf(a1[i]) === -1) {
          result.push(a1[i]);
        }
      }
      for (i = 0; i < a2.length; i++) {
        if (a1.indexOf(a2[i]) === -1) {
          result.push(a2[i]);
        }
      }
      return result;
    }

Lodash / sublinhado

Se você estiver usando lodash, você pode usar _.difference(a1, a2) (case 1 acima) ou _.xor(a1, a2) (case 2).

Se você estiver usando Underscore.js, poderá usar a função _.difference(a1, a2) para o caso 1.

ES6 Set, para matrizes muito grandes

O código acima funciona em todos os navegadores. No entanto, para grandes matrizes de mais de 10.000 itens, ela fica bastante lenta, porque tem complexidade O (n²). Em muitos navegadores modernos, podemos aproveitar o objeto ES6 Set para acelerar as coisas. O Lodash usa automaticamente o Set quando está disponível. Se você não estiver usando o lodash, use a seguinte implementação, inspirada na postagem do blog de Axel Rauschmayer :

function difference(a1, a2) {
  var a2Set = new Set(a2);
  return a1.filter(function(x) { return !a2Set.has(x); });
}

function symmetricDifference(a1, a2) {
  return difference(a1, a2).concat(difference(a2, a1));
}

Notas

O comportamento de todos os exemplos pode ser surpreendente ou não óbvio se você se preocupa com -0, +0, NaN ou matrizes esparsas. (Para a maioria dos usos, isso não importa.)


Apenas pensando ... por causa de um desafio ;-) isso funcionaria ... (para matrizes básicas de strings, números, etc.) sem matrizes aninhadas

function diffArrays(arr1, arr2, returnUnion){
  var ret = [];
  var test = {};
  var bigArray, smallArray, key;
  if(arr1.length >= arr2.length){
    bigArray = arr1;
    smallArray = arr2;
  } else {
    bigArray = arr2;
    smallArray = arr1;
  }
  for(var i=0;i<bigArray.length;i++){
    key = bigArray[i];
    test[key] = true;
  }
  if(!returnUnion){
    //diffing
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = null;
      }
    }
  } else {
    //union
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = true;
      }
    }
  }
  for(var i in test){
    ret.push(i);
  }
  return ret;
}

array1 = "test1", "test2","test3", "test4", "test7"
array2 = "test1", "test2","test3","test4", "test5", "test6"
diffArray = diffArrays(array1, array2);
//returns ["test5","test6","test7"]

diffArray = diffArrays(array1, array2, true);
//returns ["test1", "test2","test3","test4", "test5", "test6","test7"]

Observe que a classificação provavelmente não será como indicado acima ... mas, se desejar, chame .sort () na matriz para classificá-la.


Com a chegada do ES6 com conjuntos e operador splat (no momento de estar funcionando apenas no Firefox, verifique a tabela de compatibilidade ), você pode escrever o seguinte liner:

var a = ['a', 'b', 'c', 'd'];
var b = ['a', 'b'];
var b1 = new Set(b);
var difference = [...new Set([...a].filter(x => !b1.has(x)))];

que resultará em [ "c", "d" ] .


Eu suponho que você está comparando uma matriz normal. Se não, você precisa alterar o loop for para um loop for .. in .

function arr_diff (a1, a2) {

    var a = [], diff = [];

    for (var i = 0; i < a1.length; i++) {
        a[a1[i]] = true;
    }

    for (var i = 0; i < a2.length; i++) {
        if (a[a2[i]]) {
            delete a[a2[i]];
        } else {
            a[a2[i]] = true;
        }
    }

    for (var k in a) {
        diff.push(k);
    }

    return diff;
}

console.log(arr_diff(['a', 'b'], ['a', 'b', 'c', 'd']));
console.log(arr_diff("abcd", "abcde"));
console.log(arr_diff("zxc", "zxc"));

Uma solução melhor, se você não se importa com a compatibilidade com versões anteriores, está usando o filtro. Mas ainda assim, esta solução funciona.


Existe uma maneira melhor de usar o ES7:

Interseção

 let intersection = arr1.filter(x => arr2.includes(x));

Para [1,2,3] [2,3] produzirá [2,3] . Por outro lado, para [1,2,3] [2,3,5] retornará a mesma coisa.

Diferença

let difference = arr1.filter(x => !arr2.includes(x));

Para [1,2,3] [2,3] ele produzirá [1] . Por outro lado, para [1,2,3] [2,3,5] retornará a mesma coisa.

Para uma diferença simétrica , você pode fazer:

let difference = arr1
                 .filter(x => !arr2.includes(x))
                 .concat(arr2.filter(x => !arr1.includes(x)));

Desta forma, você irá obter um array contendo todos os elementos de arr1 que não estão em arr2 e vice-versa

Como @Joshaven Potter apontou sua resposta, você pode adicionar isso ao Array.prototype para que ele possa ser usado assim:

Array.prototype.diff = arr1.filter(x => arr2.includes(x));
[1, 2, 3].diff([2, 3])

Isso foi inspirado na resposta aceita por Thinker, mas a resposta de Thinker parece assumir que os arrays são conjuntos. Ele desmorona se os arrays forem [ "1", "2" ] e [ "1", "1", "2", "2" ]

A diferença entre esses arrays é [ "1", "2" ] . A solução a seguir é O (n * n), portanto, não é ideal, mas se você tiver grandes matrizes, também terá vantagens de memória sobre a solução do Thinker.

Se você está lidando com conjuntos em primeiro lugar, a solução do Thinker é definitivamente melhor. Se você tiver uma versão mais recente do Javascript com acesso a filtros, deverá usá-los também. Isto é apenas para aqueles que não estão lidando com conjuntos e estão usando uma versão mais antiga do JavaScript (por qualquer motivo) ...

if (!Array.prototype.diff) { 
    Array.prototype.diff = function (array) {
        // if the other array is a falsy value, return a copy of this array
        if ((!array) || (!Array.prototype.isPrototypeOf(array))) { 
            return this.slice(0);
        }

        var diff = [];
        var original = this.slice(0);

        for(var i=0; i < array.length; ++i) {
            var index = original.indexOf(array[i]);
            if (index > -1) { 
                original.splice(index, 1);
            } else { 
                diff.push(array[i]);
            }
        }

        for (var i=0; i < original.length; ++i) {
            diff.push(original[i]);
        }
        return diff;
    }
}   

Outra maneira de resolver o problema

function diffArray(arr1, arr2) {
    return arr1.concat(arr2).filter(function (val) {
        if (!(arr1.includes(val) && arr2.includes(val)))
            return val;
    });
}

diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]);    // return [7, 4, 5]

Que tal agora:

Array.prototype.contains = function(needle){
  for (var i=0; i<this.length; i++)
    if (this[i] == needle) return true;

  return false;
} 

Array.prototype.diff = function(compare) {
    return this.filter(function(elem) {return !compare.contains(elem);})
}

var a = new Array(1,4,7, 9);
var b = new Array(4, 8, 7);
alert(a.diff(b));

Assim, você pode fazer array1.diff(array2) para obter a diferença (complexidade de tempo horrível para o algoritmo - O (array1.length x array2.length) eu acredito)


Solução muito simples com a função de filtro do JavaScript:

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];

function diffArray(arr1, arr2) {
  var newArr = [];
  var myArr = arr1.concat(arr2);
  
    newArr = myArr.filter(function(item){
      return arr2.indexOf(item) < 0 || arr1.indexOf(item) < 0;
    });
   alert(newArr);
}

diffArray(a1, a2);


Usando o http://phrogz.net/JS/ArraySetMath.js você pode:

var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];

var array3 = array2.subtract( array1 );
// ["test5", "test6"]

var array4 = array1.exclusion( array2 );
// ["test5", "test6"]

Você poderia usar um Set neste caso. É otimizado para este tipo de operação (união, intersecção, diferença).

Certifique-se de que se aplica ao seu caso, uma vez que não permite duplicatas.

var a = new JS.Set([1,2,3,4,5,6,7,8,9]);
var b = new JS.Set([2,4,6,8]);

a.difference(b)
// -> Set{1,3,5,7,9}

para subtrair um array de outro, basta usar o snippet abaixo:

var a1 = ['1','2','3','4','6'];
var a2 = ['3','4','5'];

var items = new Array();

items = jQuery.grep(a1,function (item) {
    return jQuery.inArray(item, a2) < 0;
});

Ele retornará ['1,' 2 ',' 6 '] que são itens da primeira matriz que não existem na segunda.

Portanto, de acordo com a amostra do seu problema, o código a seguir é a solução exata:

var array1 = ["test1", "test2","test3", "test4"];
var array2 = ["test1", "test2","test3","test4", "test5", "test6"];

var _array = new Array();

_array = jQuery.grep(array2, function (item) {
     return jQuery.inArray(item, array1) < 0;
});

// abordagem es6

function diff(a, b) {
  var u = a.slice(); //dup the array
  b.map(e => {
    if (u.indexOf(e) > -1) delete u[u.indexOf(e)]
    else u.push(e)   //add non existing item to temp array
  })
  return u.filter((x) => {return (x != null)}) //flatten result
}

Eu queria uma função semelhante que recebesse uma matriz antiga e uma nova matriz e me fornecesse uma matriz de itens adicionados e uma matriz de itens removidos, e eu queria que ela fosse eficiente (por isso, não .contains!).

Você pode jogar com a minha solução proposta aqui: http://jsbin.com/osewu3/12 .

Alguém pode ver algum problema / melhoria nesse algoritmo? Obrigado!

Listagem de código:

function diff(o, n) {
  // deal with empty lists
  if (o == undefined) o = [];
  if (n == undefined) n = [];

  // sort both arrays (or this won't work)
  o.sort(); n.sort();

  // don't compare if either list is empty
  if (o.length == 0 || n.length == 0) return {added: n, removed: o};

  // declare temporary variables
  var op = 0; var np = 0;
  var a = []; var r = [];

  // compare arrays and add to add or remove lists
  while (op < o.length && np < n.length) {
      if (o[op] < n[np]) {
          // push to diff?
          r.push(o[op]);
          op++;
      }
      else if (o[op] > n[np]) {
          // push to diff?
          a.push(n[np]);
          np++;
      }
      else {
          op++;np++;
      }
  }

  // add remaining items
  if( np < n.length )
    a = a.concat(n.slice(np, n.length));
  if( op < o.length )
    r = r.concat(o.slice(op, o.length));

  return {added: a, removed: r}; 
}

Se as matrizes não são de tipos simples, então uma das respostas acima pode ser adaptada:

Array.prototype.diff = function(a) {
        return this.filter(function(i) {return a.map(function(e) { return JSON.stringify(e); }).indexOf(JSON.stringify(i)) < 0;});
    };

Esse método funciona em matrizes de objetos complexos.


function diff(a1, a2) {
  return a1.concat(a2).filter(function(val, index, arr){
    return arr.indexOf(val) === arr.lastIndexOf(val);
  });
}

Mesclar ambas as matrizes, valores exclusivos aparecerão apenas uma vez, então indexOf () será o mesmo que lastIndexOf ().


function diff(arr1, arr2) {
  var filteredArr1 = arr1.filter(function(ele) {
    return arr2.indexOf(ele) == -1;
  });

  var filteredArr2 = arr2.filter(function(ele) {
    return arr1.indexOf(ele) == -1;
  });
  return filteredArr1.concat(filteredArr2);
}

diff([1, "calf", 3, "piglet"], [1, "calf", 3, 4]); // Log ["piglet",4]

Array.prototype.diff = function(a) {
    return this.filter(function(i) {return a.indexOf(i) < 0;});
};

////////////////////  
// Examples  
////////////////////

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

["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]);  
// => ["test5", "test6"]

Array.prototype.diff = function(a) {
    return this.filter(function(i) {return a.indexOf(i) < 0;});
};

////////////////////  
// Examples  
////////////////////

var dif1 = [1,2,3,4,5,6].diff( [3,4,5] );  
console.log(dif1); // => [1, 2, 6]


var dif2 = ["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]);  
console.log(dif2); // => ["test5", "test6"]

Nota indexOf e filter não estão disponíveis em ie before ie9.


Array.prototype.difference = function(e) {
    return this.filter(function(i) {return e.indexOf(i) < 0;});
};

eg:- 

[1,2,3,4,5,6,7].difference( [3,4,5] );  
 => [1, 2, 6 , 7]




array-difference