PDA

Visualizza la versione completa : [C++] Memorizzare una grande quantità di dati a runtime


freetom
21-12-2010, 10:35
Io dovrei memorizzare in run time molti dati.. (ritardi x ambo) ca 2 milioni quante sono le quartine generabili con 90 numeri. Ora ci sono riuscito mediante l'uso dei vector... di tipo <int> ma...
chiedo agli/alle esperti/e se c'e' un modo e se si quale per velocizzare notevolmente la cosa dato che con il modo da me trovato passa molto (troppo) tempo. :old:

Grazie per le vostre eventuali dritte in tal senso

:ciauz:

GliderKite
21-12-2010, 11:27
In effetti i vector sono piuttosto "lenti" cosi come tutti i contenitori della STL, questo perchè sono contenitori altamente generici e quindi poco efficienti per situazioni specifiche.

Ovviamente è possibile velocizzare il procedimento utilizzandoli nella maniera migliore possibile, quindi dovresti postare il codice, magari qualcuno può darti qualche dritta su come ottimizzare il codice.

Quando io ho avuto un problema simile ho risolto creandomi un ADT personalizzato sorprendendomi io stesso di come sia stato possibile ottenere qualcosa di molto vicino ai vector ma circa 9 volte più efficiente. L'unica cosa che ti posso consigliare e che se lo ritieni proprio necessario potresti provarci tu stesso.

freetom
21-12-2010, 11:33
Originariamente inviato da GliderKite
In effetti i vector sono piuttosto "lenti" cosi come tutti i contenitori della STL, questo perchè sono contenitori altamente generici e quindi poco efficienti per situazioni specifiche.

Ovviamente è possibile velocizzare il procedimento utilizzandoli nella maniera migliore possibile, quindi dovresti postare il codice, magari qualcuno può darti qualche dritta su come ottimizzare il codice.

Quando io ho avuto un problema simile ho risolto creandomi un ADT personalizzato sorprendendomi io stesso di come sia stato possibile ottenere qualcosa di molto vicino ai vector ma circa 9 volte più efficiente. L'unica cosa che ti posso consigliare e che se lo ritieni proprio necessario potresti provarci tu stesso.

Scusa la mia ignoranza ma cos'è un ADT personalizzato? :)

Per quanto riguarda il codice di "accumulo" dati è semplicemente il seguente:



vector <int> ritardi;
ritardi.push_back(ritardo);


Tuttavia... via via che il vector si riempie... il programma rallenta enormemente mettendoci troppo tempo anche per una sola quartina... (infatti ogni quartina (2 mln ca in tutto) deve essere confrontata con 4000 righe ca di cinque numeri ciascuna (estrazioni) )


stavo pensando che ad ogni confronto... potrei valutare sia il ritardo massimo che quello
ultimo... e modificare l'uno o l'altro a secondo i casi avendo sempre due dati nel vector ritardi e basta.. ma non saprei come procedere in tal senso... a messo sia un'idea valida e velocizzante... :popcorn:



:ciauz:

GliderKite
21-12-2010, 12:46
Essenzialmente cos'è un ADT lo puoi trovare spiegato qui: Abstract Data Type (http://en.wikipedia.org/wiki/Abstract_data_type)

Personalizzato nel senso che te lo crei tu come meglio credi per la tua specifica applicazione (sarebbe meglio ottimizzare il codice per arrivare ad un buon connubio tra efficienza e possibilità di utilizzare lo stesso codice per diversi tipi di dato, cosa che spesso e volentieri non coincide, ma se utilizzi il C++ e non il C la cosa diventa parecchio più semplice).


Vedi, il metodo push_back dei vector alloca memoria automaticamente prima di riaggiungere la dimensione massima del vettore, in modo da permetterti di aggiungere elementi in coda. Questa operazione di re-allocazione spreca molte risorse ed è principalmente quest'operazione che rallenta il tutto.

Io non so esattamente cosa intendi fare, ma se fossi in te e dovessi memorizzare in un vettore una successione di numeri, ciascuno dei quali è compreso tra 0 e 90, di dimensione massima 2 milioni. Il modo più veloce che mi viene in mente di applicare è una cosa del tipo: pre-allocazione e successivo inserimento dei dati.

Esempio:





const size_t size = 0x1E8480;

try
{
char *vect = new char [ size ];

// Se new non lancia un'eccezione bad_alloc gestisci
// il vettore come devi

delete [] vect;
}

catch( bad_alloc & )
{
// Gestisci l'eccezione come credi
}


PS: volendo puoi sostituire char con int (maggior efficienza, più spazio occupato), ma ricordati sempre dei limiti di allocazione.

freetom
21-12-2010, 15:02
Originariamente inviato da GliderKite
Essenzialmente cos'è un ADT lo puoi trovare spiegato qui: Abstract Data Type (http://en.wikipedia.org/wiki/Abstract_data_type)

Personalizzato nel senso che te lo crei tu come meglio credi per la tua specifica applicazione (sarebbe meglio ottimizzare il codice per arrivare ad un buon connubio tra efficienza e possibilità di utilizzare lo stesso codice per diversi tipi di dato, cosa che spesso e volentieri non coincide, ma se utilizzi il C++ e non il C la cosa diventa parecchio più semplice).


Vedi, il metodo push_back dei vector alloca memoria automaticamente prima di riaggiungere la dimensione massima del vettore, in modo da permetterti di aggiungere elementi in coda. Questa operazione di re-allocazione spreca molte risorse ed è principalmente quest'operazione che rallenta il tutto.

Io non so esattamente cosa intendi fare, ma se fossi in te e dovessi memorizzare in un vettore una successione di numeri, ciascuno dei quali è compreso tra 0 e 90, di dimensione massima 2 milioni. Il modo più veloce che mi viene in mente di applicare è una cosa del tipo: pre-allocazione e successivo inserimento dei dati.

Esempio:





const size_t size = 0x1E8480;

try
{
char *vect = new char [ size ];

// Se new non lancia un'eccezione bad_alloc gestisci
// il vettore come devi

delete [] vect;
}

catch( bad_alloc & )
{
// Gestisci l'eccezione come credi
}


PS: volendo puoi sostituire char con int (maggior efficienza, più spazio occupato), ma ricordati sempre dei limiti di allocazione.

In questi momenti mi rendo conto di essere ancora proprio agli inizi... :-| della programmazione in c++

Riferendomi al tuo intervento ad esempio ho capito solo... che con il metodo push_back() rallenta notevolmente il tutto rispetto ad altri modi come quello da te indicato ma che nn riesco a capire come funziona...

const size_t size = 0x1E8480 cosa significa? :confused: :fagiano:

In particolare volessi aggiungere al vettore vect il valore ritardo di volta in volta differente (da 0 a 200) come devo fare nel tuo caso? Infine perchè lo devo "svuotare"... con delete [] vect; ???

Grazie mille e scusa la mia illimitata ignoranza.. in questo campo! :zizi:

GliderKite
21-12-2010, 15:27
Il numero 0x1E8480 corrisponde al valore esadecimale (di esempio) di 2000000 (2 milioni). E' solo un altro modo per scriverlo :)


Semplicemente se hai il vettore di interi e vuoi aggiungere un valore intero nella posizione i-esima del vettore basta il semplice assegnamento:


int ritardo = 5;
vettore[ i ] = ritardo;


E' sempre buona norma rilasciare la memoria allocata non appena l'oggetto non ti serve più. Quindi quando il vettore non ti serve più devi deallocarlo. :ciauz:

freetom
22-12-2010, 09:07
Ma forse per adesso ho risolto associando al vector solo due posizioni [0] e [1] :)

:ciauz:

RooccoXXI
22-12-2010, 19:06
Perché non utilizare una lista?!?

Tempo di inserimento davanti o dietro:

O(1)

MItaly
22-12-2010, 19:20
Se sai in anticipo quanti dati ci andrai a mettere dentro ti basta usare vector.reserve prima di richiamare i vari push_back, oppure vector.resize e poi direttamente l'operatore [].

Originariamente inviato da GliderKite
Vedi, il metodo push_back dei vector alloca memoria automaticamente prima di riaggiungere la dimensione massima del vettore, in modo da permetterti di aggiungere elementi in coda. Questa operazione di re-allocazione spreca molte risorse ed è principalmente quest'operazione che rallenta il tutto.

È un'operazione che viene ammortizzata nel tempo, man mano che si va avanti con i push_back tra l'altro le dimensioni del blocco allocato aumentano (da quanto ho visto in genere si va raddoppiando). Prendiamo pure il caso estremo di un vector che parta con capacità 1; il numero delle riallocazioni va con il logaritmo delle dimensioni finali. In ogni caso, come detto, basta un reserve all'inizio e il problema non si pone più.

Originariamente inviato da RooccoXXI
Perché non utilizare una lista?!?

Tempo di inserimento davanti o dietro:

O(1)
Mi pare una pessima idea. Le liste vanno bene se si devono inserire elementi a metà, nel semplice accodamento hai solo svantaggi: costo delle allocazioni per i singoli elementi, spreco di memoria per i puntatori al precedente e successivo elemento; una lista di interi finirebbe con prendere più del triplo dello spazio di memoria rispetto ad un equivalente vettore (assumendo sizeof(void*)==sizeof(int)).

GliderKite
22-12-2010, 20:08
Originariamente inviato da MItaly
Se sai in anticipo quanti dati ci andrai a mettere dentro ti basta usare vector.reserve prima di richiamare i vari push_back, oppure vector.resize e poi direttamente l'operatore [].

È un'operazione che viene ammortizzata nel tempo, man mano che si va avanti con i push_back tra l'altro le dimensioni del blocco allocato aumentano (da quanto ho visto in genere si va raddoppiando). Prendiamo pure il caso estremo di un vector che parta con capacità 1; il numero delle riallocazioni va con il logaritmo delle dimensioni finali. In ogni caso, come detto, basta un reserve all'inizio e il problema non si pone più.

Mi pare una pessima idea. Le liste vanno bene se si devono inserire elementi a metà, nel semplice accodamento hai solo svantaggi: costo delle allocazioni per i singoli elementi, spreco di memoria per i puntatori al precedente e successivo elemento; una lista di interi finirebbe con prendere più del triplo dello spazio di memoria rispetto ad un equivalente vettore (assumendo sizeof(void*)==sizeof(int)).

In realtà non è proprio un raddoppio delle dimensioni, ma anche fosse ciò non toglie che più cerchi rapidità più ti dovresti allontanare dall'utilizzo di un vector. Senza considerare se se le dimensioni sono piuttosto considerevoli reallocare uno spazio simile richiede risorse davvero eccessive per qualsiasi operazione direi. Ovvio che se conosci a priori il numero di elementi ridimensionare il vettore all'inizio è una valida alternativa, ma anche in questo caso una resize è più dispendiosa di un'allocazione "standard" con new/malloc (inizializzando anche gli elementi del vettore a 0, operazione che se necessaria viene svolta molto più velocemente dalla memset).

In definitiva i vector vanno molto bene per compiti per i quali sono stati pensati, ossia per i casi più generali possibili quindi niente a che vedere con operazioni specifiche e volutamente performanti.

Stack, queue e strutture dati analoghe implementate attraverso l'utilizzo di liste concatenate richiedono una maggior analisi precedente per verificare se effettivamente possono avere vantaggi rispetto all'utilizzo di un vettore. Quindi dipende sempre da cosa si deve effettivamente fare, come sempre d'altronde. :ciauz:

Loading