Самый эффективный способ дедупликации 2 массивов по значению A и сортировки по значению B?

Question

У меня есть массив, содержащий объекты, которые имеют идентификатор и значение сортировки. Когда запрашиваемая конечная точка возвращает массив с обновленными объектами, мне нужно объединить его с существующим массивом, объекты дублированного идентификатора входящего массива имеют приоритет над существующим массивом, но они оба должны быть отсортированы рядом друг с другом. например,

arrayA = [A:1, B:4, C:6]

arrayB = [D:2, A:3, C:5, G:7]

result = [D:2, A:3, B:4, C:5, G:7]

Пока что я не могу придумать никакого решения, которое не включает в себя, чтобы я сначала выводил массивы, а затем сортировал их, что кажется крайне неэффективным для длинных списков, над которыми я собираюсь работатьс участием. Какой самый эффективный способ добиться этого?

Answer 1

Вы можете выполнить обычный шаг слияния, который использует сортировка слиянием, за исключением того, что вы можете пропустить элементы в arrayA, которые уже находятся в arrayB. Чтобы быстро выполнить эту проверку, вы можете сначала добавить все идентификаторы от arrayB до Set. Это приведет к окончательному времени выполнения O (n + m) (с дополнительным пространством для Set) вместо O ((n + m) log (n + m) :

function linearMerge(A, B) {
  const res = [];
  const newIds = new Set(B.map(o => o.id));
  A = A.filter(o => !newIds.has(o.id));

  let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    if (A[i].val < B[j].val) res.push(A[i++]);
    else res.push(B[j++]);
  }
  while (i < A.length) res.push(A[i++]);
  while (j < B.length) res.push(B[j++]);
  return res;
}

const arrayA = [{id: 'A', val: 1}, {id: 'B', val: 4}, {id: 'C', val: 6}];
const arrayB = [{id: 'D', val: 2}, {id: 'A', val: 3}, {id: 'C', val: 5}, {id: 'G', val: 7}];

const result = linearMerge(arrayA, arrayB);
console.log(result); // [D:2, A:3, B:4, C:5, G:7]

Конечно, ваш оригинальный подход также работает, но может быть улучшен, если вы используете Set для удаления дубликатов:

function nLogNMerge(A, B) {
  const newIds = new Set(B.map(o => o.id));
  return [...A.filter(o => !newIds.has(o.id)), ...B]
    .sort((a, b) => a.val - b.val);
}

const arrayA = [{id: 'A', val: 1}, {id: 'B', val: 4}, {id: 'C', val: 6}];
const arrayB = [{id: 'D', val: 2}, {id: 'A', val: 3}, {id: 'C', val: 5}, {id: 'G', val: 7}];

const result = nLogNMerge(arrayA, arrayB);
console.log(result); // [D:2, A:3, B:4, C:5, G:7]

---

Я протестировал оба подхода, где arrayA и arrayB имеют 4500 записей, и линейное объединение действительно превосходит второй подход (примерно на 20% быстрее). ). Вы можете найти тест здесь: https://jsperf.com/merge-sorted-arrays-with-duplicates/1