如何利用迭代而非递归实现防爆栈的高性能深拷贝-js教程-PHP中文网

迭代深拷贝通过显式栈替代函数调用栈，避免递归爆栈，支持深层嵌套与循环引用；需用memo记录已拷贝对象ID，并分别处理基本类型、list、dict及特殊类型。

如何利用迭代而非递归实现防爆栈的高性能深拷贝

用迭代代替递归做深拷贝，核心是把“函数调用栈”换成自己管理的栈结构，避免系统栈深度限制导致的爆栈，尤其适合处理深层嵌套或超大对象。

为什么递归容易爆栈

递归每深入一层就压一个函数帧到系统调用栈。当对象嵌套超过几百层（比如 {a: {b: {c: {...}}}} 深达 500 层），PHP 默认 xdebug.max_nesting_level=256 或 Python 的 recursion limit 就会中断，抛出 Fatal error 或 RecursionError。这不是内存不够，而是调用栈满了。

迭代深拷贝的关键设计

用显式栈（如数组或列表）模拟递归过程，逐层展开、复制、回填，全程只占堆内存，不依赖系统调用栈：

维护一个待处理栈：每个元素是 (源对象, 目标容器, 键名或索引)，表示“要把这个源对象，放进目标容器的指定位置”
用哈希表记录已拷贝对象：键为原始对象 ID（如 Python 的 id(obj)，JS 的 WeakMap），值为对应的新对象，用于解决循环引用和避免重复拷贝
基本类型直接赋值：数字、字符串、布尔、None 等不入栈，原样写入目标位置
复合类型入栈处理：遇到 list/dict/object/array，先创建空容器，存入 memo，再把其每个子项推入栈中等待处理

Python 迭代深拷贝简易实现

以下代码不依赖 copy.deepcopy，纯手动迭代，支持 list、dict、基本类型及简单循环引用：

吐司AI消除

吐司AI消除是一款AI图片处理工具，Toast AI 推出的 AI 智能消除与去杂物工具。

下载

def iterative_deepcopy(obj):
    import collections
    memo = {}
    stack = collections.deque()
<pre class="brush:php;toolbar:false;"># 初始化：复制顶层对象
if isinstance(obj, (list, tuple)):
    clone = type(obj)()
    memo[id(obj)] = clone
    stack.append((obj, clone, None))  # (源, 目标容器, 无键名)
elif isinstance(obj, dict):
    clone = {}
    memo[id(obj)] = clone
    stack.append((obj, clone, None))
else:
    return obj  # 基本类型直接返回

while stack:
    src, dst_container, key_or_idx = stack.pop()

    if isinstance(src, list):
        for i, item in enumerate(src):
            if isinstance(item, (list, dict)) and id(item) in memo:
                value = memo[id(item)]
            elif isinstance(item, (list, dict)):
                value = type(item)()
                memo[id(item)] = value
                stack.append((item, value, None))
            else:
                value = item
            if isinstance(dst_container, list):
                dst_container.append(value)
            else:
                dst_container[i] = value

    elif isinstance(src, dict):
        for k, v in src.items():
            if isinstance(v, (list, dict)) and id(v) in memo:
                value = memo[id(v)]
            elif isinstance(v, (list, dict)):
                value = type(v)()
                memo[id(v)] = value
                stack.append((v, value, None))
            else:
                value = v
            dst_container[k] = value

return clone