[Roma.pm] xml + tag name

[Emanuele Zeppieri]

Oha wrote:

>> efficiente, visto che Perl non ha la tail recursion optimization 
> 
> a quanto ricordo, la tail recursion e' applicabile solo se la ricorsione e' loop-invariant

Ricordi bene.

> se ricordo bene, quindi, in questo caso la ricorsione avviene piu'
> volte per ogni stato dello stack, e non sarebbe dunque possibile fare
> tail recursion.

In realtà sarebbe possibile, se avessimo per ogni nodo un puntatore al 
padre (però certamente quella mostrata da Aldo non è tail-recursion, 
quindi non è ottimizzabile in automatico).

Ora non credo che nella struttura di dati tirata fuori da XML::Simple ci 
sia il puntatore al padre, però potremmo aggiungerlo con una visita in 
ampiezza (iterativa) molto veloce.

Solo che se utilizziamo la tail-recursion per evitare l'occupazione di 
memoria (lineare nel numero di nodi interni) sullo stack, e poi 
risprechiamo altrettanta memoria (asintoticamente) per il puntatore al 
padre, allora è un cazzo e tutt'uno, per usare un inglesismo.

Quindi percorrere questa strada non ha in effetti molto senso (benché in 
linea teorica sia possibile).

> la soluzione di usare un loop (push su una pila di di cose "da fare") 
> a sua volta potrebbe non esser efficiente (per grandi strutture dati,
> la pila potre diventare enorme)

Qui invece davvero non ti capisco.
Se la pila diventa enorme lo diventa anche nella tua soluzione ed anche 
nella soluzione ricorsiva, pari pari, non si scappa ;-)

L'occupazione di memoria sullo stack è la stessa in tutte le soluzioni: 
una soluzione iterativa, in assenza di puntatori al padre, deve gestirsi 
*per forza* uno stack, e la soluzione ricorsiva gestisce anch'essa né 
più né meno uno stack (sia pure "dietro le quinte"), necessario 
all'interprete perl per allocare le chiamate ricorsive.

> una soluzione e' farsi un vero e proprio stack applicativo,
> mi capito' di scrivere codice del genere in C usando puntatori a struct.
> senza usare OOP un esempio in perl e' quanto segue:

Che cosa vuol dire uno stack applicativo?! :-)
In realtà stai utilizzando uno stack (pressoché) identico a quello che 
ho utilizzato io e a quello necessario a qualsiasi altra soluzione 
iterativa, e altrettanto identico (almeno come dimensioni asintotiche) a 
quello utilizzato dall'interprete perl per allocare le chiamate ricorsive.

> $ref = XMLin('<opt><a/><b><b1 d="0"/></b><c><c1/></c></opt>');
> 
> my @stack = ([$ref, [keys %$ref]]);
> 
> my $sp = 0;
> while($sp>=0)
> {
>         my $r = $stack[$sp][0];
>         my $next = shift @{$stack[$sp][1]};
>         if($next)
>         {
>                 print "child $next...n";
>                 $sp++;
>                 my $r2 = $r->{$next};
>                 $stack[$sp] = [$r2, [keys %$r2]];
>         }
>         else
>         {
>                 $sp--;
>         }
> }
> 
> ogni elemento di @stack contiene lo "stato" dello stack in quel punto.
 >
>la "shift" simula un ciclo prelevando il prossimo elemento nella lista di cose da fare,
 >
>e $sp (come potra' suggerire il nome) e' lo stack pointer.

Non so che vantaggi possa avere quest'implementazione e non so neanche 
con quale altra soluzione la stai confrontando, né su quale piano 
(velocità, occupazione di memoria?)
Peraltro la pop() è leggermente più veloce della shift(), per cui, a 
meno di vincoli sull'ordine di visita dei nodi, ti conviene usare quella 
per la gestione dinamica dello stack.

Per quanto mi riguarda, la soluzione più veloce in assoluto che sono 
riuscito a trovare, puramente iterativa, è la seguente:

my @nodes;
sub iterative {
     @nodes = @_;

     foreach my $node ( @nodes ) {
         foreach my $tag (keys %$node) {
             print "$tag\n";
             push @nodes, $node->{$tag} if ref $node->{$tag}
         }
     }
}
itarative( XMLin( $data, KeepRoot => 1 ) );

E' di uno sfolgorante 8% più veloce di quella ricorsiva di Aldo (alla 
faccia delle sue "forzature" ;-) poi non rischia di incorrere nel 
warning di deep-recursion di perl, ed è sguaiatamente non-HOPpica.

Lo stack non viene mai deallocato, ma in realtà non serve perché è il 
limite superiore di occupazione di memoria che conta, e quello, come già 
detto, è invariante per qualsiasi soluzione.

La visita è diversa (è in ampiezza) e non c'è indentazione nella stampa, 
ma fornisce l'elenco dei tag come originariamente richiesto.

In realtà la ricorsione del Perl è molto più veloce di quanto 
ricordassi, e in questo caso è piuttosto difficile fare di meglio, 
infatti la mia soluzione rispetto a quella di Aldo contiene in 
definitiva solo microottimizzazioni, cercando in realtà di emulare il 
più fedelmente possibile la ricorsione di perl.

Se qualcuno sa fare di meglio si accomodi (use Benchmark)
;-)

P.S.
Il tuo client web-mail, perché non lo butti?

Ciao,
Emanuele.