Ok, siccome i problemini vagamente teorici me li bocciate proviamo con qualcosa di più concreto. Cosa vi dicono le parole Garbage Collection? Se vi viene in mente al massimo la nettezza urbana continuate a leggere.
Supponiamo di avere un albero binario, in cui ogni nodo è una struttura con tre campi: Left, Right più il campo MARK di 1 bit, inizialmente uguale a 0. Left e Right sono puntatori nella memoria ai figli sinistro e destro o NULL se questi non esistono. Scrivere una procedura che dato un puntatore alla radice imposta tutti i campi MARK dei nodi a 1, ma usando solo un numero costante di variabili. Siete autorizzati a modificare l' albero come vi pare durante la procedura, purchè alla fine ritorni uguale a quello originale tranne che per i campi MARK.
Marcatura ad albero
Credo di no, altrimenti diventa facilino. Del resto se ricorri vuol dire che sotto sotto stai usando una quantità non costante di memoria (stack).
È permesso invece utilizzare "per altri scopi" i due puntatori (e un bit) che "implementano" l'albero? Stavo pensando a qualche giochino con lo XOR...
È permesso invece utilizzare "per altri scopi" i due puntatori (e un bit) che "implementano" l'albero? Stavo pensando a qualche giochino con lo XOR...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Certo, per quello nella traccia ho detto che si può modificare arbitrariamente la struttura dell'albero, purchè alla fine ritorni come l'originale.fph ha scritto:Credo di no, altrimenti diventa facilino. Del resto se ricorri vuol dire che sotto sotto stai usando una quantità non costante di memoria (stack).
È permesso invece utilizzare "per altri scopi" i due puntatori (e un bit) che "implementano" l'albero?
La ricorsione nasconde in se una struttura dati, lo stack, che occupa spazio extra lineare al caso pessimo, ma invece bisogna farlo in spazio extra costante. C'è una ben precisa ragione pratica dietro questo vincolo, perchè questa procedura (negli interpreti di alcuni linguaggi) viene chiamata proprio quando la memoria è esaurita.
Codice: Seleziona tutto
curr:=root;
prev:=NULL;
dir:="down";
repeat
if dir="down" then
curr.mark:=0;
if curr.left=NULL then
curr.left:=prev;
prev:=NULL;
dir:="up";
else
temp:=curr;
curr:=temp.left;
temp.left:=prev;
prev:=temp;
endif;
else
if curr.mark=0 then
curr.mark:=1;
if curr.right=NULL then
curr.right:=curr.left;
curr.left:=prev;
prev:=NULL;
else
temp:=curr;
curr:=temp.right;
temp.right:=temp.left;
temp.left:=prev;
prev:=temp;
dir:="down";
endif;
else
temp:=curr;
curr:=temp.right;
temp.right:=prev;
prev:=temp;
endif;
endif;
until curr=NULL;Ok, questa è una corretta implementazione di quello che è noto come algoritmo di Shorr-Waite, risalente agli anni sessanta credo.
L'idea è abbastanza naturale e consiste nel visitare in profondità l'albero sfruttando i puntatori degli stessi nodi attraversati per salvare il cammino che congiunge la radice con il nodo corrente della visita.
Basta mantenere 3 variabili, curr: nodo corrente, prev: nodo attraversato prima di curr, dir: = "down" se prev è padre di curr, "up" se curr è padre di prev. Quando dal nodo curr scegliamo di proseguire verso uno dei due figli puntati da curr.x (con x= "left" o "right") salviamo prev in curr.x e ricorsivamente visitiamo il sottoalbero di curr.x. Quando abbiamo finito e siamo ritornati a curr ripristiniamo il valore corretto di curr.x, che conosciamo perchè coincide con il valore attuale di prev, marchiamo curr, e ripetiamo la stessa cosa per il fratello di x. Se invece la visita di entrambi i figli di curr è conclusa, cosa che possiamo testare guardando se curr è marcato o no, allora possiamo ritornare al padre di curr, dato che il suo indirizzo si troverà in curr.right, se abbiamo scelto di visitare i figli in ordine sinistro-destro. Così facendo possiamo proseguire con la visita in profondità dell'albero.
Che applicazioni ha? Questo problema è centrale nei Garbage Collector degli interpreti dei linguaggi a oggetti tipo Java, il che significa che è importante. Nel fare Garbage Collection bisogna visitare il grafo dei puntatori degli oggetti e marcare quelli raggiungibili a partire dagli oggetti riferiti nello stack attuale. Al termine, gli oggetti non marcati vengono eliminati perchè inutili. Questo processo di marcatura non può utilizzare memoria più che costante, perchè tipicamente interviene proprio quando la memoria è in buona parte occupata da oggetti non più utilizzati (il garbage, la spazzatura) che vanno distrutti. Più o meno.
L'idea è abbastanza naturale e consiste nel visitare in profondità l'albero sfruttando i puntatori degli stessi nodi attraversati per salvare il cammino che congiunge la radice con il nodo corrente della visita.
Basta mantenere 3 variabili, curr: nodo corrente, prev: nodo attraversato prima di curr, dir: = "down" se prev è padre di curr, "up" se curr è padre di prev. Quando dal nodo curr scegliamo di proseguire verso uno dei due figli puntati da curr.x (con x= "left" o "right") salviamo prev in curr.x e ricorsivamente visitiamo il sottoalbero di curr.x. Quando abbiamo finito e siamo ritornati a curr ripristiniamo il valore corretto di curr.x, che conosciamo perchè coincide con il valore attuale di prev, marchiamo curr, e ripetiamo la stessa cosa per il fratello di x. Se invece la visita di entrambi i figli di curr è conclusa, cosa che possiamo testare guardando se curr è marcato o no, allora possiamo ritornare al padre di curr, dato che il suo indirizzo si troverà in curr.right, se abbiamo scelto di visitare i figli in ordine sinistro-destro. Così facendo possiamo proseguire con la visita in profondità dell'albero.
Che applicazioni ha? Questo problema è centrale nei Garbage Collector degli interpreti dei linguaggi a oggetti tipo Java, il che significa che è importante. Nel fare Garbage Collection bisogna visitare il grafo dei puntatori degli oggetti e marcare quelli raggiungibili a partire dagli oggetti riferiti nello stack attuale. Al termine, gli oggetti non marcati vengono eliminati perchè inutili. Questo processo di marcatura non può utilizzare memoria più che costante, perchè tipicamente interviene proprio quando la memoria è in buona parte occupata da oggetti non più utilizzati (il garbage, la spazzatura) che vanno distrutti. Più o meno.