Newsgroup: it.comp.lang.c++
Titolo: Migliorare libreria

Come posso migliorare quesa mia lib?
//////////////////////////////////
//Nome Libreria: Array Utils
//Autore: Kleidemos
//Vers: 0.11
//Data: 27/03/2003
//Scopo: Utilita' per gli array
/////////////////////////////////
///////////////////////////////////
//TODO:
//
// 1)ricerca binaria 0%
// 2)quick sort 0%
///////////////////////////////////
/////////////////////////////////////
//             Sviluppi            //
/////////////////////////////////////
/*
 Ordinamento
 Ordinamento di array
*/
template<class T>
void bubbleSort(T a[], int size)
 {
  for(int i=0;i<size;i++)
  {
   for(int j=0;j<size-1;j++)
   {
    if(a[j]>a[j+1])
    {
     T old = a[j];
     a[j] = a[j+1];
     a[j+1] = old;
    }
   }
  }
 }
/*
 Ricerca Lineare
 Ricerca lineare su array
*/
template<class T>
int serch(int size, T a[], T key)
{
 for(int i=0;i<size;i++)
 {
  if(a[i] == key)
   return i;
 }
 return -1;
}
--
Ciao da Kleidemos
C++ Programmer
Visual C++ 6

 Come posso migliorare quesa mia lib?
???
Il bubble sort puo' essere scritto in modo che abbia complessita' minore.
Non capisco a cosa serve la tua libreria... o meglio, capisco a cosa serve,
ma non capisco perche' tu la stia scrivendo.
Tommy

 ma non capisco perche' tu la stia scrivendo.
serve per i miei programmi e per impratichirmi con il C++ che ho appena
finito il Deitel&Deitel


 finito il Deitel&Deitel
Allora chiedo scusa, fai benissimo ad esercitarti cosi'!
Provo a dirti come migliorare il tuo bubblesort:
Questo e' il tuo bubblesort:
<CODE>
template<class T>
void bubbleSort(T a[], int size)
{
    for(int i=0;i<size;i++){
        for(int j=0;j<size-1;j++){
            if(a[j]>a[j+1]){
                 T old = a[j];
                 a[j] = a[j+1];
                 a[j+1] = old;
             }
        }
    }
}
</CODE>
Ok, quello che hai implementato e' il bubblesort!
E' tuttavia la forma piu' semplice del bubblesort, quella che controlla se
bisogna ordinare anche le parti che sono gia' ordinate!
Quello implementato da te e' sicuramente un algoritmo con tempo n*n. Se
l'array ha 100 elementi tu esegui l'if 9.900 volte (quasi 10.000) volte. Il
problema sta nel fatto che dato il modo in cui funziona il bubble sort il
tuo algoritmo svolge tanto lavoro NON necessario: dopo che esegui una volta
il for interno, l'elemento piu' grande si trova gia' in fondo all'array.
Pensaci. La seconda volta il secondo piu' grande si trova nella penultima
posizione dell'array. Man mano questi vengono a galla come bolle (credo
derivi da qui). Dopo 10 volte i dieci elementi piu' grandi sono gia' alla
fine dell'array.
Bene, se quello che ti dico e' vero, allora non serve che il for interno
arrivi sempre a size-1, ogni volta dovrebbe fare un elemento in meno:
int p;
for(int i=0;i<size;++i){
    ++p;
    for(int j=0;j<size-p;++j){
    }
}
in questo modo inizia con size-1 (come da te), poi size-2,
size-3,.....,size-10 etc...
Questo abbassa notevolmente il tempo di esecuzione.
Se prima il temp si esecuzione era 100*99 (n*2) ora possiamo approssimare
dicendo che e' 100*50 (all'inizio 100*99, alla fine 100*1, quindi 50 in
media) quindi (n*(n/2)), in pratica la meta' del tempo.
Inoltre cosa succede se la sequenza e' gia' ordinata, oppure e' parzialmente
ordinata e dopo pochi cicli gia' risulta ordinata???
Il tuo algoritmo (anche con la mia modifica) NON se ne accorge e alla fine
esegue sempre i 9.900 if (nel tuo caso) o 5000.
Ecco allora che conviene introdurre un valore booleano che testa se l'array
e' ordinato o meno. Se e' ordinato smette. (ovvio questa operazione non deve
costare in termini computazioni altrimenti....)
In questo modo se bastano 3 cicli esterni per ordinare l'array, la funzione
terminera' con 3*98 invece che 100*50.
Se l'array e' gia' ordinato con 1*99 invece che 100*50.
Un'ultima chicca, la meno importante:
T old = a[j];
a[j] = a[j+1];
a[j+1] = old;
quando puoi evita che la variabile old venga "creata" ogni volta che entri
nell'if (n*n nel tuo caso). Molti ottimizzatori risolveranno questo
problema, ma puoi farlo anche tu diachiarando T old all'inizio della
funzione e poi usando solo old.
Ad ogni modo questo e' il suggerimento meno importante.
Questo e' cio' che ho prodotto mantenendo il tuo prototipo di funzione ed il
tuo "stile":
<CODE>
template<class T>
void bubbleSort(T a[], int size)
{
    bool is_sorted=false;
    int p=0,q=0;
    T tmp;
    while(!is_sorted){
        is_sorted=true;
        ++p;
        for(q=0;q<size-p;++q){
            if(a[q]>a[q+1]){
                tmp=a[q];
                a[q]=a[q+1];
                a[q+1]=tmp;
                is_sorted=false;
            }
        }
    }
}
</CODE>
Data una sequenza completamente NON ordinata che tiene occupato il mio
algoritmo per 7 secondi, il tuo deve lavorare per ben 12 secondi, quasi il
doppio del tempo (vista la teoria ora vediamo la pratica).
Ora dando la stessa sequenza ma ordinata il tuo impiega ben 6 secondi (non
esegue swap, non scambia i valori, arriva solo all'if). Il mio invece e'
difficile da misurare, dovrei usare dei timer, non posso usare piu' il mio
orologio da polso, ad ogni modo siamo intorno a 1 decimo di secondo.
Come vedi con gli accorgimenti di cui parlo puoi avere tempi di esecuzione
molto piu' bassi e l'intelligenza di non ordinare cio' che e' gia' ordinato.
Nel caso di sequenze ordinate la differenza e' enorme.
Spero tutto questo possa esserti utile.
Tommy

Dirti che sei un "mito" sarebbe un pallido eufemismo!
