Как ускорить работу моего кода?

Question

[Айнур Ярулин]

Здравствуйте, есть такая задача найти удалённые и новые/изменённые
объекты в двух массивах из 60 000 объектов. В своём проекте для работы с массивами и объектами
я использую библиотеку lodash.

Сейчас я написал вот такой код, но время его работы меня смущает,
в среднем: 60 - 70 сек

Вот схема двух массивов:

const oldArray = [ 
  { 
     id: (никогда не меняется), 
     syncDate: (этот параметр не должен учитывается),
     x: (другие поля, которые могут изменится в новом массиве) 
  }  
  ... 60 тысяч таких объектов 
]
const newArray = [ 
  такой же, но в нём могут быть добавлены/изменены или удалены некоторые объекты
]

Вот так я нахожу изменённые и добавленные объекты:

const updated = newArray.filter(newObject => {
  const oldObject == oldArray.find(o => o.id == newObject.id)
  return !lodash.idEqualWith(newObject, oldObject, (_, _, key) => {
    return key == 'syncDate' ? true : false
  })
})

А вот так я нахожу удалённые объекты:

const deleted = oldArray.filter(oldObject => {
  const newObject = newArray.find(o => o.id == oldObject.id)
  return !lodash.isEqualWith(newobject, oldobject, (_, _, key) => {
     return key == 'syncDate' ? true: undefined
  })
}).pullAllBy(updated, 'id').value()

Есть идеи, какой новый подход можно применить? Буду рад любой помощи.

Comments

[Сергей Соколов]

объекты в массивах отсортированы по id, или id идут в случайном порядке?

[Айнур Ярулин]

Сергей Соколов, они отсортированы

Answer 1

[Rsa97]

Отсортировать массивы по id и за один параллельный проход найти сразу добавленные, удалённые и изменённые.

oldArray.sort((a, b) => a.id - b.id);
newArray.sort((a, b) => a.id - b.id);
oldIdx = 0;
newIdx = 0;
while (oldIdx < oldArray.length || newIdx < newArray.length) {
  if (oldIdx >= oldArray.length || oldArray[oldIdx].id > newArray[newIdx].id) {
    console.log(`Added id newArray[newIdx].id`);
    newIdx += 1;
    continue;
  }
  if (newIdx >= newArray.length || oldArray[oldIdx].id < newArray[newIdx].id) {
    console.log(`Deleted id oldArray[oldIdx].id`);
    oldIdx += 1;
    continue;
  }
  if (oldArray[oldIdx].x !== newArray[newIdx].x) {
    console.log(`Changed id newArray[newIdx].id`);
    oldIdx += 1;
    newIdx += 1;
  }
}

Comments

[Айнур Ярулин]

Можешь пожалуйста пример кода накинуть? Я пока свой вариант напишу

[Айнур Ярулин]

Rsa97 пока не получается заставить ваш код работать )

[Сергей Соколов]

сортировка двух массивов по 60 тыс элементов может чуть подтормозить весь процесс.

[Alexandroppolus]

Сергей Соколов, 60 тыс сортируется прямо со скоростью "вжух".

хотя можно для сравнения попробовать и другой классический подход - через Map.. Но сомневаюсь, что на 60 тыс. увидим ощутимую разницу.

[Айнур Ярулин]

Сергей Соколов, массивы уже отсортированы

Answer 2

[Айнур Ярулин]

На основе ответа Rsa97, написал вот такой код.

const deleted = [], updated = []
for (let oldidx = 0, newidx = 0; oldidx < current_data.length || newidx < new_data.length;) {
  
  if (newidx >= new_data.length || current_data[oldidx]?.id < new_data[newidx].id) {
    deleted.push(current_data[oldidx])
    oldidx++
    continue
  }
  
  if (oldidx >= current_data.length || current_data[oldidx].id > new_data[newidx]?.id || !lodash.isEqual(new_data[newidx], current_data[oldidx])) {
    updated.push(new_data[newidx])
    oldidx++
    newidx++
    continue
  }
  
  oldidx++
  newidx++
}

Мне было важно, чтобы обновлённые и добавленные данные были в одном массиве,
поэтому я сделал именно так. Сейчас время работы ~1.5 секунды
Еще появился вариант использовать свой метод, но заменить find на бинарный поиск,
но я его не тестировал.