高效地映射数组

Question

我正在尝试找到在JS中同时比较/合并/操作两个数组（列表）的最佳/最有效或最功能性方法。下面给出的示例是总体概念的简单示例。在我的当前项目中，我处理一些非常疯狂的列表映射、过滤等，使用非常大的对象列表。作为下面所示，我对比列表的第一个想法（version1）是遍历第一个列表（即映射），并在匿名/回调函数中将第二个列表过滤以满足所需的比较条件（例如匹配ids）。显然，这种方法可以工作，如下面的version1所示。就性能而言，我有一个问题，因为通过这种方法，在每次迭代/map调用时，整个第二个列表都会被过滤，以查找与过滤器匹配的一个项目。

Also, the filter passes every other item in list2 which should be matched in list1. Meaning (as that sentence probably did not make sense):

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

Ideally on the first iteration of map (list1 id:1), when the filter encounters list2 id:3 (first item) it would just match it to list1 id:3

根据上述概念（当稍后遇到时匹配到较早的ID），我想出了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）。我正在处理更复杂的情况。

我不知道是否有一些更聪明（理想情况下是功能性的）的技术可以使用。

- 4lackof

---

任何一个数组是否应该包含唯一的对象集合，通过id来区分？这意味着在任何一个数组中，每个值只期望出现一次id。 - vol7ron

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; }

- Nina Scholz

---

那很漂亮。 - vol7ron

看起来非常出色。让我更多地关注map。我有一个问题是，如果没有左侧赋值，Object.assign(map.get(o[key]), o);会做什么？它是否会改变o的值？ - 4lackof

它会改变第一个参数（即 map.get(o[key]) 的结果），并将第二个参数 o 分配给它。 - Nina Scholz

Answer 2

使用filter进行搜索是一个错误的做法。您在版本2中的直觉更好。 Map和Set提供了更快的查找时间。

这是一种分解的方法。它应该非常快，但可能不如Nina的快。她是一个速度恶魔 >_<

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))

- Mulan

Answer 3

我提供这个完整性，因为我认为Nina和@user633183已经提供了更有效的解决方案。

如果您希望坚持使用您最初的filter示例，这是一个最大查找N*M的示例，并且您的数组是可变的；您可以考虑在遍历过程中减少集合。在旧时代，缩小数组对性能有巨大影响。

今天的一般模式是使用Map（或dict），如其他答案所示，因为它既易于理解又通常高效。

查找和调整大小

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;
}

- vol7ron

Answer 4

我不确定是否应该将这个问题标记为重复，因为你的措辞不同。无论如何，这是我对那个问题的答案，完全一样地复制过来了。你需要的是一个等值连接：

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);

使用equijoin计算答案需要O(m + n)的时间。但是，如果您已经有了索引，那么只需要O(n)的时间。因此，如果您计划使用相同的表进行多个等值连接，则将索引抽象出来可能是值得的。

- Aadit M Shah