map和object的区别以及性能

发表于

  这是一个日常周会上抛出来问题引发的一个思考，首先问题如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 全量树数据
const treeData = []; // TO BE PROVIDED;

// 以此数据做匹配
const searchData = []; //TO BE PROVIDED;

// 题目: 已知一颗树（数组），和一个待匹配数组。匹配规则：
// 1、匹配当前节点，将其作为根节点并保留当前节点的全部子节点
// 2、去重：某id节点既为根节点，又为子节点，则去掉其根节点展示
// treeData，searchData 以id做关联

let result;
// 开始匹配
console.time("getTreeData");
// CODE HERE
console.timeEnd("getTreeData");
// 结束匹配，输出结果
console.log(result);

  题目其实也很简单，但是这里的主要打分项是算法运行的速度。我这边给到的答案如下，大致就是找到了匹配的节点，判断该节点是否已经是其他节点的字节点，否，则就将该节点所有 id 记录到一个 object 中(用于判断字节点用)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const searchObj = {};
let result = [];
searchData.forEach((element) => {
  searchObj[element.id] = 1;
});
let resultObj = {};

const setResultObj = (tree) => {
  if (resultObj[tree.id]) {
    return;
  }
  resultObj[tree.id] = 1;
  if (tree.children && tree.children.length) {
    tree.children.forEach((child) => {
      setResultObj(child);
    });
  }
};

const searchTree = (tree) => {
  if (searchObj[tree.id]) {
    if (!resultObj[tree.id]) {
      result.push(tree);
      setResultObj(tree);
    }
    return;
  }
  if (tree.children && tree.children.length) {
    tree.children.forEach((child) => {
      searchTree(child);
    });
  }
};

treeData.forEach((element) => {
  searchTree(element);
});

  此算法在我这台小破电脑上面运行时间大约是 1.2ms - 1.8ms 之间，个人觉得大致思路没问题，比这快可能就有些剪枝做得好一点，怎么说都到不了 1ms 以内。

  然而，我 naive 了，有一份算法做到了 1ms 内。大致思路一致，主要在于他用的不是 obj 而是 map，问题就变得很有意思了，在我眼中 object 本质也就是个字典，居然和 map 之间有性能差距。

  于是乎网上找了一下 object 和 map 的对比，具体直接看mdn即可 Object 和 Map 的比较

  结论就是频繁插入读取情况，请使用map