[Python] Passaggio oggetti tra classi

[Daniele Varrazzo]

On 2013-12-06 17:35, De Santis Luca wrote:

Ciao Luca,

> Vi ammorbo ancora con gli alberi. Devo fare una funzione per trovare
> il path di una qualsiasi foglia di un albero.
>
>
> Per fare ciò ho pensato di inserire nella classe che definisce
> l’albero un campo nodoGenitore, così, facendo la ricerca di un nodo
> per nome, quando trovo il nodo che mi interessa, vedo chi è il nodo
> padre e vado a ritroso fino alla radice e trovo il path completo 
> della
> foglia.

Questo di solito non è necessario negli algoritmi ricorsivi. Tra 
l'altro in Python hai anche un problema: se hai due oggetti che si 
riferiscono l'uno all'altro tipo (a.figli contiene b e b.genitore punta 
ad a) hai un ciclo di riferimenti. Poiché Python distrugge gli oggetti 
quando il refcount scende a zero questi due oggetti si tengono in vita 
l'uno con l'altro e potresti avere un memory leak. Questo è molto 
semplificato: il GC di Python è abbastanza intelligente di accorgersi di 
molti casi in cui un ciclo di oggetti non ha riferimenti esterni e alla 
fine riesce a reclamarlo, ma non sempre e così (quando non sia possibile 
è un po' complesso, ma ben documentato). Per farla corta, meno cicli hai 
nel codice, meglio è (e sempre a volerla dire tutta weakref è un modo 
fatto apposta per avere cicli "rompibili", ma anche di questo non ne hai 
bisogno per ora: la butto là in caso ti vada di approfondire).

Tornando a bomba: secondo me il puntatore del genitore non ti serve: il 
tornare a ritroso te lo dà lo srotolamento dello stack quando la 
soluzione viene trovata: io farei una funzione che interroga i figli e, 
se uno di loro è positivo, aggiunge sé stesso al valore di ritorno (se 
uno dei miei figli è la soluzione, anche io sono la soluzione!)

Quando un nodo è la soluzione? quando w == nomeNodo. Non ti serve 
chiederlo ai figli, giusto? Penso ti sia infilato in un vicolo cieco 
mentale facendo:

>     def _path(self,root,w):
>         for node in root.sottoNodi:
>             if(node.nomeNodo==w):

non serve chiederlo ai figli, e hai anche il problema che se root è la 
soluzione, non la troverai, giusto?

Questa funzione deve restituire una lista di nodi: direi che se c'è una 
soluzione sarebbe una lista che ha prima la radice, poi il suo figlio 
che porta alla soluzione... fino alla soluzione. Essendo l'algoritmo 
ricorsivo, puoi scriverlo in maniera che, gira gira, troverai un albero 
la cui radice è la soluzione (che poi sia la radice complessiva o solo 
un sotto-sotto-nodo non serve saperlo a lui: serve saperlo al 
chiamante). Quindi qualcosa come:

def path(self, w):
     # sono io la soluzione?
          # sì: fico: restituisci una lista che contiene solo me stesso
     # no? peccato, ma:
          # per ognuno dei miei figli
              # dammi il path per w
              # è una lista? fico allora
                  # aggiungo me stesso all'inizio della lista
                  # e restituisco la lista a chi mi ha chiamato

questo l'ho scritto in pseudocodice, ma l'ho implementato anche in 
python. Ti dò una possibilità di farlo da te se vuoi: letteralmente ogni 
riga che ho scritto si trasforma in un'instruzione Python, ma così credo 
sia ancora più chiaro l'algoritmo. Se vuoi la soluzione completa te la 
passo (o te la passa qualcun altro).

Nota che se la parola non viene trovata in nessuno dei figli il flusso 
di esecuzione esce alla fine della funzione senza incontrare un return. 
Questo equivale a "return None", ed è il risultato alternativo di "è una 
lista? fico". In pratica nodo.path(w) restituisce una lista se la 
soluzione viene trovata, altrimenti None.

In bocca al lupo!


-- Daniele