递归为什么是实现深拷贝性能最佳

目录

• 前言
• 性能差异
• 执行栈
• 数组
• 测试性能对比
• 总结

前言

在《不用递归也能实现深拷贝》中提到递归的缺点是效率低，当调用的层次太多时，就会超出执行栈的容量，从而导致溢出。

非递归的实现深拷贝可以采用深度优先遍历：

function cloneDeep(source) {
  const map = {
      "[object Number]": "number",
      "[object Boolean]": "boolean",
      "[object String]": "string",
      "[object Function]": "function",
      "[object Array]": "array",
      "[object Object]": "object",
      "[object Null]": "null",
      "[object Undefined]": "undefined",
      "[object Date]": "date",
      "[object RegExp]": "regexp"
  }
  const result = Array.isArray(source) ? [] : {}
  const stack = [...Object.entries(source).map(item => [...item, result])]
  const toString = Object.prototype.toString
  while (stack.length) {
      const [key, value, target] = stack.pop()
      if (map[toString.call(value)] === 'object' || map[toString.call(value)] === 'array') {
          target[key] = Array.isArray(value) ? [] : {}
          stack.push(...Object.entries(value).map(item => [...item, target[key]]))
      } else {
          target[key] = value
      }
  }
  return result
}

console.log(cloneDeep({ a: 1, b: '12' }))
//{ a: 1, b: '12' }
console.log(cloneDeep([{ a: 1, b: '12' }, { a: 2, b: '12' }, { a: 3, b: '12' }]))
//[{ a: 1, b: '12' }, { a: 2, b: '12' }, { a: 3, b: '12' }]

和广度优先遍历

function cloneDeep(source) {
  const map = {
      "[object Number]": "number",
      "[object Boolean]": "boolean",
      "[object String]": "string",
      "[object Function]": "function",
      "[object Array]": "array",
      "[object Object]": "object",
      "[object Null]": "null",
      "[object Undefined]": "undefined",
      "[object Date]": "date",
      "[object RegExp]": "regexp"
  }
  const result = {}
  const stack = [{ data: source, target: result }]
  const toString = Object.prototype.toString
  while (stack.length) {
      let { target, data } = stack.unshift()
      for (let key in data) {
          if (map[toString.call(data[key])] === 'object' || map[toString.call(data[key])] === 
          'array') {
              target[key] = Array.isArray(data[key]) ? [] : {}
              stack.push({ data: data[key], target: target[key] })
          } else {
              target[key] = data[key]
          }
      }
  }
  return result
}

理论上两者性能是一样的，但在实际运行上两种方式存在一些性能差异。数组在末尾插入和删除操作效率比较高（只需 O(1) 的时间复杂度）。而在头部插入和删除操作效率最低，因为后面元素的位置都要调整。因此 pop 操作的深度优先遍历性能会更好些，这里就非递归的深度优先遍历和递归方式进行性能对比。

性能差异

递归的本质是通过执行栈来设置执行顺序并且通过执行上下文来存储执行状态。而上面非递归的方式其实是通过数组来实现栈的效果从而实现和递归一样的效果。两种方式遍历方式是一样的。时间复杂度也是一样。那么他们的性能差异主要是在执行栈的入栈、出栈操作和数组入栈、出栈操作的性能差异上。

执行栈

执行栈，也叫调用栈，具有 LIFO（后进先出）结构，用于存储在代码执行期间创建的所有执行上下文。

首次运行 JS 代码时，会创建一个全局执行上下文并 Push 到当前的执行栈中。每当发生函数调用，引擎都会为该函数创建一个新的函数执行上下文并 Push 到当前执行栈的栈顶。

根据执行栈 LIFO 规则，当栈顶函数运行完成后，其对应的函数执行上下文将会从执行栈中 Pop 出，上下文控制权将移到当前执行栈的下一个执行上下文。

数组

数组分为慢数组和快数组，快数组索引线性连续存储，慢数组使用 hash 表存储。这里的数组是慢数组。

执行栈的性能要比数组的性能好一些。

测试性能对比

function deepClone(obj) {
    if (obj === null || typeof obj !== "object") {
        return obj; // 非对象直接返回
    }
    let clone = Array.isArray(obj) ? [] : {}; // 根据类型创建对应的空对象或数组
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            clone[key] = deepClone(obj[key]); // 递归调用深拷贝
        }
    }
    return clone;
}
const limit = 1000000
let i = -1
const target= {}
while (++i < limit) {
    target[`key${i}`] = { i: i }
}

console.time('deepClone')
const clone = deepClone(target)
console.timeEnd('deepClone')

function deepClone(source) {
    const result = Array.isArray(source) ? [] : {}
    const stack = [...Object.entries(source).map(item => [...item, result])]
    while (stack.length) {
        const [key, value, target] = stack.pop()
        if (value === null || typeof value !== "object") {
            target[key] = value
        } else {
            target[key] = Array.isArray(value) ? [] : {}
            stack.push(...Object.entries(value).map(item => [...item, target[key]]))
        }
    }
    return result
}
const limit = 1000000
let i = -1
const target= {}
while (++i < limit) {
    target[`key${i}`] = { i: i }
}

console.time('deepClone')
deepClone(target)
console.timeEnd('deepClone')

总结

虽然递归可能会超出执行栈的容量，从而导致溢出，但在实际开发中几乎不会遇到超出容量的情况。而且实现深拷贝上递归要比用数组实现栈的方式性能好很多，因此平时更常见的是用递归来实现深拷贝。