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