У меня есть два массива объектов:
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}.
Поскольку массивы могут быть большими, мне нужен эффективный способ сделать это.
// 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), который включает в себя два отсортированных списка: а именно, вы рассматриваете оба списка вместе и несколько раз берете самый левый (самый маленький) элемент из списков (который исследуется, а затем увеличивается указатель/закладку из списка, который вы взяли). Это похоже на сортировку слияния, но с немного большей осторожностью, чтобы найти одинаковые элементы... и, возможно, надоедливо кодировать. В-третьих, если списки представляют собой устаревший код, и вы хотите преобразовать его в хэш-карту без лишних издержек памяти, вы также можете делать это поэтапно, неоднократно вынимая элементы из списков и в хэш-карты.
С lodash 4.12.0 вы можете использовать _. differenceBy.
_.differenceBy(a, b, 'id');
Общий способ сделать это:
В наши дни множество программных сред задали и/или реализации HashSet, что делает его очень простым.
В особых случаях другие способы могут быть более эффективными. Если, например, ваши элементы были значениями размера байтов, а a и b были достаточно большими, я бы использовал логический массив "flags" с 256 элементами, инициализируя все до false. Затем для каждого элемента x из b установите флаги [x] в true. Затем перебираем по a и для каждого y из a проверяем, установлены ли флаги [y].
Если вы не против использования библиотеки, использующей underscore.js, она имеет хорошую функцию пересечения http://documentcloud.github.com/underscore/