Algoritmi

La scelta di una struttura di dati è guidata dall'uso che si vuole fare dei dati (possiamo pensare ai Large Language Models come un esempio estremo di dati organizzati secondo l'uso atteso). Ci sono usi che rappresentano una frazione grande delle applicazioni di tecnologie IT nel mondo - procedure che meritano di venire standardizzate per le stesse ragioni che giustificano la standardizzazione delle strutture di dati (Efficienza, Astrazione, Possibilità di riutilizzo). A strutture di dati standard possono venire astrattamente associate alcune procedure standard, e non altre.

Ad una procedura che venga ben definita per operare su un problema "standard", con una struttura di dati "standard", in modo ripetibile e riutilizzabile, attribuiamo il nome generico di algoritmo.

Esempio canonico: Ricerca e ordinamento

Il sistema più elementare per ricercare un dato specifico in una collezione di dati consiste nell'esaminare uno dopo l'altro tutti i dati presenti nella collezione.
Nel peggiore dei casi, (che può capitare molto spesso, per esempio se il dato richiesto non c'è...), dovremo esaminare tutti i dati della nostra collezione: un'operazione il cui costo dipende linearmente dal numero dei dati.

Se i dati fossero ordinati in base alla grandezza sulla quale deve avvenire la ricerca e se fosse possibile accedere direttamente ai dati secondo il loro numero d'ordine, potremmo tentare un approccio più astuto come quello di una ricerca binaria.
Per effettuare una ricerca binaria su una collezione di dati contigua e ordinata basta scegliere un punto in mezzo e verificare se il valore che stiamo cercando è maggiore, minore (o uguale) al valore scelto. A questo punto basta continuare, ripetendo l'operazione sulla metà rimasta.

Dal momento che procediamo continuando a dividere il campione a metà, all'aumentare del numero degli elementi del campione il numero di operazioni necessario per completare la ricerca cresce all'incirca secondo il logaritmo in base 2 del numero di elementi, quindi molto meno che linearmente.

Il problema della ricerca e quello dell'ordinamento sono strettamente imparentati. Anche l'ordinamento è una procedura standard. Quali sistemi abbiamo dunque a disposizione per mettere in ordine una collezione di elementi disordinati?

Ordinamento per inserzione

Un possibile metodo (detto del "giocatore di carte", o anche insertion sort) consiste nel prelevare uno ad uno gli elementi da inserire, e creare una nuova lista ordinata inserendo ogni elemento nella posizione giusta. Tale sistema non è particolarmente efficiente, come constateremo fra poco, ma presenta alcuni innegabili vantaggi: in primo luogo permette di effettuare l'ordinamento nella stessa area di memoria occupata dai dati, senza richiedere la copia in un'area supplementare (in-place sort). In secondo luogo è stabile, nel senso che non viene cambiata la posizione relativa degli elementi con chiave di ricerca uguale. Infine è adatto all'uso con contenitori cone le linked list (che non possono essere indirizzati in modo assoluto). In moltissime situazioni quindi questo sistema può risultare più che sufficiente.

Si può fare di meglio? Si, molto probabilmente (ma non ingenuamente) affidandosi agli algoritmi di ricerca e ordinamento inclusi nelle librerie standard del nostro linguaggio di programmazione preferito. Per avere un'idea di come funziona un algoritmo di ordinamento generico ne descriviamo uno.

Quicksort

Supponiamo di avere una pila di libri da mettere in ordine alfabetico per autore. Possiamo iniziare scegliendo uno dei libri (ad esempio un autore che inizia con la "L" o con la "M") e dividendo i libri in due pile: una con tutti i libri che precedono in ordine alfabetico l'autore scelto, ed una con tutti i libri che seguono (il libro scelto come "elemento separatore" può appartenere ad una qualsiasi delle due pile). A questo punto possiamo ripetere la procedura su ciascuna delle due pile ottenute (ricorsivamente). Continuando a dividere rimarremo con gruppetti di due o tre libri, ed infine con libri singoli, che a questo punto si troveranno in ordine alfabetico.
Ecco un altro esempio con i numeri, che ci aiuta a capire come questa strategia possa essere convertita in un algoritmo:

Osservando bene si nota che il caso nella figura è assolutamente ottimale! Ogni volta siamo riusciti a scegliere un elemento "separatore" che divide la collezione esattamente in due. Il problema principale del quicksort riguarda proprio la strategia utilizzata per scegliere l'elemento separatore. Può sembrare sorprendente che uno dei sistemi migliori per effettuare tale scelta sia quello di affidarsi al caso. Questa strategia è in pratica l'unica utilizzata, eventualmente con una sola miglioria: scegliere l'elemento intermedio fra tre scelti a caso.

Misura e confronto dell'efficienza degli algoritmi

Esistono vari criteri, più o meno ben definiti, per analizzare l'efficienza di un algoritmo:

Analisi del caso peggiore. Se è chiaro che le prestazioni di un algoritmo, in dipendenza dalla quantità e qualità delle operazioni da svolgere, possono avere elementi di forte discontinuità (legati ad esempio alle varie strutture condizionali presenti nel codice), non è atrettanto chiaro perché proprio il comportamento nel caso peggiore dovrebbe riflettere fedelmente l'efficienza "media" di un algoritmo.
Si tratta effettivamente di un criterio piuttosto empirico, ma la sua validità è legata all'esistenza di una vasta classe di applicazioni (come gli algoritmi di ricerca) in cui il caso "peggiore" (= non trovare il dato cercato) si manifesta abbastanza spesso da dominare effettivamente le prestazioni. Inoltre è molto difficile definire l'efficienza "media" di un algoritmo, nel senso che le caratteristiche "medie" dei dati che vengono sottoposti all'algoritmo stesso possono variare drammaticamente con l'applicazione. L'efficienza "nel caso migliore" è invece decisamente poco utile per confrontare vari tipi di algoritmo, nel senso che spesso la risposta di vari algoritmi nel caso migliore è identica. Nel caso degli algoritmi di ricerca, ad esempio, nel caso "migliore" l'elemento cercato viene trovato subito, e dunque il tempo e le risorse utilizzate in tutti i casi sono praticamente nulli.
Valutazione dell'ordine di complessità computazionale dell'algoritmo. Questo è un criterio decisamente più formale, teso a valutare l'andamento di crescita delle risorse impegnate da un algoritmo al crescere della quantità di dati da trattare. Si utilizza la nozione di limite superiore a meno di una costante (O-grande) analogamente a quanto si fa per le serie numeriche. Si riesce così a valutare se un certo algoritmo cresce in complessità in modo lineare (O(n)), in modo logaritmico (O(log₂n)), o in modo quadratico (O(n²)), effettuando poi un confronto ragionato. Proviamo a stimare l'ordine di complessità di alcuni algoritmi visti finora:
- Inserzione di un elemento in una linked list: richiede un tempo costante, dunque l'ordine di complessità è O(c) = O(1).
- Inserzione di un elemento in mezzo ad un array: richiede di spostare un certo numero degli elementi dell'array per ricavare lo spazio per il nuovo elemento. L'ordine di complessità è dunque O(c n)=O(n): la quantità di risorse utilizzate cresce linearmente con il numero degli elementi.
- Ricerca lineare su un campione di n elementi: richiede di esaminare una frazione di tutti gli n elementi. Dunque l'ordine di complessità è ancora una volta O(cn)=O(n).
- Ricerca binaria su un campione di n elementi ordinati: nella procedura si continua a dividere in due il campione fino a trovare l'elemento richiesto. Se l'elemento non viene trovato vengono effettuate log₂n divisioni. Di conseguenza l'ordine di complessità della procedura è O(log₂n), e rappresenta il caso migliore che si possa attendere in pratica da un algoritmo.
- Ordinamento per inserzione di un campione di n elementi: richiede di esaminare la lista degli elementi finora ordinati per tutti gli elementi del campione salvo il primo. Sono quindi necessarie (n-1) operazioni, ciascuna composta da un ciclo che, nel caso peggiore, è rispettivamente di 1,2,3,4,5,.... iterazioni. Il numero totale di operazioni si comporta dunque come la somma dei numeri da 1 a (n-1), che è n(n-1)/2, dunque O(n²).
- Quicksort di un campione di n elementi: nell'algoritmo di quicksort vengono verificati (ed eventualmente scambiati) tutti gli n elementi del campione, e questo viene ripetuto continuando a dividere il campione in due, per un totale di log₂n volte. Pertanto l'ordine di complessità risultante è O(n log₂n).
Misura del consumo di risorse. Il metodo sperimentale è l'unico che permetta di tener conto dell'effettiva natura dei dati, come pure di tutte le peculiarità e dei comportamenti discontinui dell'algoritmo utilizzato. Se l'importanza della valutazione è solo relativa (quando ad esempio si vuole fare un confronto fra varie soluzioni), questo metodo può essere più che sufficiente. Se invece la complicazione dell'algoritmo è eccessiva (oppure l'algoritmo è sconosciuto), questa può essere l'unica soluzione disponibile. Questa misura si può sempre realizzare con l'aiuto del Sistema Operativo.

Linus Torvalds: "Good programmers worry about data structures".

Per approfondire:

M.T. Goodrich et al. Data Structures and Algorithms in XXX, Wiley, 201r31-2025
M. La Rocca Grokking Data Structures, Manning Publications, 2024
Wes McKinney, "Python for Data Analysis", 3^rd edition

Proprietà degli iterables di Python

Molti contenitori 'built-in' di Python (lists, tuples, dictionaries, sets), oltre agli ndarrays di NumPy, e Series e Dataframe di pandas, oltre ad essere oggetti iterable, condividono queste funzioni (tabelle da Wes McKinney, "Python for Data Analysis"):

Ufunc unarie:
abs, fabs	Calcola il valore assoluto elemento per elemento per valori di tipo intero, virgola mobile o complesso.
sqrt	Calcola la radice quadrata di ogni elemento (equivalente a `arr ** 0.5`)
square	Calcola il quadrato di ogni elemento (equivalente a `arr ** 2`)
exp	Calcola l'esponenziale e^x di ogni elemento
log, log10, log2, log1p	Rispettivamente, calcola il logaritmo naturale (base e), il logaritmo decimale, il logaritmo in base base 2, e il logaritmo di (1 + x) di ogni elemento
sign	Calcola il segno di ogni elemento: 1 (positivo), 0 (zero), or –1 (negativo)
ceil	Calcola il 'ceiling' di ogni elemento (cioè il più piccolo intero maggiore o uguale all'elemento)
floor	Calcola il 'floor' di ogni elemento (cioè il più grande intero minore o uguale all'elemento)
rint	Arrotonda gli elementi all'intero più vicino, preservandone il dtype
modf	Restituisce le parti frazionali ed intere degli elementi dell'array in array separati
isnan	Restituisce un array di booleani che indicano se ciascun elemento è is NaN (Not a Number)
isfinite, isinf	Restituisce un array di booleani che indicano se ciascun elemento è, rispettivamente, finito (non-inf, non-NaN) oppure infinito
cos, cosh, sin, sinh, tan, tanh	Funzioni trigonometriche ordinarie o iperboliche.
arccos, arccosh, arcsin, arcsinh, arctan, arctanh	Funzioni trigonometriche inverse
logical_not	Calcola il valore di verità di 'not x' elemento per elemento (equivalente a `~arr`).

Ufunc binarie:
add	Somma gli elementi corrispondenti di due array
subtract	Sottrae dal primo array gli elementi del secondo
multiply	Moltiplica elemento per elemento i due array
divide, floor_divide	Divide elemento per elemento i due array (troncando il resto in `floor_divide`)
power	Eleva gli elementi del primo array alle potenze contenute nel secondo
maximum, fmax	Massimo di ciascuna coppia di elementi corrispondenti; `fmax` ignora i NaN
minimum, fmin	Minimo di ciascuna coppia di elementi corrispondenti; `fmin` ignora i NaN
mod	Modulo (resto della divisione) elemento per elemento.
copysign	Copia il segno dei valori del secondo argomento nei valori del primo argomento
greater, greater_equal, less, less_equal, equal, not_equal	Confronta gli elementi uno per uno. Il risultato è un array di booleani. (equivalente agli operatori `>, >=, <, <=, ==, !=`)
logical_and, logical_or, logical_xor	Calcola elemento per elemento il valore di verità della corrispondente operazione logica (equivalente agli operatori `& \|, ^`)

Ufunc di `numpy` (o `pandas`):
count	Conta il numero di valori non-NA
describe	Calcola statistiche riassuntive di una 'Series' or di ciascuna colonna di un DataFrame.
min, max	Calcola i valori minimo o massimo argmin,
argmin, argmax	Calcola le posizioni (numeri interi) dove si trova l'elemento minimo o, rispettivamente, massimo idxmin,
idxmin, idxmax	Calcola le 'label' degli indici dove si trova l'elemento minimo o, rispettivamente, massimo
quantile	Calcola il quantile del campione, cha varia da 0 a 1
sum	Somma dei valori
mean	Media dei valori
median	Mediana aritmetica (50% quantile) dei valori
mad	Deviazione assoluta media dal valor medio
prod	Prodotto di tutti i valori
var	Varianza dei valori del campione
std	Deviazione standard del campione
skew	Skewness (terzo momento) del campione
kurt	Kurtosis (quarto momento) del campione
cumsum	Somma cumulativa del campione
cummin, cummax	Valore rispettivamente minimo o massimo cumulativo dei valori
cumprod	Prodotto cumulativo dei valori
diff	Calcola la prima differenza aritmetica (utile per le serie temporali)
pct_change	Calcola le variazioni percentuali

Metodi statistici per gli array:
sum	Somma tutti gli elementi di un array, oppure lungo una dimensione/asse; gli array di lunghezza zero hanno somma 0
mean	Media aritmetica; gli array di lunghezza zero hanno media NaN
std, var	Rispettivamente, deviazione standard e varianza, rispettivamente, con regolazione opzionale dei gradi di libertà (denominartore di default n)
min, max	Minimo e massimo
argmin, argmax	Indici degli elementi minimo e massimo, rispettivamente
cumsum	Somma cumulativa degli elementi iniziando da 0
cumprod	Prodotto cumulativo degli elementi iniziando da 1

*Metodi di sort:*
unique(x)	Calcola e ordina gli elementi unici in x
intersect1d(x, y)	Calcola e ordina gli elementi comuni in x and y
union1d(x, y)	Calcola e ordina l'unione degli elementi di x e y
in1d(x, y)	Calcola un array booleano che indica se ciascun elemento di x è contenuto in y
setdiff1d(x, y)	Differenza degli insiemi:elementi in x che non sono in y
setxor1d(x, y)	Differenza simmetrica degli insiemi: elementi che sono in uno dei due array, ma non in entrambi

Comuni funzioni di algebra lineare:
diag	Return the diagonal (or off-diagonal) elements of a square matrix as a 1D array, or convert a 1-D array into a square matrix with zeros on the off-diagonal
dot	Moltiplicazione di matrici
trace	Calcola la somma degli elementi sulla diagonale
det	Calcola il determinante della matrice
eig	Calcola gli autovalori e gli autovettori di una matrice quadrata
inv	Calcola l'inversa di una matrice quadrata
pinv	Calcola la pseudo-inversa di Moore-Penrose di una matrice
qr	Calcola la decomposizione QR
svd	Calcola la decomposizione a valori singolari (SVD)
solve	Risolve (calcola x) il sistema lineare `Ax = b`, dove A è una matrice quadrata
lstsq	Calcola la soluzione ai minimi quadrati di `Ax = b`

Lista parziale delle funzioni di `numpy.random`:
seed	Seme del generatore di numeri casuali
permutation	Restituisce la permutazione casuale di una sequence, o un range permutato
shuffle	Permuta casualmente una sequenza 'in-place'
rand	Estrae campioni da una distribuzione uniforme
randint	Estrae numeri casuali interi in un certo range
randn	Estrae campioni da una distribuzione normale di media 0 e deviazione standard (interfaccia simile a MATLAB)
binomial	Estrae campioni da una distribuzione binomiale
normal	Estrae campioni da una distribuzione normale (Gaussiana)
beta	Estrae campioni da una distribuzione beta
chisquare	Estrae campioni da una distribuzione chi-quadrato
gamma	Estrae campioni da una distribuzione gamma
uniform	Estrae campioni da una distribuzione uniforme nell'intervalllo [0, 1)

Esempi di strutture di dati astratte

Algoritmi

Esempio canonico: Ricerca e ordinamento

Ordinamento per inserzione

Quicksort

Misura e confronto dell'efficienza degli algoritmi

Per approfondire:

Proprietà degli iterables di Python

Ufunc unarie:

abs, fabs

sqrt

square

exp

log, log10, log2, log1p

sign

ceil

floor

rint

modf

isnan

isfinite, isinf

cos, cosh, sin, sinh, tan, tanh

arccos, arccosh, arcsin, arcsinh, arctan, arctanh

logical_not

Ufunc binarie:

add

subtract

multiply

divide, floor_divide

power

maximum, fmax

minimum, fmin

mod

copysign

greater, greater_equal, less, less_equal, equal, not_equal

logical_and, logical_or, logical_xor

Ufunc di numpy (o pandas):

count

describe

min, max

argmin, argmax

idxmin, idxmax

quantile

sum

mean

median

mad

prod

var

std

skew

kurt

cumsum

cummin, cummax

cumprod

diff

pct_change

Metodi statistici per gli array:

sum

mean

std, var

min, max

argmin, argmax

cumsum

cumprod

Metodi di sort:

unique(x)

intersect1d(x, y)

union1d(x, y)

in1d(x, y)

setdiff1d(x, y)

setxor1d(x, y)

Comuni funzioni di algebra lineare:

diag

dot

trace

det

eig

inv

pinv

Ufunc di `numpy` (o `pandas`):

**Metodi di sort:**

Lista parziale delle funzioni di `numpy.random`: