Как найти элементы в массиве2, которые не находятся в массиве1?

Question

У меня есть два массива:

var a1 = [ { ID: 2, N:0 }, { ID: 1, N:0 } ]; 
var a2 = [ { ID: 1, N:0 }, { ID: 2, N:0 }, { ID: 3, N:0 } ]; 

Мне нужно, чтобы все элементы, которые находятся на a2, но не в a1. Элемент здесь отличается от другого только свойством ID, остальные свойства следует игнорировать. И я не могу гарантировать порядок элементов на массивах. Значение результата для этого примера должно быть следующим:

Как я могу сделать это эффективным способом? (Я буду сравнивать массивы от 500 до 5000 длины)

Answer 1

Чтобы сделать это эффективно, вам нужно создать индекс элементов, которые уже находятся в a1, чтобы вы могли циклически перемещаться по a2 и сравнивать каждый с индексом, чтобы убедиться, что он уже был замечен или нет. Для индекса можно использовать объект javascript. Перейдите через a1 и поместите все его идентификаторы в индекс. Затем выполните цикл через a2 и соберите все элементы, идентификатор которых не отображается в индексе.

function findUniques(testItems, baseItems) { 
    var index = {}, i; 
    var result = []; 

    // put baseItems id values into the index 
    for (i = 0; i < baseItems.length; i++) { 
     index[baseItems[i].ID] = true; 
    } 

    // now go through the testItems and collect the items in it 
    // that are not in the index 
    for (i = 0; i < testItems.length; i++) { 
     if (!(testItems[i].ID in index)) { 
      result.push(testItems[i]); 
     } 
    } 
    return(result); 
} 

var a1 = [ { ID: 2, N:0 }, { ID: 1, N:0 } ]; 
var a2 = [ { ID: 1, N:0 }, { ID: 2, N:0 }, { ID: 3, N:0 } ]; 

var result = findUniques(a2, a1); 
// [{"ID":3,"N":0}] 

Работа демо: http://jsfiddle.net/jfriend00/uDEtg/

Answer 2

Тот же вопрос был размещен в несколько раз, посмотрите здесь:

JavaScript array difference

Большинство решений, данное через «родной» JavaScript однако , Я иногда предпочитаю использовать underscore.js, так как я создаю много вещей, используя backbone.js, а подчеркивание - зависимость для Backbone. Поэтому я могу использовать его удивительные утилиты. Вы могли бы рассмотреть их загрузку в:

http://documentcloud.github.com/underscore/

var a1 = [ { ID: 2, N:0 }, { ID: 1, N:0 } ]; 
var a2 = [ { ID: 1, N:0 }, { ID: 2, N:0 }, { ID: 3, N:0 } ]; 

var from, to; 
if(a1 > a2){ 
    from = a1 
    to = a2 
} else { 
    from = a2 
    to = a1 
} 

var a3 = _.filter(from, function(obj){ 
    var compare = _.find(to, function(obj2){ return obj.ID === obj2.ID }); 
    return compare === undefined 
}); 
console.log(a3); 

я первый определил длинный массив, я делаю это потому, что я хочу, чтобы сравнить, как много объектов, как можно более короткий список. В противном случае мы «забыли» некоторые.

Затем я просто использую фильтр и нахожу в библиотеке underscore.js для возврата объектов, которые не находятся в более коротком массиве, но ARE в более длинном массиве.

Если оба массива одинаковой длины, это тоже хорошо, потому что тогда мы сравним все предметы со всеми остальными.