使用迭代风格在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

Answer 1

这是值得怀疑的是一个迭代版本将真正成为速度更快，因为您要更换多次调用排队功能的递归调用。迭代转换有助于防止堆栈溢出（因为调用堆栈往往小于解释型语言中的堆栈），并且在没有尾部调用优化的语言中使用尾部递归。

Answer 2

我尝试使用队列的链表实现来查看会发生什么。我觉得你的问题可能已经在函数调用的开销和shift（）不necessaroly是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; 
} 

Answer 3

你（使用队列）存储在迭代版本的方法是什么导致增长放缓。 使用数组堆栈并为每个项目设置一个条目，而不是包含这两个项目的对象（基本值为&值）。

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的clone function benchmark suite。在一些运行中，迭代版本比递归更快，其他时候递归胜出。

Answer 4

那么，这个试图用JSON替代品来只有一个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[""]; 
} 

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