Newsgroup: it.comp.lang.c++
Titolo: Sort di interi, array non grosso, un consiglio.

Devo ordinare un array di interi o di puntatori, comunque un tipo dati
molto semplice.
La dimensione dell'array non dovrebbe essere grossa, diciamo che
potrebbe essere nell'ordine di una decina se va bene, se va proprio
male potrebbe arrivare a un centinaio, ma spero proprio di evitarlo.
Mi serve un algoritmo di sorting che sia il piu' veloce possibile, nel
caso medio piu' che nel valore di picco.
Tra l'altro inserito in un ciclo che devo ottimizzare diventa non
irrilevante la complessita' del codice.
Voglio dire: se devo scrivere 5000 righe di codice alla fine il tempo
di esecuzione non e' piu', mettiamo pure, n*log(n), ma va aggiunto un
overhead non trascurabile.
Googlando ho trovato il comb_sort, che sembrerebbe comportarsi bene
mediamente rispetto al banale bubble sort, non usa ricorsivita' quindi
niente allocazione di stack e appunto overhead che minaccia di
richiedere piu' tempo del sort stesso visti i pochi dati in gioco.
Quel che pero' mi lascia perplesso sono i numeri float che utilizza,
per carita' ci fa solo una divisione ma..
Domanda: che tipo di algoritmo mi conviene adottare in questo genere
di situazione? Va bene sto comb sort?
Ve lo riporto, se a qualcuno interessa
	int depthIndex[255] = {7,3,2,1,6,4,5,9,8,0}; // numeri messi a caso
	SpaceCollection::maxDepth = 10;
	// 
http://en.wikipedia.org/wiki/Comb_sort
	float gap = (float) SpaceCollection::maxDepth; //initialize gap size
    unsigned int swaps = 0; //see bubblesort for an explanation
	while ((gap > 1) || (swaps != 0))
	{
        //update the gap value for a next comb
        if (gap > 1)
		{
            gap /= 1.3f;
            if ((gap == 10) || (gap == 9))
				gap = 11;
		}
        unsigned int i = 0;
        swaps = 0; //see bubblesort for an explanation
		//a single "comb" over the input list
	    while (i+gap < (float) SpaceCollection::maxDepth)
		{
			unsigned int j = i+(unsigned int) gap;
			if (depthIndex[i] > depthIndex[j])
			{
			    int temp = depthIndex[i];
				depthIndex[i] =  depthIndex[j];
				depthIndex[j] =  temp;
				swaps = 1;
			}
            i++;
		}

 molto semplice.
Sei sicuro che la funzione std::sort non faccia al caso tuo? Se si,
perche'?
Ciao,
Nicola

Nicola Musatti ha spiegato il 23/01/2008 :

perche' non sapevo esistesse :)
sono approdato al c++ da poco.
Guardero', grazie.
-- 
Diario di un videogioco che non vedrà mai la luce
http://pidigi.blogspot.com/


Poi ci ho riflettuto.
La mia perplessità è: una funzione di sort generica, per quanto
ottimizzata, riesce ad essere piu' veloce di una scritta ad hoc nel
caso si debbano ordinare pochi elementi?
Cioe' son senz'altro convinto che su dimensioni ragguardevoli il sort
della libreria standard sia estremamente efficente, ma quel che mi
chiedo e': ordinando 10 numeri non si rischia che l'overhead rispetto
alle semplici operazioni di confronto e scambio la rendano di fatto
piu' lenta?
Chiedo, perche' non so onestamente.

 caso si debbano ordinare pochi elementi?
Credo che lo std::sort utilizzi l'algoritmo quicksort. E se ricordo bene 
  il quicksort decide quale algoritmo effettivamente utilizzare a 
seconda del numero di elementi dell'array. Il problema, semmai, ci 
sarebbe se tu avessi molti elementi che non sono disposti del tutto a 
caso. Solo in situazioni del genere un algoritmo generico potrebbe non 
essere il migliore.
E.


Controdomanda: sei convinto di saper ottimizzare il caso particolare
di quanto persone del calibro di Bill Plauger o Matt Austern non
abbiano saputo ottimizzare il caso generale?
L'unica risposta sensata e': misura le prestazioni di std::sort sulla
tua macchina col tuo compilatore e, se risulta necessario, prova a far
di meglio.
Ciao,
Nicola
P.S. Un altro consiglio: sbircia dentro <algorithm> per vedere cosa fa
effettivamente il tuo compilatore.

 di meglio.
Chiaro, anche se non e' banale misurare delle prestazioni all'interno di un
motore 3d, mi chiedevo semplicemente se qualcuno ci avesse gia' riflettuto.
-- 
Diario di un videogioco che non vedr? mai la luce
http://pidigi.blogspot.com/

 male potrebbe arrivare a un centinaio, ma spero proprio di evitarlo.
per l'ordine di grandezza del tuo problema solitamente la complessità 
asintotica non è cosi ponderante. potrebbe benissimo esser piu veloce un 
qualsiasi algoritmo quadratico ma molto semplice piuttosti che un 
algoritmo loglineare ma piu complesso. fai due prove, quicksort contro 
selectionsort e vedi quale dei due è piu veloce.
visto che stai scrivendo un engine 3d con un mucchio di ottimizzazioni, 
il consiglio che ti posso dare è quello di procurarti un profiler e di 
fare tante prove finche non trovi la soluzione piu veloce. ovviamente 
partendo con cognizione di causa :)


Il quicksort di per se' non decide che tipo di algoritmo usare, il
quicksort E' un algoritmo.
E non si tratta comunque solo di disposizione di elementi (nel mio
caso tra l'altro partirei da un array abbastanza ordinato, non
caotico), ma anche da numero di elementi da ordinare.
Se prendiamo n=10, tanto per dirne una, l'ordinamento piu' stupido di
sempre (quello ingenuo) richiede n(n-1)/2 cicli, ovvero 45 cicli.
Il quicksort, nel suo caso migliore n*log(n) ovvero 34 cicli.
Ora; il tempo di esecuzione dell'ordinamento ingenuo diventa = 45*H,
quello del Quicksort 34*K, dove H e K rappresentano la durata di un
ciclo, e sono dati dalla somma del tempo di confronto+ tempo di
scambio + tempo di overhead (allocazione variabili, incremento indici,
utilizzo dello stack eccetera).
34K<40H e' vero quindi quando K< 1.18H, ovvero se K/H>1.18 l'algoritmo
stupido diventa piu' veloce del quicksort.
A sto punto e' chiaro che il valore di K e H, per piccoli n diventa
rilevante. Se n invece e' grosso, diciamo 1000
9965K < 449500H, il valore di K e H diventa tutto sommato ininfluente
visto che bisogna che K/H sia maggiore di 45 affinche' il quicksort
diventi piu' lento.
Ma 1.18 e' poco, basta un 10% di overhead per rendere il quick non
piu' quick, e mi immagino (ma sottolineo immagino) che un algoritmo di
libreria, che presumo sia studiato per gestire disparati tipi di dati,
abbia una struttura piu' complessa di un paio di for nidificati.
Tra l'altro immagino dipenda da molte cose, prima di tutto
dall'implementazione di std::sort nell'ambiente c++ particolare, dal
compilatore, dalla cpu..
Insomma non e' una questione semplice, da qui il mio thread.

 partendo con cognizione di causa :)
Il mio consiglio e` di limitare le ottimizzazioni a quelle banali 
(quicksort piuttosto che bubblesort, ricerca dicotomica piuttosto che 
lineare su container ordinati...) e di usare il profiler per vedere 
quali sono i colli di bottiglia ed eventualmente ottimizzare quelli 
piuttosto che rischiare di seminare qua e la' bug dovuti ad improbabili 
ottimizzazioni a priori :)
Bye,
  Gabry

 caotico), ma anche da numero di elementi da ordinare.
Sě, ma l'algoritmo puň comportarsi diversamente a seconda del numero di 
elementi da ordinare. Invece non puň sapere a priori se i dati sono in 
ordine casuale o no.
E.