Эффективный способ получить разницу между двумя массивами объектов? - PullRequest
Новая
       6

Эффективный способ получить разницу между двумя массивами объектов?

13 голосов
/ 16 июля 2011

У меня есть два массива объектов: 

var a = [  {'id': 20},   {'id': 15},   {'id': 10},   {'id': 17},   {'id': 23}  ];

var b = [ {'id': 90},   {'id': 15},    {'id': 17},   {'id': 23}  ];

Я хотел бы получить объекты, которые находятся в a, но не в b. Результаты из этого примера будут:

{'id': 20} и {'id': 10}.

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

Ответы [ 4 ]

20 голосов
/ 16 июля 2011 
// Make hashtable of ids in B
var bIds = {}
b.forEach(function(obj){
    bIds[obj.id] = obj;
});

// Return all elements in A, unless in B
return a.filter(function(obj){
    return !(obj.id in bIds);
});

очень незначительное дополнение: если списки очень велики и вы хотите избежать фактора дополнительной памяти 2, вы могли бы хранить объекты в хэш-карте в первую очередь вместо использования списков, предполагая, что идентификаторы уникальны : a = {20:{etc:...}, 15:{etc:...}, 10:{etc:...}, 17:{etc:...}, 23:{etc:...}}. Я бы лично сделал это. Альтернатива: во-вторых, javascript сортирует списки на месте, поэтому он не использует больше памяти. например a.sort((x,y)=>x.id-y.id) Сортировка будет хуже, чем выше, потому что это O (N log (N)). Но если вам все равно пришлось сортировать, есть алгоритм O (N), который включает два отсортированных списка: а именно, вы рассматриваете оба списка вместе и многократно берете самый левый (наименьший) элемент из списков (то есть проверяете, затем увеличиваете указатель / закладка из списка, который вы взяли). Это похоже на сортировку слиянием, но с большей осторожностью, чтобы найти идентичные элементы ... и, может быть, противно кодировать. В-третьих, если списки являются устаревшим кодом, и вы хотите преобразовать его в хэш-карту без лишних затрат памяти, вы также можете делать это поэлементно, многократно выталкивая элементы из списков и в хеш-карты.

5 голосов
/ 13 мая 2016

С lodash 4.12.0 вы можете использовать _. Разность по . 

_.differenceBy(a, b, 'id');
2 голосов
/ 16 июля 2011

Общий способ сделать это:

  1. поместить все объекты из b в хеш-таблицу
  2. итерировать по a, для каждого элемента проверять, находится ли он в хеш-таблице

В настоящее время во многих средах программирования установлены и / или реализованы HashSet, что делает это очень простым.

В особых случаях другие способы могут быть более эффективными.Если, например, ваши элементы имеют байтовые значения, а a и b довольно большие, то я бы использовал «флаги» логического массива с 256 элементами, инициализируя все как false.Затем для каждого элемента x of b установите flags [x] в true.Затем выполните итерацию по a, и для каждого y в a проверьте, установлены ли флаги [y].

0 голосов
/ 16 июля 2011

Если вы не против, чтобы библиотека использовала underscore.js, она имеет хорошую функцию пересечения http://documentcloud.github.com/underscore/

...