O^2 de comparaison entre la liste des objets

Question

J'ai deux liste d'objets:

list1 = [{value: 'X'}, {value: 'Y'}, ..., {value: 'Z'}]; 
list2 = [{value: 'A'}, {value: 'B'}, ..., {value: 'C'}]; 

J'ai ce code qui vérifie si les valeurs sont en list2list1. Si c'est le code ne fait rien, sinon il devrait ajouter à list1 (ceci va créer une nouvelle liste, list3). Ce qui signifie que je fais une union entre les deux listes sans conserver les valeurs répétées.

for (let i = list2.length-1; i >= 0; i--) { 
    let item = list2[i]; 
    let shared = false; 
    for (let j = list1.length-1; j >=0; j--) { 
    let childItem = list1[j]; 
    if (item.value === childItem.value) { 
     shared = true; 
     break; 
    } 
    } 
    if (!shared) { newValues.push(item); } 
} 
list3 = list1.concat(newValues); 

Cela fonctionne très bien, mais je me demandais si je pouvais améliorer ce O (n * m). Je ne suis pas sûr si les listes sont toujours triées par défaut, mais d'après ce que j'ai vu à la fois (list1 et list2) sont toujours triés par valeur.

Exemple:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}]; 
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}]; 
var list3 = union(list1, list2); 
list3 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}, {value: 'test'}, {value: 'testz'}]; 

Answer 1

créer un ensemble de valeurs de list1, et le filtre list2 par les valeurs de l'ensemble avant concating à list1:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}]; 
 
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}]; 
 

 
const union = (list1, list2) => list1.concat(
 
    list2.filter(function({ value }) { // filter list2 
 
    return !this.has(value); // filter out items which value is in the set 
 
    }, new Set(list1.map(({ value }) => value))) // the set of list1 values 
 
); 
 

 
const list3 = union(list1, list2); 
 

 
console.log(list3);

Answer 2

Vous pouvez utiliser une seule boucle et stocker la valeur dans un ensemble pour vérification ultérieure. Complexité: O (n).

var list1 = [{ value: 'X' }, { value: 'Y' }, { value: 'C' }, { value: 'Z' }], 
 
    list2 = [{ value: 'A' }, { value: 'B' }, { value: 'C' }, { value: 'D' }], 
 
    list3 = list1 
 
     .concat(list2) 
 
     .filter((s => ({ value }) => !s.has(value) && s.add(value))(new Set)); 
 

 
console.log(list3);

.as-console-wrapper { max-height: 100% !important; top: 0; }