Continua la serie di progetti sviluppati a scopi didattici per l’Università di Urbino “Carlo Bo”.

Specifica del problema

Sia dato un semplice database che rappresenta un elenco di studenti che hanno sostenuto un esame.

Il database è organizzato sotto forma di file di testo su 3 colonne contenenti informazioni relative a (Cognome, Matricola, Voto) come ad esempio:

Scrivere un programma ANSI C che acquisisce il database da file, ne effettua un ordinamento in base alla chiave primaria (Cognome) o alle chiavi secondarie (Matricola, Voto) sulla base della scelta dell’utente e produce in uscita il database ordinato. L’ordinamento sulle chiavi secondarie deve conservare l’ordine relativo prodotto dalla chiave primaria.

Analisi del problema

Il problema richiede di ordinare una tabella mediante l’uso di un algoritmo stabile, ovvero un procedimento che, in presenza di più chiavi di ordinamento, preservi l’ordine relativo prodotto da altre chiavi; è facilmente intuibile che il problema posto sia decidibile, ovvero che esiste un algoritmo che lo risolve in tempo finito e per una qualunque istanza di dati.

Come da specifica, il dato di ingresso per il programma è costituito da un file, quale rappresentazione testuale della tabella del database; il programma impone che il formato del file sia CSV, ovvero delimitato da un determinato separatore di campo.

Per semplicità, si assume che il file sia sintatticamente corretto, ovvero che non esistano righe (record) che non abbiano i tre campi valorizzati correttamente.

L’output del programma sarà la medesima tabella, opportunamente formattata, ordinata secondo i criteri che l’utente potrà specificare da riga di comando, ed eventuali messaggi d’errore.

Progettazione dell’algoritmo

La scelta della struttura dati e del relativo algoritmo tiene conto dei parametri dettati dalla specifica del problema: l’efficacia dell’algoritmo di ordinamento sarà il parametro fondamentale per la scelta del modus operandi; l’analisi non terrà conto delle comuni problematiche relative alla gestione di una base dati, quale la gestione degli indici, un’efficiente gestione dello storage o la disponibilità del dato a fronte di crash applicativi.

Si è scelto di articolare il programma in tre fasi distinte:

* analisi dei parametri forniti su riga di comando: di particolare rilievo, la possibilità di definire un criterio di ordinamento; * lettura del file contenente i dati e relativa creazione della struttura dati in memoria; * stampa dei dati ordinati e successiva deallocazione della struttura dati.

Struttura dati

Al fine di risolvere il problema fornito in modo ottimale, si è scelto di adottare una struttura dati del tipo albero rosso nero, particolare evoluzione dell’albero binario.

La modalità di rappresentazione del dato in memoria non può essere affidata ad una struttura statica quale il vettore1: tale soluzione, infatti, risulterebbe inefficiente in termini computazionali, in quanto gli algoritmi di ordinamento di vettori sono caratterizzati, nel caso migliore, da una complessità pari a n·log(n); non è inoltre noto a priori il numero di record che il vettore dovrebbe contenere, il che renderebbe la soluzione poco flessibile e scalabile.

La struttura dati originale prevede l’uso di un particolare nodo chiamato “sentinella”, in modo tale che non esistano foglie e tutti i nodi puntino alla sentinella: l’implementazione proposta farà uso di un puntatore nullo piuttosto che allocare un nodo.

Algoritmo

Il metodo di ordinamento scelto è di tipo interno, in quanto il file da ordinare può essere contenuto in memoria: questo approccio permette di accedere direttamente ad un record generico della tabella, riducendo sensibilmente i tempi di ordinamento; al contrario, un ordinamento esterno prevede che i dati risiedano su disco e si possa accedere ad essi solo in modo sequenziale o al più per grandi blocchi.

Sebbene l’implementazione di un albero rosso-nero risulti complessa, questo offre un eccellente tempo di esecuzione anche nel caso peggiore. L’implementazione proposta segue il paradigma di massimizzare l’efficienza in termini temporali di esecuzione, a discapito di un maggiore utilizzo di memoria: questa scelta progettuale si basa sulla considerazione che il sistema operativo, sfruttando diverse tecniche di virtualizzazione e gestione della memoria di sistema, metta a disposizione di un programma in esecuzione un quantitativo di memoria praticamente illimitato, al contrario del fattore “tempo” che non può essere riutilizzato e condiviso. L’algoritmo di ordinamento proposto prevede di memorizzare il record della tabella all’interno di un nodo dell’albero: ne consegue che l’operazione di lettura del file, la relativa creazione dei nodi e l’inserimento degli stessi all’interno dell’albero, generi un albero perfettamente bilanciato ed ordinato secondo i criteri richiesti. Nella tabella seguente vengono riassunte le principali proprietà, in termini di efficienza di algoritmo:

Si fa riferimento ad un albero contenente “n” nodi. I suddetti valori rappresentano il caso peggiore che si può verificare.

Le operazioni di lettura su un albero rosso-nero non richiedono particolari considerazioni rispetto a quelle utilizzate per gli alberi binari di ricerca, poiché gli alberi rosso-neri sono una loro specializzazione.

Prima fase: analisi dei parametri

Il programma inizierà la sua esecuzione inizializzando le strutture dati e le variabili necessarie al suo funzionamento. Successivamente verranno analizzati i parametri specificati su riga di comando, necessari per definire il nome del file contenente la tabella, nonché per modificare alcuni comportamenti predefiniti dell’applicativo.

Seconda fase: lettura del file di input

La lettura del file di input corrisponde alla fase più rilevante dell’applicazione: durante questa fase, in corrispondenza di ogni record letto dal file, verrà creato un nuovo nodo ed effettuato un inserimento nell’albero, qualora questa operazione risulti possibile.

L’implementazione della struttura dati e delle funzioni necessarie al suo mantenimento costituiscono una parte statica ed immutabile del programma; al contrario, la funzione preposta al confronto di due nodi generici tiene conto dei criteri di ordinamento specificati dall’utente.

Si è scelto di creare tre funzioni differenti (compare_name, compare_mark e compare_registration) preposte al confronto di due generici nodi dell’albero, ognuna delle quali tiene conto di uno solo dei tre campi del record; un vettore di puntatori a funzione verrà opportunamente inizializzato durante la prima fase con queste tre funzioni, seguendo l’ordine specificato dai criteri di ordinamento indicati dall’utente; in ultimo, la funzione che dovrà effettuare il confronto tra due nodi dell’albero, scorrerà il vettore ed userà la sotto-funzione specifica.

Le funzioni di ordinamento sono necessarie per individuare il punto esatto dell’albero nel quale inserire il nuovo nodo; il risultato immediato di un inserimento o di una cancellazione può corrispondere ad una violazione di una delle quattro proprietà fondamentali dell’albero rosso-nero: ristabilire tali proprietà richiede un numero limitato di operazioni, che possono avere una complessità costante nel caso medio, logaritmica nel caso peggiore.

Terza fase: stampa dei risultati

La terza fase si limita ad una ricorsione sull’albero per stampare i nodi presenti ed a una successiva fase di deallocazione della struttura dati utilizzata. Va sottolineato che la visita ricorsiva dell’albero per la cancellazione di un nodo, è di tipo non lineare: non è pertanto possibile ottimizzare ulteriormente l’implementazione a meno di non perdere di leggibilità e semplicità di gestione del codice (al contrario, una ricorsione lineare potrebbe essere sostituita con un’iterazione, portando ad una riduzione della complessità).

Si è scelto di non implementare in forma iterativa la funzione “node_traverse”: sebbene questa forma risulti più efficiente, si vuole dare esempio di visita ricorsiva in ordine simmetrico e posticipato (node_dealloc).

Testing del programma

Unitamente ai sorgenti che compongono il progetto, sono stati inclusi anche alcuni file contenenti dati di esempio; questi rappresentano istanze di input con dimensioni differenti, di modo che sia possibile un test più esaustivo dello strumento proposto.

Di seguito verrà incluso qualche test significativo ed il relativo output del programma; i seguenti test sono stati effettuati usando questi parametri da riga di comando:

• -i file: Legge i dati dal file specificato
• -o output.txt: Scrive la tabella ordinata nel file specificato
• -s criterio: Criterio di ordinamento

Test 1. lettura da un file inesistente

1
2
3

./rb-sorter -i not-exist.txt
[INFO] Creazione struttura dati
[INFO] Lettura dati dal file 'not-exist.txt' [ERR ] impossibile aprire il file 'not-exist.txt'

Test 2. database di 15 linee, duplicati presenti

1
2
3
4
5
6
7
8
9

$ time ./rb-sorter -i database_15_linee.txt -o output.txt -s c+m+v [INFO] Creazione struttura dati
[INFO] Lettura dati dal file 'database_15_linee.txt'
[INFO] Record letti : 15
[INFO] Nodi inseriti: 15
[INFO] Scrittura risultati
[INFO] Distruzione struttura dati
real  0m0.005s
user  0m0.001s
sys   0m0.003s

Test 3. database con 1,7 milioni di linee, duplicati non presenti

1
2
3
4
5
6
7
8
9

$ time ./rb-sorter -i database_1.7M_linee.txt -o output.txt -s c+m+v [INFO] Creazione struttura dati
[INFO] Lettura dati dal file 'database_1.7M_linee.txt'
[INFO] Record letti : 1699062
[INFO] Nodi inseriti: 1699062
[INFO] Scrittura risultati
[INFO] Distruzione struttura dati
real  0m10.839s
user  0m8.470s
sys   0m0.665s

Valutazione della complessità del programma

Per calcolare il tempo di esecuzione del programma nonché l’ordine di grandezza della complessità, si è scelto di adoperare due approcci distinti: in prima istanza, utilizzando un metodo analitico e, successivamente, uno sperimentale.

Approccio analitico

Sono stati identificati, all’interno del codice, tre macro blocchi di istruzioni: ad ognuno di questi è stato associato un costo, calcolando dapprima il numero effettivo di passi base eseguiti e derivando in seguito la classe dell’ordine di grandezza. Il primo blocco, la funzione loadfile, legge i dati dal file contenente il database; facendo coincidere il numero di righe del file con il numero di nodi che possibilmente verranno inseriti nell’albero, possiamo esprimere l’intero costo del programma in funzione del numero di record letti. Il costo del suddetto blocco sarà equivalente al prodotto di n record per il costo della funzione di inserimento di un nodo nell’albero, ovvero O(log n). Il secondo ed il terzo blocco del programma equivalgono alla visita dell’intero albero per stamparne i nodi ed alla deallocazione della struttura dati: entrambi hanno una complessità proporzionale al numero di nodi (record) presenti nell’albero, quindi pari ad O(n).

Di seguito, il riepilogo di quanto esposto:

La complessità totale quindi è pari a 2×n + n×log n, assimilabile alla classe di complessità pseudo lineare T(n) = O(n×log n).

Approccio sperimentale

L’approccio empirico proposto si basa sulla misurazione dei tempi di esecuzione del programma, fornendo istanze di input progressivamente maggiori.

Per ogni istanza di input, il programma è stato eseguito più volte: si è quindi valutato e riportato il valore medio.

Mettendo in relazione il numero di record processati ed il numero di secondi impiegati, si è notato come l’andamento della complessità temporale (espressa in secondi) seguisse la curva espressa dalla complessità calcolata con l’approccio analitico.

Di seguito i valori rilevati e loro rappresentazione grafica.

Scarica il progetto rb-sorter.tar.gz