\documentclass{howto}
\usepackage[T1]{fontenc}
\usepackage[italian]{babel}

\title{Mini-HOWTO sull'ordinamento dei dati}

% Increment the release number whenever significant changes are made.
% The author and/or editor can define 'significant' however they like.
\release{0.01}

\author{Andrew Dalke}
\authoraddress{\email{dalke@bioreason.com}}

\begin{document}
\maketitle

\begin{abstract}
\noindent
Questo documento � un piccolo resoconto su una mezza dozzina di metodi
di organizzare una lista di dati con il metodo built-in
\method{sort()}.  Traduzione italiana a cura di Carlos
(enne.enne at tiscalinet.it). 

\`E disponibile presso la pagina degli HOWTO Python all'indirizzo
\url{http://www.python.org/doc/howto}, la traduzione
presso la pagina \url{http://www.zonapython.it/doc/howto/}.
\end{abstract}

\tableofcontents

Le liste in Python hanno il metodo built-in \method{sort()}.  
Siccome manca una descrizione univoca e specifica sui molti modi in
cui � possibile ordinare una lista, questo documento cerca di fornirne
una descrizione.

\section{Ordinare dati di tipo elementare}

Per un ordinamento in ordine crescente basta chiamare il metodo
\method{sort()} di una lista.

\begin{verbatim}
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> print a
[1, 2, 3, 4, 5]
\end{verbatim}

Sort prende una funzione facoltativa che pu� essere
chiamata per operare confronti.  La routine predefinita di sort �
equivalente a 

\begin{verbatim}
>>> a = [5, 2, 3, 1, 4]
>>> a.sort(cmp)
>>> print a
[1, 2, 3, 4, 5]
\end{verbatim}

ove \function{cmp} � la funzione built-in che confronta gli oggetti
\code{x} e \code{y}, restituendo -1, 0 o 1 a seconda se \code{x < y},
\code{x == y} o \code{x > y}.  Affinch� la lista  finale abbia senso,
durante l'ordinamento i rapporti devono restare costanti. 

Volendo, per il confronto si pu� definire una propria funzione; per i
numeri interi (ed i numeri in generale) ad esempio possiamo scrivere: 

\begin{verbatim}
>>> def compara_numeri(x, y):
>>>    return x-y
>>> 
>>> a = [5, 2, 3, 1, 4]
>>> a.sort(compara_numeri)
>>> print a
[1, 2, 3, 4, 5]
\end{verbatim}

Per inciso, la funzione non lavora se il risultato dell'operazione � fuori dai 
limiti, come in \code{sys.maxint - (-1)}.

Se non si vuole definire una funzione con un nome nuovo, se ne pu�
creare una anonima mediante la funzione \keyword{lambda}, come questa: 

\begin{verbatim}
>>> a = [5, 2, 3, 1, 4]
>>> a.sort(lambda x, y: x-y)
>>> print a
[1, 2, 3, 4, 5]
\end{verbatim}

Se si desidera l'ordine inverso � sufficiente scrivere:

\begin{verbatim}
>>> a = [5, 2, 3, 1, 4]
>>> def inverti_numeri(x, y):
>>>     return y-x
>>> 
>>> a.sort(inverti_numeri)
>>> print a
[5, 4, 3, 2, 1]
\end{verbatim}

(un'implementazione pi� generale potrebbe restituire \code{cmp(y,x)} o
\code{-cmp(x,y)}). 

Per�, dato che si fa prima a non obbligare Python a chiamare una
funzione per ogni confronto, se si vuole una lista ordinata
all'inverso per dati di tipo elementari, �  meglio eseguire prima
l'ordinamento diretto e poi usare il metodo \method{reverse()}. 

\begin{verbatim}
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a.reverse()
>>> print a
[1, 2, 3, 4, 5]
\end{verbatim}

Ecco una stringa di confronto insensibile a maiuscole e minuscole con
la funzione \keyword{lambda}: 

\begin{verbatim}
>>> import string
>>> a = string.split("Trattasi di una stringa di prova, da NN.")
>>> a.sort(lambda x, y: cmp(string.lower(x), string.lower(y)))
>>> print a
['da', 'di', 'di', 'NN.', 'prova,', 'stringa', 'Trattasi', 'una']
\end{verbatim}

Questo evita di dover convertire le maiuscole di una parola ad ogni
confronto.  Talora, pu� essere pi� spiccio conteggiarle una volta e
poi usare i valori ottenuti, come nel seguente esempio.

\begin{verbatim}
>>> parole = string.split("Trattasi di una stringa di prova, da NN.")
>>> offsets = []
>>> for i in range(len(parole)):
...     offsets.append( (string.lower(parole[i]), i) )
... 
>>> offsets.sort()
>>> nuove_parole = []
>>> for nonticurare, i in offsets:
...      nuove_parole.append(parole[i])
... 
>>> print nuove_parole
\end{verbatim}

La lista \code{offsets} viene inizializzata in una tupla di stringhe
composte di caratteri in lettere minuscole, alla corretta posizione,
nella lista \code{parole}, e quindi ordinata.  Il metodo di
ordinamento in Python ordina le tuple confrontandone i termini; dati
\code{x} e \code{y}, confronta \code{x[0]} e \code{y[0]}, \code{x[1]} e
\code{y[1]}, ecc.  finch� ci sia differenza. 

Ne risulta che la lista \code{offsets} � ordinata a partire dal suo
primo termine e il secondo fa capire dove fosse disposto il dato in
origine.  (Il ciclo \code{for} assegna \code{nonticurare} e d\code{i} ai
due campi di ogni termine della lista, ma basta gi� il valore
dell'indice.) 

Un altro modo di implementare ci� � memorizzare il dato d'origine come
secondo termine della lista \code{offsets}, come in:

\begin{verbatim}
>>> parole = string.split("Trattasi di una stringa di prova, da NN.")
>>> offsets = []
>>> for parola in parole:
...     offsets.append( (string.lower(parola), parola) )
... 
>>> offsets.sort()
>>> nuove_parole = []
>>> for parola in offsets:
...     nuove_parole.append(parola[1])
... 
>>> print nuove_parole
\end{verbatim}

Questo non � sempre corretto, poich� i secondi termini nella lista (la
parola, in questo esempio) vengono confrontati quando i primi sono
uguali.  Se ci� succede molte volte, un confronto dei due oggetti
risulta sempre superfluo --- il che, se per lo pi� i termini si
equivalgono e gli oggetti definiscono i propri metodi \method{__cmp__}
(ma con l'ulteriore incombenza di determinare se \method{__cmp__} sia
definito), costituisce un grande spreco. 

Ancora, per liste molto estese, o nelle quali il calcolo delle
informazioni di confronto sia gravoso, gli ultimi due esempi sono
probabilmente i modi pi� rapidi per ordinarle; non funzioneranno,
per�, con dati difficili a disporsi, come i numeri complessi (la cui
conoscenza, peraltro, non � essenziale). 

\section{Confrontare classi}

Il confronto fra due tipi elementari di dati --- come interi o stringhe
--- � incorporato in Python ed ha un senso.  C'� un modo predefinito di
confrontare istanze di classi, anche se di solito non � molto utile; con
il metodo \method{__cmp__} si possono definire dei confronti
personalizzati, come in: 

\begin{verbatim}
>>> class Spam:
>>>     def __init__(self, spam, eggs):
>>>         self.spam = spam
>>>         self.eggs = eggs
>>>     def __cmp__(self, other):
>>>         return cmp(self.spam+self.eggs, other.spam+other.eggs)
>>>     def __str__(self):
>>>         return str(self.spam + self.eggs)
>>> 
>>> a = [Spam(1, 4), Spam(9, 3), Spam(4,6)]
>>> a.sort()
>>> for spam in a:
>>>   print str(spam)
5
10
12
\end{verbatim}

Se si desidera un ordinamento in base ad un attributo specifico della
classe, correttamente basterebbe definire il metodo \method{__cmp__}
per confrontare quei valori, ma non si pu�, volendo un confronto fra
attributi diversi in tempi diversi.  Invece, bisogna tornare indietro
e tradurre la funzione di confronto in criterio di ordinamento, come
in: 

\begin{verbatim}
>>> a = [Spam(1, 4), Spam(9, 3), Spam(4,6)]
>>> a.sort(lambda x, y: cmp(x.eggs, y.eggs))
>>> for spam in a:
>>>   print spam.eggs, str(spam)
3 12
4 5
6 10
\end{verbatim}

Volendo confrontare due attributi a scelta (senza preoccuparsi troppo
delle prestazioni), si pu� addirittura definire il proprio oggetto per
il confronto, usando la capacit� delle classi di emulare funzioni
definendo il metodo \method{__call__}, come in: 

\begin{verbatim}
>>> class CmpAttr:
>>>     def __init__(self, attr):
>>>         self.attr = attr
>>>     def __call__(self, x, y):
>>>         return cmp(getattr(x, self.attr), getattr(y, self.attr))
>>> 
>>> a = [Spam(1, 4), Spam(9, 3), Spam(4,6)]
>>> a.sort(CmpAttr("spam"))  # ordina in base all'attributo "spam" 
>>> for spam in a:
>>>    print spam.spam, spam.eggs, str(spam)
1 4 5
4 6 10
9 3 12

>>> a.sort(CmpAttr("eggs"))   # riordina in base all'attributo "eggs"
>>> for spam in a:
>>>    print spam.spam, spam.eggs, str(spam)
9 3 12
1 4 5
4 6 10
\end{verbatim}

Naturalmente, se si cerca un ordinamento pi� rapido, si possono estrarre gli
attributi in una lista intermedia e ordinare quest'ultima.

E, cos�, ecco qua sei modi diversi di definire come ordinare una lista:
\begin{itemize}
 \item con il metodo predefinito;
 \item con una funzione per il confronto;
 \item al rovescio, senza l'uso di funzioni per il confronto;
 \item tramite una lista intermedia (due forme);
 \item usando una classe dove si � definito il proprio metodo __cmp__;
 \item utilizzando la funzione sort di un oggetto.
\end{itemize}

\end{document}
% LocalWords:  maxint
