Domanda su “Coda di chiamata Optimization” Articolo

Question

Ho una domanda per quanto riguarda questo articolo .

Tra questo codice

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

e questo codice

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) Sono confuso su quanto questo aiuta. Ha il secondo frammento di semplicemente hanno una chiamata coda che crea meno overhead perché calcola che cosa ha bisogno prima che si chiama di nuovo, o c'è qualcosa di più che mi manca?

A quanto mi risulta, la chiamata coda ancora non viene eliminato, appena ottimizzato.

2) E perché c'è bisogno di essere odds e odds1 comunque? Ancora non è chiaro neanche a me.

Answer 1

Sono confuso su quanto questo aiuta. Ha il secondo frammento di semplicemente hanno una chiamata coda che crea meno overhead perché calcola che cosa ha bisogno prima che si chiama di nuovo, o c'è qualcosa di più che mi manca?

A quanto mi risulta, la chiamata coda ancora non viene eliminato, appena ottimizzato.

Se la fine di una procedura simile a questo:

push args
call foo
return

Poi il compilatore può ottimizzare che via per solo

jump startOfFoo

L'eliminazione della chiamata di procedura del tutto.

E Perché ci devono essere quote e comunque Odds1? Ancora non è chiaro neanche a me.

Il "contratto" di specifica odds solo due argomenti - il terzo argomento è solo un dettaglio di implementazione. Così si nasconde che via in un metodo interno, e presentare un "wrapper", come l'API esterna.

Si potrebbe chiamare odds1 qualcosa come oddsImpl e sarebbe renderlo più chiaro, credo.

Answer 2

La prima versione non è coda ricorsiva perché dopo aver ottenuto il valore di odds(n - 1, p - 1) deve poi moltiplicarlo per (n / p), la seconda versione sposta questo nel calcolo dei parametri per la funzione odds1 per renderlo ricorsiva correttamente coda.

Se si guarda lo stack di chiamate poi la prima sarebbe andata in questo modo:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

, mentre il secondo potrebbe essere:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

perché si sta semplicemente restituendo il valore della chiamata ricorsiva il compilatore può ottimizzare facilmente questo:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

La ragione per avere odds e odds1 è semplicemente quello di fornire il valore iniziale dell'accumulatore quando altro codice chiama questa funzione.

Answer 3

L'ottimizzazione della ricorsione in coda è il seguente, nel primo esempio poiché non è possibile calcolare il risultato della return (n / p) * odds(n - 1, p - 1) moltiplicazione fino a quando hai chiamato odds (n-1), l'interperator deve tenere la nostra attuale posizione in memoria (su lo stack), e aprire una nuova chiamata alla probabilità.

ricorsivamente, che avverrà nella prossima chiamata così, e quello dopo e così via. Così abbiamo n operazioni in sospeso per il momento si raggiunge la fine della nostra ricorsione e iniziare la restituzione del valuesand calcolo dei prodotti.

Nel secondo esempio, dal momento che l'istruzione return eseguito è semplicemente return odds1(n - 1, p - 1, (n / p) * acc) possiamo calcolare gli argomenti della funzione, e semplicemente chiamare l'Odds1 (n-1) senza tenere la nostra attuale posizione . questo è dove l'ottimizzazione è, perché ora non devo ricordare dove sto ogni volta che apro un nuovo fotogramma sullo stack.

Pensate a come riferimenti del libro. immaginare si apre un libro di cucina e andare a una certa ricetta, e gli ingredienti sono elencati come segue:

1. sale
2. gli ingredienti nella pagina successiva

Nella pagina successiva ha

1. pepe
2. gli ingredienti nella pagina successiva

ecc. come si fa a dire ciò che tutti gli ingredienti sono? si deve ricordare quello che avete visto in ogni pagina!

anche se il secondo esempio è più simile al seguente elenco gli ingredienti:

1. sale
2. dimenticare questo, basta usare quello che si vede nella pagina successiva

Nella pagina successiva è:

1. sale
2. pepe
3. dimenticare questo, basta usare quello che si vede nella pagina successiva

ecc. per il momento si raggiunge l'ultima pagina (nota che l'analogia è accurato in quanto entrambi prendono la stessa quantità di chiamate di funzione), si dispone di tutti gli ingredienti, senza la necessità di "tenere a memoria" quello che avete visto in ogni pagina, perché è tutto quello che c'è in ultima pagina!