Esiste un modo (sistematico) per convertire un programma ricorsivo in una versione utilizzando lo stack utente?

Naviga le tue risposte
3

Ho un'immagine (una serie di 1000 x 1000 pixel) di 1s e 0s. Mi è stato chiesto di eseguire il rilevamento dei bordi, quindi ho scritto questo programma in C per attraversare la figura. La mia idea era quella di convertire ogni pixel circondato da pixel simili in bianco (1) e ogni pixel circondato da almeno un pixel diverso dal nero (0). E ho usato la ricorsione.

Questo ha funzionato quando la figura era piccola, ma ricevo un messaggio di "overflow dello stack" con cifre più grandi.

Esiste una tecnica sistematica per convertire questo in un programma "non ricorsivo" - simulando la ricorsione usando uno stack definito dall'utente?

    
posta TV Mohini 18.02.2015 - 17:41
fonte

2 risposte

3

Leggi sullo stack di chiamate , chiamate di coda , continuazioni e stile di passaggio continuo (CPS).

Quindi leggi la conversione CPS (o la trasformazione CPS). È un modo sistematico di trasformare uno stack di chiamate profonde in strutture e controlli allocati su heap.

Qui non c'è alcun punto magico, la conversione CPS sta semplicemente assegnando l'equivalente dei frame di chiamata nell'heap.

Leggi anche il libro di Appel Compilando con Continuazioni e il suo vecchio articolo Garbage Collection può essere più veloce di Stack Allocation

In termini pratici, potresti essere in grado di trasformare il tuo codice C ingenuo allocando la maggior parte dei dati nell'heap.

Un altro modo di pensare è quello di "inventare" un codice byte specializzato (per il tuo algoritmo) e implementare il suo interprete basato su stack.

Cfr. anche Gabriel Céralis Continuation Based C

Il (Deutch-) algoritmo di tracciatura del grafico di Schorr Waite potrebbe anche essere di ispirazione.

    
risposta data 18.02.2015 - 18:18
fonte
4

Quello che stai facendo è una variazione sulla colorazione del blob o sulla connettività a 8 vie.

La soluzione tradizionale per questo è ricorsiva e può creare problemi con i blob di grandi dimensioni.

Anni fa, un giovane collaboratore geniale ha escogitato un modo per fare connettività a 8 vie non ricorsiva. Ha usato due anelli, uno sopra le righe, una delle colonne in ogni riga e un corpo ad anello che guardava i quattro pixel "successori" (est, sud-est, sud, sud-ovest).

C'era una presa e un trucchetto secondario.

Il problema era che dovevi mantenere una tabella ausiliaria di "colori equivalenti", per gestire i casi in cui due blob che pensavi fossero separati risultassero connessi. (Immagina una grande lettera X. Finché non vedi il centro della X, potresti guardare una barra rovesciata e una barra.)

Il trucco secondario era che il corpo del ciclo doveva essere scritto in macro C, perché la chiamata di subroutine in testa lo stava mangiando vivo.

Questo dovrebbe darti qualcosa a cui pensare.

    
risposta data 18.02.2015 - 18:22
fonte

Leggi altre domande sui tag

Nell'analisi del valore limite, perché testare min + 1 insieme a min? Consigli per la valutazione di Web Framework (o librerie di software in generale)