Daniele Ludovici
Dare una riordinata in Perl
http://www.perl.it/documenti/articoli/2008/06/dare-una-riordi.html
© Perl Mongers Italia. Tutti i diritti riservati.

Una caratteristica molto interessante che incontriamo spesso in Perl è la possibilità di utilizzare alcune funzioni fornite dal linguaggio con molta flessibilità.
Un esempio? La funzione sort! "Cosa" fa non ve lo dico, credo sia piuttosto intuitivo, cercherò invece di spiegare "come" lo fa e mostrare attraverso alcune sue applicazioni quanto flessibile sia questa funzione.

Immaginate di avere un array contentente un insieme di lettere e di volerle ordinare alfabeticamente:

@lettere_disordinate = qw( d a n i e l e );

Il modo più semplice di utilizzare sort è chiamarla passandole una lista come argomento:

@ordinate = sort @lettere_disordinate;

stampiamo le lettere ordinate alfabeticamente:

print "@ordinate\n"; # stampa a d e e i l n

so far so good, molto facile ma la flessibilità dove sta? Ad esempio potremmo volere le nostre lettere in ordine alfabetico decrescente... Come fare a dirlo a sort? È possibile "spiegarle" come deve ordinare la lista in un modo piuttosto semplice e cioè:
* tramite un blocco: sort BLOCCO lista_da_ordinare
* tramite il nome di una funzione: sort NOME_FUNZIONE lista_da_ordinare

Nel blocco possiamo inserire codice come se stessimo scrivendo una funzione anonima (senza nome) in stile one-liner:

@ordinate = sort { $b cmp $a } @lettere_disordinate;

oppure possiamo scrivere il codice in una funzione separata

sub alfabetico_decrescente {
    return $b cmp $a
}

e chiamare sort passandole il nome della stessa:

@ordinate = sort alfabetico_decrescente @lettere_disordinate;

Come avviene l'ordinamento della lista? Dando una rapida occhiata alla pagina di manuale ci accorgiamo che sort è implementata nelle versioni recenti di Perl utilizzando l'algoritmo mergesort. A noi resta da capire come spiegare a sort il tipo di ordinamento che vogliamo, per questo usiamo un esempio piuttosto intuitivo. Immaginate le lettere dell'array che stavamo considerando prima, in maniera tale che scorrano da destra verso sinistra all'interno del blocco

{ $b cmp $a } d a n i e l e 

sort le prende a coppie e usando le due variabili speciali $a e $b fa questo

$a = 'd'; $b = 'a'; 

applica l'operatore "cmp" che restituisce -1 0 +1 a seconda che il valore di sinistra sia minore, uguale o maggiore lessicograficamente di quella che sta a destra. Cosa significa? Per ordinare, sort esamina i valori a coppie, e se sono nell'ordine sbagliato, li scambia di posto. Il blocco che gli passiamo determina quale sia l'ordine "giusto": se restituisce 1, sort capisce che i due elementi vanno scambiati;
* 0 indica che sono uguali (serve in alcune ottimizzazioni);
* -1 indica che vanno bene in quell'ordine.

Nel nostro caso 'a' è minore lessicograficamente di 'd' quindi cmp restituisce -1 e lascia invariato l'ordine 'd' 'a'.

Questo è esempio grafico serve a farci capire come possiamo spiegare a sort l'ordine che vogliamo, cambiando la posizione delle variabili $a e $b rispetto all'operatore al quale sono applicate.

Stesso discorso applicabile ai numeri con l'operatore spaceship <=> che restituisce al solito -1, 0, 1 a seconda che il valore... vabbè dai non ve lo ridico tanto è uguale a prima :)
Esempio:

@numeri_decrescenti = sort { $b <=> $a } 1 .. 9;

stampiamo:

print "@numeri_decrescenti\n"; => 9 8 7 6 5 4 3 2 1

Complichiamo le cose: abbiamo un insieme di numeri e li vogliamo in ordine crescente ma con un vincolo in più e cioè devono esser suddivisi in due gruppi, prima i pari e poi i dispari. La risposta è compatta e molto "perlish":

@list = (9,1,9,7,2,3,4,3,4,2,3,4,5,2,0,9);
@sorted = sort { ($a%2 <=> $b%2) || ($a <=> $b) } @list;
print "@sorted\n";
#risultato => 2 2 2 4 4 4 1 3 3 3 5 7 9 9 9

Che razza di accrocchio è mai questo??? Quello di cui abbiamo bisogno è ordinare prima di tutto in base al fatto che un numero sia pari o dispari: qualora i nostri due numeri siano entrambi pari o entrambi dispari allora li ordiniamo in ordine crescente.

Pari o dispari? Questo lo controlliamo utilizzando l'operatore modulo % su entrambe le variabili $a e $b. Ad esempio se $a è pari allora ($a%2) ci restuitirà 0 mentre se $b è dispari allora ($b%2) ci restituirà 1; quindi la prima parte del blocco che spiega a sort cosa fare (quella evidenziata)

($a%2 <=> $b%2) || ($a <=> $b)
|_____________|

sarà 0 <=> 1 vale a dire -1 e quindi tutti numeri pari vengono ad esser ordinati prima dei dispari. Qualora invece questa parte dell'espressione ci restituisca 0 (nel caso stessimo confrontando due pari o due dispari) allora passeremo, grazie all'operatore OR ||, all'espressione:

($a%2 <=> $b%2) || ($a <=> $b)
                   |_________|

che ordinerà i nostri due numeri pari (o dispari) in ordine crescente. Il gioco è fatto! Un po' più complicato sarebbe stato ordinare prima i numeri dispari e poi quelli pari mantenendo l'ordine crescente all'interno di ciascuno dei due gruppi. Questo perché l'ordinamento prima pari e poi dispari ci viene abbastanza gratuitamente per la natura dell'operatore % abbinato a <=> .

Per avere l'ordinamento inverso (dispari - pari) dobbiamo lavorarci un pochino... Vogliamo ottenere 1 3 3 3 5 7 9 9 9 0 2 2 2 4 4 4 . Utilizzate la sezione commenti di questo articolo per le risposte :-)

E ora trasformiamoci!

Abbiamo visto come ordinare le lettere, abbiamo visto come ordinare i numeri ma se avessimo lettere e numeri insieme a costituire un unico elemento come si comporterebbe sort? Vediamo un esempio per capire meglio di cosa stiamo parlando:

@confuse = qw( N P21 36 A 123 V C P10 P2 P11 P1 );

L'ELEMENTO che stiamo considerando è di questo tipo LETTERE-NUMERO, ad esempio 'P21'. Anche '3' o 'C' vi appartengono, ci possono quindi essere delle parti mancanti nell'elemento, che siano esse le lettere o il numero. A noi piacerebbe che fossero ordinate in questo modo:
* lettere in ordine crescente e
* se le lettere sono uguali allora si ordina in base al numero (sempre crescente).

Tornando al nostro esempio, il risultato che vogliamo è:

36 123 A C N P1 P2 P10 P11 P21 V

Chissà che combina sort nuda e cruda:

@in_qualche_modo_ordinate = sort @confuse;
print "@in_qualche_modo_ordinate\n"; # stampa 123 36 A C N P1 P10 P11 P2 P21 V

Deludente? No, ha fatto bene il suo compito! Se non le spieghiamo niente all'interno del blocco, sort esegue un ordinamento crescente su stringhe ($a cmp $b).

Ma noi le stiamo chiedendo di ordinare in ordine crescente e invece ci ha messo 123 prima di 36 :( Cerchiamo di capire perché 123 è minore di 36 se stiamo parlando di stringhe. Eseguendo 123 cmp 36 ci viene restituito -1 perché il primo carattere di 123 (cioè 1) è minore del corrispondente in 36 (e cioè 3) quindi 123 è minore di 36 string-wise! Bhuuu!!

Altra cosa strana da notare nella sequenza "in qualche modo ordinata" è P11 prima di P2. Il motivo? Sempre lo stesso! P è uguale a P, 1 è minore di 2, quindi P11 minore di P2. Mazzù!

La platea mormora e si domanda cosa possiamo inventarci per risolvere l'arduo compito...

Esiste un sistema molto potente ed elegante chiamato "Trasformazione di Schwartz". Matematici e secchioni stiano al loro posto, non stiamo parlando del noto teorema bensì dello yankee Randal L. Schwartz, perlista e ideatore di questa tecnica.

I secchioni in prima fila vogliono vedere il codice! Eccoli accontentati:

@ordinate =  map { $_->[2]}                        # (3)
             sort {  $a->[0] cmp $b->[0]           # (2)
                             || 
                     $a->[1] <=> $b->[1] 
             } 
             map { [m/(\D*)(\d*)/, $_] } @confuse; # (1)

quelli dell'ultima fila ora scalpitano per lasciare l'aula :-D

Come si legge questa pappardella? Beh, si parte dalla fine andando verso l'alto e cioè da @confuse che viene dato in pasto a map. Parafrasando il mio amico polettix in "Puoi ripetere" map è una sorta di catena di montaggio dove gli elementi della lista entrano da destra a sinistra nel blocco {}, si fa quel che si deve fare e in uscita si restituisce una lista che dipende da ciò che si è combinato dentro a { }. Questa lista sarà a sua volta l'input di sort che la ordinerà in base alla regola espressa nel suo blocco e restituirà un'altra lista che andrà in pasto al nostro ultimo map (il primo in alto (3)). Notate bene che all'interno di map l'ELEMENTO entrante è mappato sulla variabile $_

Cool! Ma qual è l'idea dietro tutto questo flusso? Ci creiamo un riferimento ad array anonimo costituito da alcuni campi che ci torneranno poi utili nelle prossime fasi. Il riferimento all'array anonimo lo creiamo tramite le parentesi quadre [ ]. Nell'array ci mettiamo: [LETTERE, NUMERO, ELEMENTO]. Iniziamo con l'isolare LETTERE e NUMERO dal nostro ELEMENTO (primo map in basso (1)). Questa cosa la otteniamo facendo pattern matching con m// (che se non specificato diversamente opera su $_ e cioè il nostro ELEMENTO) chiedendogli di fare match e raggruppare, tramite le parentesi, tutto ciò che non sia un numero (\D*) e tutto ciò che invece lo è (\d*).

Va detto che questo operatore m// usato in contesto lista restituisce gli elementi raggruppati tramite le parentesi. Adesso ci manca solo l'ELEMENTO. Ma non avevamo detto che $_ è l'ELEMENTO entrante in map? Quindi possiamo usare direttamente $_ e il gioco è fatto! Alla fine di tutta questa manfrina il nostro riferimento punterà un array costituito dai seguenti campi:

* LETTERE #posizione 0
* NUMERO #posizione 1
* ELEMENTO #posizione 2

Il risultato di map è quindi una collezione di riferimenti che andranno in pasto a sort e saranno mappati come al solito sulle variabili $a e $b del suo blocco:

$a->[LETTERE]  $b->[LETTERE]    # 0 
    [NUMERO]       [NUMERO]     # 1
    [ELEMENTO]     [ELEMENTO]   # 2

A questo punto siamo a posto. Dentro sort ordiniamo prima in base alle LETTERE che si trovano in posizione 0 del nostro array: $a->[0] cmp $b->[0] se le LETTERE sono uguali allora grazie all'operatore || ordiniamo in base al NUMERO: $a->[1] <=> $b->[1].

In uscita da sort ci ritroviamo una collezione di riferimenti ordinati in base alle proprietà che abbiamo specificato nel blocco. OK ma in @ordinate non ci vogliamo i riferimenti vero? Vogliamo metterci l'ELEMENTO ecco perché ce lo siamo tenuto buono buono nell'array. Ora per recuperarlo basta usare un altro map e pescare l'ultimo campo dell'array che lo contiene: map { $_->[2] } #(3). In @ordinate avremo tutti gli elementi ordinati in base alle regole specificate nel blocco di sort!

Altro regalo per la sezione commenti:

cosa dovremmo scrivere nel blocco di sort se volessimo ordinare allo stesso modo ma con l'aggiunta che prima vogliamo gli ELEMENTI che hanno le LETTERE e poi quelli solo con NUMERO? Il risultato che ci aspettiamo è: A C N P1 P2 P10 P11 P21 V 36 123. Suggerimento: bisogna controllare che l'elemento abbia la parte "letteraria" uguale a '' e invertire l'ordinamento solo in questo caso. Il resto è uguale.

Abbiamo mostrato come la funzione di sorting di Perl sia molto flessibile specialmente se combinata con altri strumenti quali ad esempio "map". Questa tecnica è particolarmente flessibile perché nel primo map possiamo separare gli elementi nel modo che riteniamo più conveniente per il successivo ordinamento. In sort ordiniamo a piacimento e poi con l'ultimo map andiamo a ripescare l'elemento ordinato che ci siamo portati dietro nell'array anonimo.

Tutto qua?

In realtà ci sarebbe da parlare per ore di tecniche di sorting e problemi affini ma l'intento di questo articolo è stato quello di far intuire potenza e flessibilità degli strumenti presentati. A voi la palla, buona lettura e buon ordinamento a tutti :-)

print sort qw/ puntate alle prossime /;

Riferimenti:

* Gli amanti di CPAN sapranno bene che per risolvere alcuni problemi di ordinamento "misto" come quello che abbiamo risolto con la prima Trasformazione di Schwartz, esiste un modulo chiamato Sort::Naturally. Noi abbiamo preso spunto dal problema risolto da questo modulo per mostrare una delle possibili applicazioni della "Trasformazione di Schwartz"
* Potete trovare altri interessanti suggerimenti sulle tecniche di sorting andandovi a leggere perlfaq4 o semplicemente digitando perldoc -q sort
* Le pagine di manuale di sort e map, le trovate con perldoc -f sort e perldoc -f map
* Aprite google e scrivete sort site:stonehenge.com , sono tutti gli articoli sulle tecniche di sorting scritti da Randal L. Schwartz