0

Есть 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: '...'}} ];
9
  • 1
    можешь сначала свернуть один массив в объект, где ключами будут значения нужного поля, а затем просто проверять наличие поля в объекте
    – Grundy
    20 мар 2019 в 12:48
  • 1
    @Grundy хорошая идея. Но будет ли это быстрее? Pavel приведите пример структуры массивов. 20 мар 2019 в 12:54
  • 1
    Поиск свойства по объекте выполняется за константное время 20 мар 2019 в 13:09
  • 1
    @Pavel, тоже самое получится, только в случае, когда поиск ключа в объекте реализован наивным циклом. В других случаях сложность будет n+m
    – Grundy
    20 мар 2019 в 13:09
  • 1
    @АндрейNOP, за константное относительно количества элементов в массиве, но все зависит от конкретной реализации:)
    – Grundy
    20 мар 2019 в 13:10

2 ответа 2

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 } ]
2
  • да мой код не работает я вместо if(row_1.id === row_2.sub.id) без else не подумав row_1['checked'] = row_1.id === row_2.sub.id; влепил спасибо за замечание.
    – Pavel
    20 мар 2019 в 14:46
  • А вы можете добавить еще код, который предлагал @Grundy? Может, он будет еще быстрее! 21 мар 2019 в 5:09
1

Попробуйте все-таки 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' );

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

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.