Nei forum di informatica ci sono continuamente "guerre di religione" a favore o contro un determinato prodotto o tecnologia, ci sono spesso prese di posizione immotivate: la mia sensazione è che c'è tanta gente che effettua le proprie scelte con valutazioni "di pancia", ovvero senza alcun ragionamento, anzichè analizzando i pro e i contro di ciascuna possibile alternativa.
Questo "fondamentalismo informatico" può portare a fare scelte controproducenti, come nell'esempio che presento in questo articolo.
Si è abituati a considerare il Quick Sort un algoritmo veloce perchè ha una complessità O(n log2n) e quindi sia quanto di meglio si possa richiedere ad un algoritmo di ordinamento; algoritmi più semplici, come il Bubble Sort, hanno una complessità O(n2), ovvero al crescere del numero di elementi da ordinare il tempo impiegato crescerà in modo quadratico.
Banalmente si potrebbe dire che Quick Sort è più veloce di Bubble Sort ma... è sempre vero?
Problema
Analizziamo un problema apparso in un forum di programmazione in linguaggio C:
Dato in input un elenco di N parole, ordinare le lettere all'interno di ciascuna parola (es. "ciccio" -> "ccciio")
La scelta immediata sarebbe quella di utilizzare qsort() passandole una funzione di callback per il confronto fra i caratteri; questo perchè "quick sort è più veloce".
In realtà, in questo caso, l'algoritmo lavorerà sempre sulle singole parole, non bisogna farsi influenzare dal numero di parole N in input, quel che conta nella nostra valutazione è la lunghezza delle varie parole; nella lingua italiana la parola di lunghezza massima ("precipitevolissimevolmente") conta 26 caratteri e quindi possiamo considerare 26 come nostro "n" massimo.
Personalmente trovo che sviluppare un Bubble Sort, con due for, sia semplice almeno quanto utilizzare la funzione qsort(): penso inoltre che con un numero limitato di elementi da ordinare sia meglio non "scomodare" Quick Sort perchè potrebbe risultare condizionato dal "costo" delle chiamate a funzione.
Ma queste, appunto, sono valutazioni "di pancia"; bisogna provare!
Programma di prova
La dimostrazione che in questo caso particolare caso il Bubble Sort è più veloce è nel programmino C che segue; io l'ho compilato con Visual Studio 2015 ma credo che non ci sia alcun problema a ricompilarlo con altri compilatori e su altri sistemi (eventualmente va commentata la GetTickCount()).
Da notare che la costante TEST_CYCLES va "tarata" in dipendenza della velocità del proprio sistema.
#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//---------------------------------------------
// Quick Sort
//---------------------------------------------
typedef int (*compfn)(const void*, const void*);
int compare(char *pa, char *pb)
{
char a = *(char *)pa;
char b = *(char *)pb;
if ( a < b)
return -1;
else if (a > b)
return 1;
else
return 0;
}
void ordina_qsort(char *strin, char *strout)
{
int len = strlen(strin);
strcpy( strout, strin );
qsort((void *) strout,
len,
sizeof(char),
(compfn)compare );
}
//---------------------------------------------
// Bubble Sort
//---------------------------------------------
void ordina_bubble(char *strin, char *strout)
{
int len = strlen(strin);
int i, j;
char c;
strcpy( strout, strin );
for(i=0; i<len; i++)
{
for(j=i+1;j<len;j++)
{
if( strout[i] > strout[j] )
{
c = strout[j];
strout[j] = strout[i];
strout[i] = c;
}
}
}
}
//---------------------------------------------
// Test
//---------------------------------------------
#define TEST_CYCLES 1000000
void main(void)
{
char strout[80];
int i;
DWORD start, finish;
DWORD msec;
printf( "Ordinamento parole con qsort\n" );
start = GetTickCount();
for( i=0; i<TEST_CYCLES; i++ )
{
ordina_qsort( "precipitevolissimevolmente", strout );
}
finish = GetTickCount();
msec = finish - start;
printf( "tempo %d msec\n", msec );
printf( "strout %s\n", strout );
printf( "Ordinamento parole con bubble sort\n" );
start = GetTickCount();
for( i=0; i<TEST_CYCLES; i++ )
{
ordina_bubble( "precipitevolissimevolmente", strout );
}
finish = GetTickCount();
msec = finish - start;
printf( "tempo %d msec\n", msec );
printf( "strout %s\n", strout );
printf( "Premi un tasto\n" );
getch();
}
Risultati
Sul mio sistema, compilando in Release, ottengo:
Ordinamento parole con qsort
tempo 797 msec
Ordinamento parole con bubble sort
tempo 594 msec
Mentre se compilo in modalità Debug, ottengo
Ordinamento parole con qsort
tempo 5984 msec
Ordinamento parole con bubble sort
tempo 1516 msec
Molto probabilmente la versione Debug include dei controlli aggiuntivi nelle chiamate a funzione e quindi in questo caso l'algoritmo Quick Sort viene ulteriormente penalizzato; comunque, anche considerando solo l'esecuzione in Release si nota come il bubble sort risulti più veloce.
Provando a cambiare la parola o aggiungendone di altre (per questo basta aggiungere ulteriori chiamate alle funzioni ordina_qsort() e ordina_bubble() nei due cicli di test) si può notare come generalmente Bubble Sort è più veloce di Quick Sort.
Conclusioni
Quando leggo o sento affermazioni del tipo "Python è lento", "C è veloce", "Eclipse ha dei problemi"... mi innervosisco un pò: ogni strumento, tecnologia o linguaggio ha un motivo di esistere, è stato creato da persone che vogliono risolvere un problema o facilitare un compito e che vi hanno dedicato il proprio tempo: sta a noi utilizzare gli strumenti nel miglior modo possibile, valutando di volta in volta quello che ci conviene fare.
Così anche l'algoritmo Bubble Sort, per quanto sia "banale", non è da scartare a priori, solo perchè si è sentito dire o l'hanno insegnato a scuola che "Quick Sort è il più veloce"; in fondo, per una valutazione corretta, bastano solo dieci minuti!
