javascript - 搜索数百万条记录的最快方法是两个 js 对象的组合

Question

我有数百万个消息对象

messages: [
    {
      id: Int,
      text: String,
      userId: Int,
      receiverId: Int,
    },

和成千上万的用户

  users: [
    {
      id: Int,
      name: String,
    },

我需要处理两个对象并以格式返回一个对象

[{ message, userFromName, userToName }]

我读到有关查找、过滤等数组方法的信息，其中一些和所有这些方法都比原生的 for 和 foreach 慢。

我还写了一个有两个foreach循环的函数

msgData.forEach(function(msg,i) {
    ...iterating every msg 
    userData.forEach(function(user) {
       ...iterating every user id over message sender and receiver id
    });
});

代码复杂度O(n)平方

如何在更短的时间内获得所需的格式？

Answer 1

将 users 转换为字典以进行快速、非迭代的查找:

原生对象:

let userDict = users.reduce((o,u)=> {
  o[u.id]=u.name;
  return o;
}, {});

map :

let userDict = new Map();
userDict.forEach(u => userDict.set(u.id,u.name));

这是 O(n)。使用这本字典，您可以将 forEach 的 msgData 简化为:

let result = msgData.map(msg => {
  return { message: msg.text, userFromName: userDict[msg.userId], userToName: userDict[msg.receiverId]};
 });

这也是 O(n)，因为对象和 Map 查找都是 O(1)。参见 this question有关这些的性能详细信息。无论采用哪种方式，都将比当前的 O(n^2) 解决方案显着提高性能。