Как сравнить массивы объектов по полю?

195

10 декабря 2019, 07:10

Есть 2 массива rows_1, rows_2 и есть функция которая ищет совпадение полей:

compare(rows_1, rows_2) {
  rows_1.forEach(row_1 => {
    rows_2.forEach(row_2 => {
      row_1['checked'] = row_1.id === row_2.sub.id;
    });
  });
}

У меня получились 2 вложенных цикла.

Нельзя ли это как-то лучше переписать, без двойного цикла или O(n2)?

UPDATE

Структура объектов:

rows_1 = [ {id: '1', title: '...'}, {id: '2', title: '...'}, ];
rows_2 = [ {sub: {id: '1', title: '...'}}, {sub: {id: '2', title: '...'}} ];

Answer 1

А вы уверены, что ваш код работает?
Ниже пример

var rows_1 = [ /*{ id: '1', title: '...' }, { id: '2', title: '...' },*/ ]; 
var rows_2 = [ /*{ sub: { id: '1', title: '...' } }, { sub: { id: '3', title: '...' } }*/ ]; 
var rows_1_f = [ ], rows_2_f = [ ]; 
 
var max  = 1000; 
var count = max; 
while ( --count ) { 
    rows_1.push( { id: count, title: '...' } ); 
    rows_1_f.push( { id: count, title: '...' } ); 
    if ( count <= max/2 ) { 
        rows_2.push( { sub: { id: count, title: '...' } } ); 
        rows_2_f.push( { sub: { id: count, title: '...' } } ); 
    } 
} 
 
// Ваш 
function compare ( rows_1, rows_2 ) { 
    rows_1.forEach( row_1 => { 
        rows_2.forEach( row_2 => { 
            row_1['checked'] = row_1.id === row_2.sub.id; 
        } ); 
    } ); 
} 
 
 
function compareFast ( rows_1, rows_2 ) { 
    var arr = [ ]; 
    rows_2.forEach( row_2 => { 
        arr.push( row_2.sub.id ); 
    } ); 
    rows_1.forEach( row_1 => { 
        row_1.checked = arr.indexOf( row_1.id ) !== -1; 
    } ); 
} 
 
console.time( 'compare' ); 
compare( rows_1, rows_2 ); 
console.timeEnd( 'compare' ); // compare: 10.747ms 
 
console.time( 'compareFast' ); 
compareFast( rows_1_f, rows_2_f ); 
console.timeEnd( 'compareFast' ); // compareFast: 1.098ms 
 
// Установите max в 10 и посмотрите что выводит ваш код 
//console.log( rows_1 ); 
//console.log( rows_1_f );

Разница примерно в 10 раз.

Установите max в 10 и посмотрите что выводит ваш код

После вашего кода

[ { id: 9, title: '...', checked: false },
  { id: 8, title: '...', checked: false },
  { id: 7, title: '...', checked: false },
  { id: 6, title: '...', checked: false },
  { id: 5, title: '...', checked: false },
  { id: 4, title: '...', checked: false },
  { id: 3, title: '...', checked: false },
  { id: 2, title: '...', checked: false },
  { id: 1, title: '...', checked: true } ]

После compareFast

[ { id: 9, title: '...', checked: false },
  { id: 8, title: '...', checked: false },
  { id: 7, title: '...', checked: false },
  { id: 6, title: '...', checked: false },
  { id: 5, title: '...', checked: true },
  { id: 4, title: '...', checked: true },
  { id: 3, title: '...', checked: true },
  { id: 2, title: '...', checked: true },
  { id: 1, title: '...', checked: true } ]

Answer 2

Попробуйте все-таки Set, я понимаю, что его скорость зависит от реализации, но по хорошему этот класс должен быть сделан на основе хеш-таблицы или бинарного дерева, что даст сложность O(1) или O(log n) против O(n) для обычного массива. У меня в хроме вариант на Set работает в 2-3 раза быстрее варианта на массиве (на тысяче элементов):

var rows_1 = [ /*{ id: '1', title: '...' }, { id: '2', title: '...' },*/ ]; 
var rows_2 = [ /*{ sub: { id: '1', title: '...' } }, { sub: { id: '3', title: '...' } }*/ ]; 
var rows_1_f = [ ], rows_2_f = [ ]; 
 
var max  = 1000; 
var count = max; 
while ( --count ) { 
    rows_1.push( { id: count, title: '...' } ); 
    rows_1_f.push( { id: count, title: '...' } ); 
    if ( count <= max/2 ) { 
        rows_2.push( { sub: { id: count, title: '...' } } ); 
        rows_2_f.push( { sub: { id: count, title: '...' } } ); 
    } 
} 
 
function compareFast ( rows_1, rows_2 ) { 
    var arr = [ ]; 
    rows_2.forEach( row_2 => { 
        arr.push( row_2.sub.id ); 
    } ); 
    rows_1.forEach( row_1 => { 
        row_1.checked = arr.indexOf( row_1.id ) !== -1; 
    } ); 
} 
 
function compareWithSet (rows_1, rows_2) { 
  let set = new Set( 
    rows_2.map(row_2 => row_2.sub.id) 
  ); 
  rows_1.forEach( row_1 => { 
      row_1.checked = set.has(row_1.id); 
  }); 
} 
 
console.time( 'compareFast' ); 
compareFast( rows_1_f, rows_2_f ); 
console.timeEnd( 'compareFast' ); 
 
console.time( 'compareWithSet' ); 
compareWithSet( rows_1, rows_2 ); 
console.timeEnd( 'compareWithSet' );

Код для теста нагло стащил из соседнего ответа