Marcatura ad albero

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Marcatura ad albero

Messaggio da rand » 14 ott 2007, 13:53

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.

Startrek
Messaggi: 120
Iscritto il: 18 lug 2007, 22:18

Messaggio da Startrek » 14 ott 2007, 21:28

La ricorsione è permessa? L'espressione numero costante di variabili non è molto esplicita...

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 15 ott 2007, 09:16

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...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 15 ott 2007, 13:08

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?
Certo, per quello nella traccia ho detto che si può modificare arbitrariamente la struttura dell'albero, purchè alla fine ritorni come l'originale.

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.

Avatar utente
phi
Moderatore
Messaggi: 349
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi » 20 ott 2007, 07:34

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;

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 20 ott 2007, 13:58

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.

Rispondi