Найти различия между двумя массивами

Сначала одна маленькая деталь. Использовать const result вместо let. Вы, наверное, запутались там. Вы никогда не изменяете переменную результата, вы изменяете свойства объекта, хранящегося в этой переменной. Конст там в порядке.

Теперь к вашей проблеме с производительностью. Давайте определим n1 быть количеством ключей первого объекта. Сходным образом, n2 для второго объекта. Давайте определим n как сумма двух или, другими словами, максимально возможное количество ключей обоих объектов вместе взятых. Давайте определим m как средняя длина массива под ключом в любом из объектов. На самом деле вы можете думать о n как о количестве ключей объединения, а m как о среднем или максимальном значении. Производительность в целом будет варьироваться в зависимости от соотношений между n, n1, n2 и m. Но мы можем, по крайней мере, придумать приближение для среднего случая, худшего случая и т. д.

Чтобы создать массив всех ключей, вам нужно время O(n), и это, вероятно, не является узким местом.

Затем вы сортируете его по стоимости O (n log (n)), но это, вероятно, не является узким местом, хотя на самом деле это бесполезно, если вы не хотите сортировать его для вывода.

Затем у нас есть for над ключами, что означает, что у нас есть O (n) раз то, что находится внутри for.

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

И затем вы вызываете разностную функцию, которая составляет O (m) для времени фильтрации O (m) для проверки включения, что дает вам O (m ^ 2) всего для разностной функции. И это, вероятно, ваша проблема, и она становится хуже, чем больше m, чем n.

Вы можете легко исправить это, преобразовав массивы в наборы, которые равны O(m), а разница между двумя наборами также равна O(m)=O(m1+m2), где m1 и m2 — размеры двух наборов. Но здесь сложности не умножаются, а просто суммируются, что дает нам сложность всего O(m).

Это уменьшит общую сложность с O(nm^2) до O(nm). Как обычно, это будет незначительным или даже контрпродуктивным для небольших m входов, но это будет основным улучшением для больших m входов. Вы, вероятно, можете внести другие улучшения, но они не сократят временную сложность большого O (по крайней мере, не для стоимости памяти не более O (n)), и если они не нацелены на конкретную характеристику распределения входных данных (т. е. нацелены на большие n и small m, что может быть, а может и не быть в вашем случае), это будет иметь менее значительное влияние.

// m1 = arr1.length
// m2 = arr2.length
// O(m1 * m2)
// O(1) if arr1 is empty
// O(m1) if arr2 is empty
// combined call to difference(a,b) and difference(b,a) is therefore O(m1+m2) if at least one of the arrays is empty
// and it may even perform better than difference_using_set if one of the arrays is empty (or maybe actually just small) most of the time
function difference(arr1, arr2) {
  return arr1.filter((x) => !arr2.includes(x));
}

// O(m1 + m2) no matter if any of the arrays is empty
// O(m2) if arr1 is empty
// O(m1) if arr2 is empty
function difference_using_set(arr1, arr2) {
  // O(m2)
  const set2 = new Set(arr2)
  // O(m1) * O(1) = O(m1)
  return arr1.filter((x) => !set2.has(x))
}

function compute_differences(before, after) {
  const result = {
    added: {},
    removed: {},
  };

  // n1 = Object.keys(before).length
  // n2 = Object.keys(after).length
  // O(n1+n2)
  const allKeys = Object.keys(before).concat(Object.keys(after))
  // O(n1+n2)
  const allKeysSet = new Set(allKeys)
  // O(n)
  const keys = [...allKeysSet]
  // n = keys.length
  // O(n log(n))
  const sortedKeys = keys.sort()


  // n = keys.length (at most n1+n2)
  // O(n) times complexity of the inner code
  // = O(nm^2) when using difference function
  // = O(nm) when using difference_using_set function
  for (const key of sortedKeys) {
    // O(1)
    if (!before[key] || !before[key].length) {
      // notice added check for empty array because the effect is the same
      // and we avoid call to difference (_using_set) function which would be O(m) as described for empty arrays
      // even beating the advantage of difference function over difference_using_set function when one array is empty

      // O(1)
      result.added[key] = after[key];
      continue;
    }
    // O(1)
    if (!after[key] || !after[key].length) {
      // O(1)
      result.remove[key] = before[key];
      continue;
    }

    // O(m1*m2) ~ O(m^2)
    // const removed = difference(before[key], after[key]);
    // O(m2*m1) ~ O(m^2)
    // const added = difference(after[key], before[key]);

    // O(m1+m2) ~ O(m)
    const removed = difference_using_set(before[key], after[key]);
    // O(m2+m1) ~ O(m)
    const added = difference_using_set(after[key], before[key]);

    // O(1)
    if (removed.length) result.removed[key] = removed;
    // O(1)
    if (added.length) result.added[key] = added;
  }

  return result;
}