Newsgroup: it.comp.lang.c
Titolo: Compattamento di un vettore

Ho un vettore di reali, a dimensione
variabile, per esempio:
[0] [1.23] [5.67] [0] [0] [4]
Voglio compattarlo, togliere cioe'
gli elementi nulli.
Avevo pensato a qualcosa del genere:
(devo usare cpp), cioe' spostare
a sinistra il primo elemento non nullo,
(cioe' alla posizione originaria dell'elemento
non nullo meno il numero di elementi nulli
saltati...cioe' se ho 
1 0 0 5.62
il vettore compatt. sara'
1 5.62
quindi l'originario quarto elemento
viene spostato al secondo posto,
cioe' (posizione originaria - numeri di elementi saltati)
Ho provato a buttare giu' un po' di
codice non funge; inutile dire che sono
un principiante e che il risultato
e' invariato (il vettore non viene compattato):
/* Inizio codice funzione compatvet() */
int compatvet (vettore& vet, int& dim) {
float compatvet[dim];
int j, i, pos, nulli=0;
while (j<dim) {
 if (vet[j]==0) {
   j=j+1;  // salta all'elemento successivo
   nulli=+1;  // incremento il numero di elementi nulli
   pos=(j-nulli); // la posizione del prossimo elemento non nullo
   } else {
       vet[j]=vet[pos];  //l'elemento vet[j] viene spostato a vet[pos]
       }
   j=+1;
 }
return 0;
}
/* Fine codice funzione compatvet()  */
Grazie e ciao

 e' invariato (il vettore non viene compattato):
Hai sbagliato NG! Questo e' il NG di C, non di C++.
Ad ogni modo parli di vettori variabili, non so cosa tu intenda, io propongo
una versione con std::vector del C++, poi fanne tu quello che vuoi.
<CODE>
void RemoveAllZeros(vector<double> &v)
{
   int p=0,q=0;
   // copia sul vettore stesso gli
   // elementi tranne 0 nelle giuste pos.
   while(p<v.size()){
      if(v[p]!=0.0){
         v[q++]=v[p];
      }
      ++p;
   }
   // compatta:
   v.resize(q);
}
</CODE>
Fammi sapere se va bene o meno, ma se e' per C++ spostati di NG.
Ho risposto ugualmente, tanto, vector a parte, potrebbe essere codice C.
(scusate!)
Tommy

       }
se vuoi renderlo leggermente piu' efficiente puoi fare:
if( (v[p]!=0.0) && (p!=q) ){
....
questo migliora la situazione, ad esempio, in un file che non e' da
compattare (non ci sono zeri!).
Ma in genere, su un file con degli zeri non cambia praticamente nulla....
Ad ogni modo, per completezza...
Tommy

 ....
Chiedo scusa....
L'idea spero tu l'abbia capita, putroppo l'ho scritto senza pensare ed
espresso cosi' non e' ne utile ne corretto ;-)
Sorry!
Il problema di quel if e' ovvio credo...
La soluzione per ottenere l'effetto leggermente piu' efficiente e'
trasformare:
if(v[p]!=0.0){
   v[q++]=v[p];
}
in:
if(v[p]!=0.0){
    if(p!=q){
        v[q]=v[p];
    }
    ++q;
}
In questo modo eseguiamo v[q]=v[p]; solo se p e q sono diversi, altrimenti
non ne vale la pena ;-) (oltre che v[p] diverso da 0).
Il codice errato ( if( (v[p]!=0.0) && (p!=q) )) aveva il problema di non
incrementare la q nel caso in cui v[p]!=0 ma p==q, questo in alcuni casi
poteva portare ad alcuni problemi.
Riassumendo...
La prima versione postata e' corretta... Il tempo di esecuzione e' n
(lineare). Se un array non contine nessuno 0 l'operazione "v[q]=v[p];" viene
eseguita n volte. Il codice postato voleva risolvere questo motivo di
leggera inefficienza.... era putroppo buttato li senza ragionare e quindi
errato;-)
Il codice sostitutivo postato in questa mail invece per un array che non
contiene nessuno 0 non effettua "v[q]=v[p];" nemmeno una volta (sarebbe
inutile farlo).
A parte questa piccola chicca, puoi usare benissimo il primo codice postato
che per il resto e' assolutamente corretto ed equivalente.
Tommy

 }
Mi dispiace contraddirti, ma, a seconda del compilatore e di altri
fattori, questo secondo codice puo' benissimo essere leggermente
MENO veloce del primo. (almeno e' cosi' in una prova che ho fatto).
il fatto e' che risparmi degli assegnamenti, ma esegui ogni
volta un test (quindi istruzioni condizionali).
ciao,
g.

 volta un test (quindi istruzioni condizionali).
Concordo con te!
Non vale la pena di usare la seconda versione. E' piu' veloce solo quando ci
siano pochi zeri (o nessuno) e cmq non nella prima parte del vettore (ma
piuttosto verso la fine). La differenza anche in questo caso e' cosi' minima
che non giustifica!
I miei test sono stati effettuati compattando un vettore di un milione di
elementi per ben mille volte.
La differenza di prestazioni nel caso in cui non ci siano zeri e' del 5% a
favore della seconda versione.
La differenza di prestazioni nel caso in cui ci sia uno zero all'inizio del
vettore (caso opposto) e' del 6% a favore della prima versione.
Concludo dicendo che hai ragione, nonostante il mio pensiero fosse per certi
versi giusto, non e' stata un gran trovata, ho vatto un errore di
valutazione (pensavo si guadagnasse di piu' quando non ci sono zeri!)
Conviene buttare via la seconda versione e usare in qualsiasi caso la prima.
Ti ringrazio quindi per aver sollevato la questione.
A presto,
Tommy

favore della seconda versione.
   A occhiometro mi pare anche poco... Forse migliorerebbe mettendo (p
!= q) prima? (per via dei cortocircuiti logici, non eseguirebbe il
confronto tra v[p] e 0.0, che mi aspetterei piu` lento di un confronto
tra interi)
-- 
S.L.

 tra interi)
Capisco benissimo quello che dici... ha senso.
Tuttavia il tempo di esecuzione e' identico. Probabilmente l'optimiser
produce lo stesso codice.
Tommy

}
Ti ringrazio sei stato gentilissimo.
Solo che mi e' nuova l'istruzione
v[q++]=v[p]
Cioe' non ho mai visto incrementare
l'indice del vettore direttamente
nell'espressione del vettore stesso.
Grazie

 nell'espressione del vettore stesso.
Beh, puoi sempre incrementare q dopo in una seconda riga... non devi per
forza scriverlo in una riga sola!
v[q++]=v[p]
corrisponde a:
v[q]=v[p]
q=q+1;
usa tu la forma che preferisci. Se v[q++] ti suona nuovo, non lo usare.
Personalmente lo trovo piu' leggibile, capisco subito cosa stia succedendo,
ma questo dipende dai gusti e da quanto uno sia abituato a questo tipo di
espressioni o meno.
Tommy

usa tu la forma che preferisci.
Perfetto, ancora grazie.
Mi resta l'ultimo dubbio
 v.resize(q);
non volendo utilizzare il metodo
(si dice cosi'?) resize() c'e' qualche
istruzione "canonica".
Ciao

 istruzione "canonica".
Questa domanda dovrei farla io a te....
Tu parli di vettori a dimensione variabile. Io non so quali vettori tu stia
utilizzando!!!
Per semplicita' ho usato std::vector del C++ che e' un vettore che si puo'
ridimensionare.
In pratica se il nostro vettore contiene 20 numeri tra cui 5 zeri sparsi,
dobbiamo compattarlo, ovvero mettere i 15 numeri (non zero) vicini e poi
possibilmente ridurre la sua dimensione. Per fare questo vector ha un metodo
che sia chiama resize. Dopoi il resize il nostro vector conterra' solo 15
elementi e non piu' 20 (altrimenti non sapremo cosa farcene dei 5 finali!).
Non e' obbligatgorio ridurre la dimensione del vettore....
Volendo potresti anche lasciare la dimensione del vettore invariata e poi
ritornare un int che e' appunto la nuova lunghezza da tenere in
considerazione o ancora piu' semplicemente scorrere il vettore fino al primo
zero escluso (e quando compatti azzerare tutta la parte finale non usata o
anche solo il primo elemento non usato).
Dalla tua domanda avevo tuttavia capito che tu volesssi ridurre la
dimensione di un vettore, visto che parlavi di vettori a dimensioni
variabili e compattare.....
Se ti serve invece, come avevo capito io, ridurre la sua dimensione:
Ci sono tanti modi per cambiare la dimensione di un vettore e tanti tipi di
vettori... tu quale usi?!? Quale e' questo vettore a dimensione variabile?!?
Quali metodi o funzioni ha a disposizione!?
Visto che hai anche detto che usi il C++, se il vettore che usi e' una
classe C++ ti consiglio di rispondermi sul NG it.comp.lang.c++ o andiamo
ancora piu' OT.
Tommy