Более быстрый подход сравнения двух массивов объектов с литеральными значениями в Javascript - PullRequest
Новая
       10

Более быстрый подход сравнения двух массивов объектов с литеральными значениями в Javascript

1 голос
/ 11 октября 2019
  1. Массив объектов с литеральными значениями означает, что это массив, каждый его элемент является объектом, в то время как все значения такого объекта являются литералами (поэтому он выигралЭто могут быть вложенные объекты, массив внутри объекта и т. д.), например: 
[ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false}, ... ]
Сравнить означает, что мы должны различать added и removed элементы, например: 
const original = [ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false} ];
const modified = [ { name: 'Alice', age: 19, isMale: false}, { name: 'Jay', age: 21, isMale: true } ];

// then added = [{ name: 'Jay', age: 21, isMale: true }]
// and removed = [{ name: 'Bob', age: 20, isMale: true }]

Мой подход:используя lodash разность с и isEqual , чтобы заставить вещи работать, например: 

const original = [ { name: 'Bob', age: 20, isMale: true }, { name: 'Alice', age: 19, isMale: false} ];
const modified = [ { name: 'Alice', age: 19, isMale: false}, { name: 'Jay', age: 21, isMale: true } ];

const removed = _.differenceWith(original, modified, _.isEqual);
const added = _.differenceWith(modified, original, _.isEqual);

^ Однако, этоне достаточно быстро !! У меня есть выборка из двух массивов, каждый массив содержит 10K + объектов, в то время как каждый объект имеет 3 свойства с lietal значениями. как это: 

[{lat: 123.321, long: 234.432, radius: 100}, ....]         // 10K+ elements

Я тестировал сам, использование моего подхода обойдется:

  1. ~ 10 секунд для завершения <= слишком медленно </li>
  2. браузер будетзависание из-за больших вычислений <= главная проблема! </li>

Теперь вопрос заключается в том, можете ли вы предоставить более быстрый и более элегантный способ Сравнить такие образцы?

Одно из моих предположений - я могу улучшить, заменив isEqual на что-то другое, но не уверен, поможет ли это в такой ситуации.

1 Ответ

1 голос
/ 11 октября 2019

Сравнение каждого объекта с каждым объектом приведет к проблеме O(n^2), которая, как вы заметили, является сложностью, которая растет довольно быстро, и тогда 10 тыс. Объектов (что не так много в компьютерном мире) практически не обрабатываются.

Однако есть более простой способ пройти через это.

Предварительная обработка

  1. Сортировать оба массива по имени, это займет O(n*log(n))
  2. Имеется два индекса для каждогомассив, начинающийся с 0, давайте назовем его i и j

Обработка

  1. Сравнение имен в original[i] и modified[j]
  2. Если это одно и то же, просто i++ и j++
  3. Если оно отличается, проверьте, какое из них "ниже" в сравнении строк (например, Боб ниже, чем Катрин, потому что он начинается с B)
  4. Если original[i] ниже, добавьте его к removed и i++
  5. Если modified[j] ниже, добавьте его к added и j++
  6. Повторяйте, пока не обработаете оба массива

Самая дорогая часть - сортировка, все остальное - dодин раз в O(n), поэтому общая сложность будет O(n*log(n)), что достаточно даже для миллионов предметов.

Примечание: если вам нужно сравнить, например, возраст или пол, а не только имена, вам нужнообновите вышеупомянутое с сортировкой по нескольким полям и затем сравнением по нескольким полям)

...