Stack locale vs stack di chiamate

Uno stack "locale", come viene usato da quel commento, significa stack implicitamente dichiarato come variabile locale. Lo differenziare dallo stack delle chiamate definendolo uno stack "esplicito".

L'iterazione su uno stack esplicito può essere più veloce della ricorsione nei linguaggi che non supportano le ottimizzazioni correlate alla ricorsione come la ricorsione della coda. O una lingua potrebbe avere una profondità di stack limitata.

Ecco un buona spiegazione con un esempio di Eric Lippert.

LKM indica semplicemente una pila gestita manualmente, ad esempio una lista collegata in cui premi gli elementi in testa e poi li fai uscire di nuovo. Sarebbe più veloce perché è più piccolo, meno dati da mescolare.

Viene implementato disponendo di un campo nella struttura che è un puntatore (o riferimento se lo desideri) all'elemento successivo e una variabile head che è la parte superiore della pila. Quando si preme, si imposta il puntatore successivo dell'elemento spinto sul valore corrente della variabile head e quindi si imposta la variabile head per fare riferimento all'elemento spinto. Popping fa l'inverso.

Un altro modo per implementarlo, se si conosce lo stack massimo della pila, è di avere una matrice normale e una variabile di indice che indichi dove si trova la matrice nella matrice. Questo è il modo in cui viene implementato lo stack di chiamate di ricorsione, se lo si semplifica.

Credo che molte delle lingue menzionate sopra abbiano costrutti speciali per trattare gli array come stack, solitamente chiamati push / pop o shift / unshift.

In questo caso, usare uno stack locale significa "usare una variabile locale, ad esempio un array a cui si accede come una pila", cioè FIFO, invece di "effettuare chiamate di funzione, che creano frame di stack, ognuno dei quali contiene un int, tutti insieme considerati con gli stessi valori del tuo array ". Può essere più veloce perché stai evitando il sovraccarico dei registri push e popping, impostando il frame stack locale per ogni invocazione di funzione ecc. Invece stai facendo solo una allocazione di memoria e questo è tutto (e se usi alloca allora lo stack locale è è nello stack delle chiamate - alloca è essenzialmente solo un incremento in dex, mentre malloc può coinvolgere tutti i tipi di operazioni costose).

Il compromesso, come sempre, è che rendendo visibile la macchina dello stack, la struttura ricorsiva effettiva dell'algoritmo è molto meno chiara per molte persone. Nota che dico "molte persone" - alcune persone capiscono naturalmente la ricorsione e altre no. (Insegnavo Scheme e Prolog alle matricole, e direi che circa un terzo di loro fa e due terzi no.) Entire libri sono stati scritti solo per convincere quest'ultimo tipo di studenti a superare questo ostacolo, e dal momento che sembra appartenere al primo tipo, non so se posso comunicarti quanto sia mistificante il concetto è per molte persone. Non si tratta nemmeno di capire la sequenza di passaggi che avviene, più un problema di credere che è possibile usare una definizione che sembra non essere ancora completa. La soluzione richiede molta pratica e molti passaggi attraverso alcuni piccoli e esempi di medie dimensioni. Alla fine questo lascerà cadere il penny per molti studenti, anche se di gran lunga non tutti.