ak optymalnie dopasować obiekty z dwóch tablic po pasujących właściwościach?

jeśli mam listę użykowników których muszę przemapować, i muszę dopasować do niego dług

let listOfUsers =
 [
  { id: 1, imie: "Jan", nazwisko: "Kowalski", wiek: 30 }, 
  { id: 2, imie: "Anna", nazwisko: "Nowak", wiek: 25 }, 
  { id: 3, imie: "Piotr", nazwisko: "Zielinski", wiek: 40 }
];

i mam drugą listę

let listOfUsersDebts =
 [
  { id: 1, dlug: 4000 }, 
  { id: 5, dlug: 444 }, 
  { id: 3, dlug: 900 }
];

można przejść po 1 tablicy i dla każdego elementu w tablicy 2 przeszukiwać odpoiwedniego elemntu
ale czy da się lepiej?

Trochę mało danych dałeś.
Czy jedna osoba może mieć kilka długów?
Czy to potrzebujesz tylko raz puścić, czy cyklicznie i aktualizować?
Ile takich wpisów będzie - bardziej 20 czy 3498989?
Czy chcesz sprawdzać poprawność danych - np. w podanym przykładzie w drugiej tablicy masz dług dla kogoś o ID=5, ale na liście useów kończysz na pozycji 3. Domyślam się, że to ID długu to jest odnośnik do osoby, więc co zrobić w sytuacji, w której taki pacjent nie istnieje?
Po co to robisz - czy chodzi o jakiś program na zaliczenie, gdzie masz się wykazać jakąś optymalizacją, czy serio ma to do czegoś służyć?

Nie ogólnie bo widziałem taki przypadek. Nigdy się optymalizacją nie zajmowałem, i zastanwaiłem sie jak to można zoptymalizwać.

User moze nie miec długu, a jeśli ma to tylko jeden. Jesli jest jakis dlug to jest tez user (tu akurat zly przyklad dalem).
powiedzmy że do 100 userów

User moze nie miec długu, a jeśli ma to tylko jeden.

No to tak na szybko pierwsza optymalizacja - jeśli user ma max. 1 dług, to po znalezieniu jakiegoś długu dla tego pacjenta, już nie sprawdzasz/nie szukasz innych wpisów w zakresie zadłużenia tego konkretnego usera.

Tak, jeżeli lista długów / userów jest wystarczająco długa to zyskasz przerzucając najpierw długi do mapy:

const debtByUser = new Map(listOfUsersDebts.map(({id, dlug}) => [id, dlug]))

i potem możesz dopasować dług w O(1)

listOfUsers.map(user => ({...user, debt: debtByUser.get(user.id)})

Przy małej ilości długów może to zadziałać na niekorzyść

Jeśli danych jest mało, to nie ma co się bawić.

Jeśli danych będzie dużo, to faktycznie naiwne lecenie i wyszukiwanie liniowe razy tyle, ile jest rekordów w drugiej tablicy będzie dość słabe
Wtedy złożoność byłaby w najgorszym wypadku O(m * n) , czy jakoś tak.

Więc bym wtedy próbował zoptymalizować szukanie.

1. jeśli tablica jest posortowana, to można zastosować szukanie binarne (binary search). Jak nie jest posortowana, to można posortować (ale samo sortowanie też może się odbić na wydajności, więc nie wiem, czy gra warta świeczki)
2. albo można wrzucić dane w mapę, jak @obscurity napisał. Albo w obiekt, gdzie klucze to ideki. Np. ja bym coś takiego zastosował:

const debtsByUserId = Object.create(null)
listOfUsersDebts.forEach(debt => debtsByUserId[debt.id] = debt.dlug);
listOfUsers.forEach(user => {
   console.log(`#${user.id} ${user.imie}, dlug: ${debtsByUserId[user.id]}`);
});

obscurity napisał(a):

Kopiuj

const debtByUser = new Map(listOfUsersDebts.map(({id, dlug}) => [id, dlug]))

Algorytmicznie ma sens, jednak tutaj wchodzi kiepski design JSa i .map() tworzy ci nową tablicę (zamiast być po prostu iteratorem). Więc jeśli masz milion elementów, to najpierw zostanie utworzona niepotrzebnie nowa tablica z milionami elementów tylko po to, żeby przekazać ją do konstruktora Map. Trzeba by jakiegoś benchmarka zrobić, ale obstawiam, że uniknięcie .map() i zrobienie tego bardziej imperatywnie może być szybsze.

LukeJL napisał(a):

Algorytmicznie ma sens, jednak tutaj wchodzi kiepski design JSa i .map() tworzy ci nową tablicę (zamiast być po prostu iteratorem). Więc jeśli masz milion elementów, to najpierw zostanie utworzona niepotrzebnie nowa tablica z milionami elementów tylko po to, żeby przekazać ją do konstruktora Map. Trzeba by jakiegoś benchmarka zrobić, ale obstawiam, że uniknięcie .map() i zrobienie tego bardziej imperatywnie może być szybsze.

Pozwoliłem sobie puścić mały benchmark i wyszło mi dla 100000 userów i "długów" średnie wartości:

58ms dla tworzenia elementu / mapy w pętli
71ms dla tworzenia mapy jednolinijkowcem (kopia w pamięci).
4347ms dla zwykłego szukania w pętli

Dla miliona userów zwykłe szukanie w pętli trwa zbyt długo żeby mi się chciało czekać.

Także o ile zmiana z pętli na objekt / mapę ma duże znaczenie i sens bo zmieniamy złożoność z kwadratowej na liniową to rozważanie czy użyć mapy czy obiektu i czy tworzyć pomocniczą tablicę w pamięci czy nie to jak dla mnie mikrooptymalizacje. Tu można się pokusić też o zwykłą pętlę zamiast .forEach i delegatów ale to wszystko nie ma realnego wpływu na prędkość algorytmu.

Ja bym postawił na mapę dlatego że jest bardziej intuicyjna i można prosto ją zainicjować, mniej kodu i czytelniej. Ale oczywiście można sobie potworzyć funkcje utilsowe typu toMap albo potworka z reduce i nie przejmować się większą ilością linijek kodu.

Wyszukaj w google "javascript intersect lists by object property"

Pierwszy link w google ze stacka: https://stackoverflow.com/questions/33356504/difference-and-intersection-of-two-arrays-containing-objects