Uso dello stile iterativo per clonare un oggetto in JavaScript

Question

È possibile riscrivere la seguente funzione ricorsiva JavaScript per renderla più veloce?

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; 
} 

ho riscritto in uno stile iterativo, ma non guadagna qualsiasi prestazione, infatti la velocità è sceso da ≈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

E 'doubtable che una versione iterativa sarebbe davvero essere più veloce, come si sta sostituendo una chiamata ricorsiva con più chiamate a funzioni in coda. Nei casi in cui una trasformazione per l'iterazione aiuta a prevenire gli overflow dello stack (poiché gli stack di chiamate tendono ad essere più piccoli degli heap nelle lingue interpretate) e con ricorsione in coda nelle lingue senza ottimizzazione di chiamata di coda.

Answer 2

Ho provato a utilizzare un'implementazione di lista collegata della coda per vedere cosa succede. Credo che i vostri problemi avrebbero potuto essere la funzione di chiamata in testa e lo spostamento() non necessaroly essendo O (1)

Jsperf ha detto che era il più veloce in questo modo (ho testato su FF7): http://jsperf.com/clone-an-object/4 ma poi io non sono certo se non ho rovinato il benchmark in quanto non sono molto abituato al sito web di jsperf.

Modifica: Ho avuto un errore ritardato nel mio codice. In realtà era solo una copia superficiale

Quanto segue è la versione fissa del codice che ho usato. La sua più velocemente allora l'altra versione imperativo, ma perde ancora il codice ricorsivo:

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

Il modo in cui si memorizzano (con la coda) nella versione iterativa è ciò che sta causando il rallentamento. Utilizzare uno stack di array e disporre di una voce per ciascun elemento anziché di un oggetto che contiene entrambi gli elementi (valore base &).

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; 
} 

Scopri i clone function benchmark suite su JS Fiddle. In alcune corse la versione iterativa è più veloce di ricorsiva, altre volte la ricorsione vince.

Answer 4

Bene, questo ha cercato di utilizzare JSON sostituto per avere un solo JSON attraversamento, ma anche non più veloce (vedi 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

iterativo. 2 array, non usano 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; 
} 

E 'il più veloce iterativo finora. In Chrome Canary (17.0.959.0) è il più veloce in assoluto. Ancora più lento del ricorsivo in tutti gli altri browser.

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