在JavaScript中使用迭代风格克隆一个对象

Question

有没有可能改写下面的JavaScript递归函数，使其更快？

function clone_recursive(object) {
    var result = {};
    for (var key in object) {
        var value = object[key];
        if (typeof value === 'object') {
            result[key] = clone_recursive(value);
        } else {
            result[key] = value;
        }
    }
    return result;
}

我将其改写为迭代式风格，但性能没有提升，事实上速度下降了约20%。

function clone_iterative(object) {
    var result = {};
    var queue = [{base: result, value: object}];
    var item;
    while (item = queue.shift()) {
        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queue.push({base: resultValue, value: value});
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

http://jsperf.com/clone-an-object/13

- NVI

---

你可以将递归算法重写为迭代算法，如果递归深度太深，这有时是必要的，但你是否有理由想要特别转向继续传递？我认为现有的递归算法会更容易理解... - nnnnnn

我想看到一个迭代版本。 - NVI

我修改了问题。唯一的目标是使它更快。 - NVI

你正在使用哪种继承实现？如果不是 extension（我暂时记不起它的确切名称），则 clone_recursive 的两个实现都可能是不正确的。 - outis

在JavaScript中，不可能编写完美的克隆方法，但至少应该考虑数组。这个方法非常接近：https://dev59.com/A3RB5IYBdhLWcg3wET5J#728694 - user123444555621

Outis，让我们假设输入对象是Object的直接后代，并且它的所有属性都是自有属性。 - NVI

Answer 1

值得怀疑的是，迭代版本是否真的更快，因为您正在用多个调用队列函数来替换递归调用。转换为迭代的帮助之处在于防止堆栈溢出（因为解释性语言中的调用堆栈往往比堆小），以及在没有尾调用优化的语言中进行尾递归。

- outis

---

在FF3.6上，我回答的版本比递归版本经验上更快。在队列中使用对象来保存2个值是主要瓶颈。 - Louis Ricci

@LastCoder：使用你的基准测试脚本在jsFiddle上运行了10次试验，每个试验运行10次，每次运行中每个函数被调用100次。结果显示，在FF 3.6下，递归版本的平均执行时间为19.331毫秒（标准差：0.2424），迭代版本为23.49毫秒（标准差：0.1749）。在Chrome 15下，递归版本的平均时间为6.268毫秒（标准差：0.2291），迭代版本为6.409毫秒（标准差：0.2771）。根据我的研究，递归函数在实际中比迭代函数更快。如果-1是你的评价，那我现在收回它 :-)。 - outis

如果-1是你，那就不是这样的...我试验了一些修改测试对象的方法，看看在每个层级嵌套更多递归对象是否有任何差异。事实证明，递归确实更快，无论复制的测试对象变化如何，速度提高了5%到15%。我的最初回答是观察偏见，因为我在虚拟机上运行FF测试代码的前三次运行中。 - Louis Ricci

Answer 2

您在迭代版本中存储（使用队列）的方式是导致减速的原因。 使用数组堆栈，每个项目都有一个条目，而不是保存两个项目（基础和值）的对象。

function clone_iterative(object) {
    var result = {};
    var stack = [result, object];
    var curr, base;
    while (curr = stack.pop()) {
        var base = stack.pop();
        for (var key in curr) {
            var value = curr[key];
            if (typeof value === 'object') {
                stack.push(base[key] = {});
                stack.push(value)
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

请查看JS Fiddle上的复制函数基准测试套件。在某些运行中，迭代版本比递归更快，有时递归胜出。

- Louis Ricci

---

这是对原始迭代版本的改进。它在Chrome中与clone_recursive配对运行，但在所有其他浏览器中仍然较慢。http://jsperf.com/clone-an-object/5 - NVI

Answer 3

我尝试使用队列的链表实现来查看会发生什么。我认为您的问题可能是函数调用开销和shift()不一定是O(1)。

Jsperf说这是最快的方法（我在FF7上测试过）：http://jsperf.com/clone-an-object/4，但我不确定是否搞乱了基准测试，因为我不太熟悉jsperf网站。

编辑：我的代码中有一个愚蠢的错误。它实际上只是浅复制。

以下是我使用的代码的修正版本。它比其他命令式版本更快，但仍然输给递归代码：

function clone_iterative_linked_list(object) {
    var result = {};
    var queueHead = {base: result, value: object, next: null};
    var queueTail = queueHead;

   for(;queueHead; queueHead = queueHead.next){
        var item = queueHead;

        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queueTail.next = {base: resultValue, value: value, next:null};
                queueTail = queueTail.next;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

- hugomg

---

http://jsperf.com/clone-an-object/3 迭代版本使用链表仍然比递归版本慢。虽然在Safari中比数组快，但在Firefox中较慢，在Chrome中完全相同。 - NVI

你的版本没有进行深拷贝：clone_iterative_linked_list({a:{b:1}}) // {a:{}} - NVI

糟糕，quehead.next 在我添加项目之前就已经发生了。现在我想知道在我发布这个问题之前运行的测试用例是如何工作的 :D - hugomg

Answer 4

好的，这个尝试使用JSON replacer只进行一次JSON遍历，但速度并没有更快（请参见http://jsperf.com/clone-an-object/6）：

function clone(x) {
var r = {}, lastSrc, lastDst = r, stack = [], v;
function replacer(key, value) {
    while (this !== lastSrc && stack.length) {
        lastDst = stack.pop();
        lastSrc = stack.pop();
    }
    if (typeof value === "object") {
        stack.push(lastSrc, lastDst);
        lastDst[key] = v = new value.constructor;
        lastDst = v;
        lastSrc = value;
        return value;
    } else {
        lastDst[key] = value;
        return undefined;
    }
}
JSON.stringify(x, replacer);
return r[""];
}

- user1046334

Answer 5

迭代。使用 2 个数组，不要使用 pop()

function clone_iterative2(object) {
    var result = {};
    var bases = [result];
    var objects = [object];
    for (var i = 0, length = 1; i < length; ++i) {
        var current = objects[i];
        var base = bases[i];
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                bases.push(base[key] = {});
                objects.push(value);
                ++length;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

这是目前最快的迭代方式。在Chrome Canary（17.0.959.0）中，它是整体最快的。但在其他所有浏览器中，仍然比递归慢。

http://jsperf.com/clone-an-object/13

- NVI