Эффективное отображение массивов

Question

Я пытаюсь найти лучший / самый эффективный или наиболее функциональный способ сравнения / объединения / манипулирования двумя массивами (списками) одновременно в JS.

Пример, который я привожу нижеэто простой пример общей концепции.В моем текущем проекте я имею дело с очень сумасшедшим отображением списков, фильтрацией и т. Д. С очень большими списками объектов.

Как указано ниже, моей первой идеей (version1) по сравнению списков было бы запуститьчерез первый список (т. е. карту) и в функции анонимного / обратного вызова отфильтруйте второй список, чтобы он соответствовал критериям, необходимым для сравнения (например, идентификаторы соответствия).Это, очевидно, работает, как в version1 ниже.

У меня возник вопрос с точки зрения производительности, так как с помощью этого метода на каждой итерации / вызове карты весь 2-й список фильтруется только для того, чтобы найти этот один элемент, которыйсоответствует фильтру.

Кроме того, фильтр пропускает все остальные элементы в списке list2, которые должны совпадать в списке list1.Значение (поскольку это предложение, вероятно, не имело смысла):

list1.map   list2.filter

id:1        [id:3,id:2,id:1]
                          ^-match
id:2        [id:3,id:2,id:1]
                     ^-match
id:3        [id:3,id:2,id:1]
                ^-match

В идеале на первой итерации карты (list1 id:1), когда фильтр встречает list2 id:3 (первый элемент), он просто соответствует емуна list1 id:3

Думая с вышеупомянутой концепцией (в соответствии с более поздним идентификатором, когда он встречался ранее, я придумал version2).

Это превращает list2 всловарь, а затем ищет значение в любой последовательности по ключу.

const list1 = [
  {id: '1',init:'init1'},
  {id: '2',init:'init2'},
  {id: '3',init:'init3'}
];
const list2 = [
  {id: '2',data:'data2'},
  {id: '3',data:'data3'},
  {id: '4',data:'data4'}
];

/* ---------
* version 1
*/

const mergedV1 = list1.map(n => (
  {...n,...list2.filter(f => f.id===n.id)[0]}
));
/* [ 
  {"id": "1", "init": "init1"}, 
  {"id": "2", "init": "init2", "data": "data2"}, 
  {"id": "3", "init": "init3", "data": "data3"} 
] */

/* ---------
* version 2
*/

const dictList2 = list2.reduce((dict,item) => (dict[item.id]=item,dict),{}); 
// does not handle duplicate ids but I think that's 
// outside the context of this question.

const mergedV2 = list1.map(n => ({...n,...dictList2[n.id]}));
/* [ 
  {"id": "1", "init": "init1"}, 
  {"id": "2", "init": "init2", "data": "data2"}, 
  {"id": "3", "init": "init3", "data": "data3"} 
] */

JSON.stringify(mergedV1) === JSON.stringify(mergedV2);
// true

// and just for fun
const sqlLeftOuterJoinInJS = list1 => list2 => on => {
  const dict = list2.reduce((dict,item) => ( 
    dict[item[on]]=item,dict
  ),{});
  return list1.map(n => ({...n,...dict[n[on]]}
))};

Очевидно, что приведенные выше примеры довольно просты (объединение двух списков, каждый из которых имеет длину 3).Есть более сложные случаи, с которыми я работаю.

Я не знаю, есть ли какие-нибудь более умные (и идеально функциональные) методы, которые я должен использовать.

Answer 1

Вы можете взять закрытие по требуемому ключу для группы и Map для сбора всех объектов.

function merge(key) {
    var map = new Map;
    return function (r, a) {
        a.forEach(o => {
            if (!map.has(o[key])) r.push(map.set(o[key], {}).get(o[key]));
            Object.assign(map.get(o[key]), o);
        });
        return r;
    };
}

const
    list1 = [{ id: '1', init: 'init1' }, { id: '2', init: 'init2' }, { id: '3', init: 'init3' }],
    list2 = [{ id: '2', data: 'data2' }, { id: '3', data: 'data3' }, { id: '4', data: 'data4' }],
    result = [list1, list2].reduce(merge('id'), []);

console.log(result);

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

Answer 2

Использование filter для поиска является ошибкой. Ваш инстинкт в версии 2 намного лучше. Map и Set обеспечивают намного более быстрое время поиска.

Вот разложенный подход. Это должно быть довольно быстро, но, возможно, не так быстро, как у Нины. Она демон скорости> _ <</p>

const merge = (...lists) =>
  Array .from
    ( lists
        .reduce (merge1, new Map)
        .values ()
    )

const merge1 = (cache, list) =>
  list .reduce
    ( (cache, l) =>
        cache .has (l.id)
          ? update (cache, l.id, l)
          : insert (cache, l.id, l)
    , cache
    )

const insert = (cache, key, value) =>
  cache .set (key, value)

const update = (cache, key, value) =>
  cache .set
    ( key
    , { ...cache .get (key)
      , ...value
      }
    )

const list1 =
  [{ id: '1', init: 'init1' }, { id: '2', init: 'init2' }, { id: '3', init: 'init3' }]

const list2 =
  [{ id: '2', data: 'data2' }, { id: '3', data: 'data3' }, { id: '4', data: 'data4' }]

console .log (merge (list1, list2))

Answer 3

Я не уверен, стоит ли мне отмечать этот вопрос как дубликат , потому что вы сформулировали его по-другому. В любом случае, вот мой ответ на этот вопрос, скопированный дословно. То, что вы хотите, это equijoin:

const equijoin = (xs, ys, primary, foreign, sel) => {
    const ix = xs.reduce((ix, row) => // loop through m items
        ix.set(row[primary], row),    // populate index for primary table
    new Map);                         // create an index for primary table

    return ys.map(row =>              // loop through n items
        sel(ix.get(row[foreign]),     // get corresponding row from primary
        row));                        // select only the columns you need
};

Вы можете использовать его следующим образом:

const equijoin = (xs, ys, primary, foreign, sel) => {
    const ix = xs.reduce((ix, row) => ix.set(row[primary], row), new Map);
    return ys.map(row => sel(ix.get(row[foreign]), row));
};

const list1 = [
    { id: "1", init: "init1" },
    { id: "2", init: "init2" },
    { id: "3", init: "init3" }
];

const list2 = [
    { id: "2", data: "data2" },
    { id: "3", data: "data3" },
    { id: "4", data: "data4" }
];

const result = equijoin(list2, list1, "id", "id",
    (row2, row1) => ({ ...row1, ...row2 }));

console.log(result);

Требуется O(m + n) время, чтобы вычислить ответ, используя equijoin. Однако, если у вас уже есть индекс, тогда это займет всего O(n) времени. Следовательно, если вы планируете выполнять несколько эквайоинов с использованием одних и тех же таблиц, возможно, стоит выделить этот индекс.

Answer 4

Я предлагаю это для полноты, поскольку я думаю, что Нина и @ user633183 предложили, скорее всего, более эффективные решения.

Если вы хотите придерживаться своего начального фильтра примера, который является максимальным поиском N * M, и ваши массивы являются изменяемыми;Вы можете рассмотреть возможность уменьшения набора при прохождении.В старые времена сжатие массива оказывало огромное влияние на производительность.

Общая схема сегодня заключается в использовании карты (или слова), как указано в других ответах, поскольку она проста для понимания и в целом эффективна.

Найти и изменить размер

const list1 = [
  {id: '1',init:'init1'},
  {id: '2',init:'init2'},
  {id: '3',init:'init3'}
];
const list2 = [
  {id: '2',data:'data2'},
  {id: '3',data:'data3'},
  {id: '4',data:'data4'}
];

// combine by ID
let merged = list1.reduce((acc, obj)=>{
  acc.push(obj);

  // find index by ID
  let foundIdx = list2.findIndex( el => el.id==obj.id );
  // if found, store and remove from search
  if ( foundIdx >= 0 ){
    obj.data = list2[foundIdx].data;
    list2.splice( foundIdx, 1 );        // shrink lookup array
  }
  return acc;
},[]);

// store remaining (if you want); i.e. {id:4,data:'data4'}
merged = merged.concat(list2)

console.log(merged);

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