如何实现一个惊艳面试官的非递归版本的 js 对象深拷贝方法
flytam Lv4
  2020-03-28 13:46:05 2020-03-28 13:46      

众所周知，js 语言本身是不提供对象的深拷贝的功能，无论是直接赋值、Object.assign、展开运算符...都只是浅拷贝，关于 js 的深浅拷贝的一些概念可以参考我比较久以前写过的一篇文章

关于如何实现深拷贝，网上有很多相关的文章和实现都非常完美，本文主要讲述的是用一种非常规的使用非递归方法实现深拷贝

本文的深拷贝只考虑数组、对象、简单值三种数据类型

要实现判断数据类型，先来实现这 3 个判断类型的工具方法。最通用的就是利用Object.prototype.toString的特性

1
2
3
4
5
6
7
8
9
10
11
const getType = v => {
    switch (Object.prototype.toString.call(v)) {
        case "[object Object]":
            return "Object";
        case "[object Array]":
            return "Array";
        default:
            // 只考虑数组和对象，其余都是简单值
            return false;
    }
};

递归实现

在讲述非递归实现之前，先看看递归版本的深拷贝实现，很简单，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const copy = source => {
    const _cp = source => {
        let dest;
        const type = getType(source);
        if (type === "Array") {
            dest = [];
            source.forEach((item, index) => {
                dest[index] = _cp(item);
            });
            return dest;
        } else if (type === "Object") {
            dest = {};
            for (let [k, v] of Object.entries(source)) {
                dest[k] = _cp(v);
            }
            return dest;
        } else {
            return source;
        }
    };

    return _cp(source);
};

当然，这种是处理不了循环引用的。处理循环引用也很简单，用个WeakMap记录遍历过的值，每次拷贝前查出WeakMap中存在这个值，就直接返回。所以加上处理循环引用后的代码如下

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
const copy = (source) => {
    const map = new WeakMap();

    const _cp = (source) => {
        let dest;
        if (map.get(source)) {
            return map.get(source);
        }

        const type = getType(source);
        if (type === "Array") {
            // 数组
            dest = [];
            map.set(source, dest);
            source.forEach((item, index) => {
                dest[index] = _cp(item);
            });
            return dest;
        } else if (type === "Object") {
            // obj
            dest = {};
            map.set(source, dest);
            for (let [k, v] of Object.entries(source)) {
                dest[k] = _cp(v);
            }
            return dest;
        } else {
            return source;
        }
    };

    return _cp(source);
};

非递归实现

其实几乎所有的函数递归，都可以使用非递归的方法实现。如果大家有使用 javascript 刷 leetcode 的经历，很多时候如果我们的代码使用递归去解决问题，没有进行尾调用优化（很多时候有的题目确实写不出尾调用优化的写法，也可能我太菜）的时候，是很容易出现 js 调用栈过深出错的情形，这个时候切回成非递归写法就可以，而且很简单

我们简单先了解下 j s 递归的本质。j s 全局是有一个函数调用栈，当我们调用一个函数 a 时，这个函数 a 入栈，函数 a 内再次调用 a 时，一个新的函数 a 再次入栈。执行完毕依次弹出栈。多个函数的话也是类似的流程。用非递归解法的本质就是使用队列或者栈的数据结构来模拟 js 调用栈的执行过程

伪代码如下，百分之 99 的递归都可以用如下的思想实现非递归

  • 声明一个stack变量模拟调用栈

    1
    const stack = [];

  • 初始参数入栈

    1
    stack.push({ param1, param2 });

  • 栈非空，就一直取栈元素执行

    1
    2
    3
    4
    while (stack.length) {
        const item = stack.pop();
        //.......
    }

  • 如果需要继续下一次递归，将下一次递归调用的参数重新入栈

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(stack.length) {
    	const item = stack.pop()
      //继续下一次递归
      //  每次递归的执行流程
      .....
      if (condition) {
        stack.push({{param1:nextParam1,param2:nextParam2}})
      } else {
        ....
      }
    }

  • 当前递归终止条件，不入栈即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(stack.length) {
    	const item = stack.pop()
      //继续下一次递归
      //  每次递归的执行流程
      .....
      if (condition) {
      //...
      } else {
        //  递归终止条件。不入栈了
      }
    }

看完这里可能会有疑问，如果每次的递归调用，本次的结果需要是下一次递归的返回值怎么办呢。例如我们上面递归实现的深拷贝

1
dest[index] = _cp(item);

其实很好理解，递归的时候，当我们的下一级递归返回的时候，我们还能赋值说明在递归场景下，下一级返回后，我们当前级的执行变量还都在我们直接执行就可以，但是非递归情形下当前迭代执行完，是没有上一级的变量的了。这里就需要在每次迭代下一次的时候多传递一个指向当前迭代中需要获取下级结果的变量。（其实就是在递归场景中，下一级递归返回值的设置是在上一级中；非递归场景中，下一级的返回值，是在下一级中调用处理，很类似我们平时传递了一个回调函数的形式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while(stack.length) {
	const item = stack.pop()
  //继续下一次递归
  //  每次递归的执行流程
  .....
  // 上一级传递的dest
  //
  dest[xx] = xxx
  if (condition) {
    // 注意dest
    stack.push({{param1:nextParam1,param2:nextParam2,dest: {}}})
  } else {
    ....
  }
}

理解到这里，相信大家都知道将类似递归深拷贝转化成非递归实现的大致思路了，其实就是将一个对象，一级一级往下拆分key、value的形式进行处理。下面是详细分析

  • 首先，深拷贝是接收一个value然后返回一个拷贝值，所以需要一开始建立一个拷贝值的引用。在迭代的过程中，我们每一级都是对这个引用的子部分进行处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    const copy = source => {
        // 简单值直接返回
        if (!getType(source)) {
            return source;
        }
        // 建立这个最终返回的深拷贝值的本体
        let dest = Array.isArray(source) ? [] : {};
        //.....
    };

  • 进行上面提到的模拟调用栈的过程。在递归版本中，我们知道递归函数的入参其实就是这次访问的子节点的值，返回值是当前子节点的拷贝值。前面分析过，迭代调用我们需要传递上一级的创建的引用值进来设置。所以我们迭代调用，每次也有两个值，一个是当前访问节点的原值（和递归调用一样）、用于存储拷贝的引用值（在上一级迭代中创建的）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 调用栈初始状态
    const queue = [{ source, dest }];
    while (queue.length) {
        // source 当前访问的节点
        // dest 用于存储拷贝的引用值
        const { dest, source } = queue.shift();
        // 判断访问节点类型
        const type = getType(source);
        //
    }

  • 每次的迭代处理流程
    这里是需要分情况讨论

    • 访问节点是数组

      1
      2
      3
      4
      5
      6
      if (type === "Array") {
          // ....
          source.forEach((x, index) => {
              const xType = getType(x);
          });
      }
- 数组项是对象 (1)

  
1
2
3
4
5
6
7
8
9
10
if (xType === "Object") {
   // 生成一个对象引用，给下一次迭代的时候用
            dest[index] = {};
   // 入栈，需要下一次迭代
            queue.push({
                source: x,
                dest: dest[index]
            });
            return;
        }




- 数组项是数组(2)

  
1
2
3
4
5
6
7
8
9
10
if (xType === "Array") {
  // 生成一个数组引用，给下一次迭代的时候用
    dest[index] = [];
  // 入栈，需要下一次迭代
    queue.push({
        source: x,
        dest: dest[index]
    });
    return;
}




- 数组项是简单值。直接设置这个值到dest上

  
1
2
3
4
if (!getType(x)) {
      dest[index] = x;
     return;
              }

  • 访问节点是对象。类似于数组处理

    • 对象键是对象
    • 对象键是数组
    • 对象键是简单值

再加上循环引用处理也非常简单，每次迭代的最后将当前source添加到WeakMap中。在每次进行处理对象类型的stack.push的时候判断push的source是否在WeakMap中就可以了，若在WeakMap中说明是循环引用，直接设置值，不进行push

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while (stack.lenght) {
    //....
     if (xType === "Object") {
                    if (map.get(x)) {
                        dest[index] = map.get(x);
                        return;
                    }
                    dest[index] = {};
                    queue.push({
                        source: x,
                        dest: dest[index],
                    });
                    map.set(x, dest[index]);
                    return;
                }
    //....
}

最终我们的非递归版本的深拷贝就完成了。虽然花了一些力气，实现这个拷贝，代码也比递归版本复杂很多，性能可能也更差，但是如果能重头看到尾，并且自己实现一遍，相信会大大加深自己对深拷贝的理解和函数递归思想的的理解。下一次面试官让你写深拷贝的时候，你写一个非递归版本的，一定会大大惊艳面试官！

完整代码如下

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
const copy2 = (source) => {
    if (!getType(source)) {
        // 简单值
        return source;
    }
    let dest = Array.isArray(source) ? [] : {};
    const queue = [{ source, dest }];

    const map = new WeakMap();

    while (queue.length) {
        const { dest, source } = queue.shift();
        const type = getType(source);
        if (type === "Array") {
            // 数组
            source.forEach((x, index) => {
                const xType = getType(x);
                if (!getType(x)) {
                    dest[index] = x;
                    return;
                }

                if (xType === "Array") {
                    dest[index] = [];
                    queue.push({
                        source: x,
                        dest: dest[index],
                    });
                    return;
                }

                if (xType === "Object") {
                    if (map.get(x)) {
                        dest[index] = map.get(x);
                        return;
                    }
                    dest[index] = {};
                    queue.push({
                        source: x,
                        dest: dest[index],
                    });
                    map.set(x, dest[index]);
                    return;
                }
            });
        } else {
            // 对象
            for (let [k, v] of Object.entries(source)) {
                const vType = getType(v);
                if (!vType) {
                    dest[k] = v;
                    continue;
                }
                if (vType === "Array") {
                    dest[k] = [];
                    queue.push({
                        source: v,
                        dest: dest[k],
                    });
                }
                if (vType === "Object") {
                    if (map.get(v)) {
                        dest[k] = map.get(v);
                        continue;
                    }
                    dest[k] = {};
                    queue.push({
                        source: v,
                        dest: dest[k],
                    });
                }
                map.set(v, dest[k]);
            }
        }
    }
    return dest;
};

码字不易，如果觉得不错，求给个 star 或者赞吧！

  • Post title：如何实现一个惊艳面试官的非递归版本的 js 对象深拷贝方法
  • Post author：flytam
  • Create time：2020-03-28 13:46:05
  • Post link：https://blog.flytam.vip/如何实现一个惊艳面试官的非递归版本的 js 对象深拷贝方法.html
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments