[Risolto] [C++] Scelta contenitore e metodo di stampa
Inviato: giovedì 9 febbraio 2012, 18:08
Salve.
Ho un problema esistenziale relativo alla scelta del contenitore.
Cerco di spiegare semplificando molto il problema, di modo che non ammazzo nessuno con un messaggio
(cosa che penso rientri nel campo dei reati informatici )
Allora, devo scegliere un contenitore... e fin qui ci siamo.
La scelta penso che si possa restringere tra una lista o un vettore della libreria standard del C++, in quanto non vorrei dover reinventare la ruota, ma preferirei usare qualcosa che preveda già tutti gli usuali metodi, senza che li implementi io ex novo.
Mi servirebbe capire quale è la migliore "idea" per un contenitore che preveda un numero elevato di rimozioni e un numero esiguo di inserimenti.
Ogni elemento del contenitore, a sua volta, è un vector di due coordinate intere.
(quindi il contenitore per cui ho aperto la discussione lo chiamo contenitore "superiore")
Io faccio delle operazioni su tali coordinate e quando si verifica una determinata condizione (che le coordinate siano entrambe nulle) devo rimuovere l'elemento dal contenitore "superiore" (quello che contiene tutti questi vector a due coordinate).
Il contenitore "superiore" può avere da pochi elementi (poche decine) fino a svariate centinaia di migliaia (e forse anche più).
Quale è il miglior contenitore "superiore", in termini di performance per questo tipo di rimozione?
La rimozione, sto pensando, la farei mentre faccio le operazioni sul vector a due coordinate (ovvero mentre scorro con un iteratore il contenitore "superiore").
Ossia, faccio l'operazione, controllo e se le coordinate sono entrambe nulle rimuovo tale elemento.
Tale rimozione, ovviamente, la farei stando attento a non far impazzire l'iteratore sul contenitore "superiore".
Ovvero (se per esempio il contenitore "superiore" fosse una lista):
Test selle coordinate del vettore (di interi) a due dimensioni:
Evoluzione e rimozione tutto in uno:
Le mie "preoccupazioni" sono relative a quale sia il contenitore migliore per fare un numero elevato di rimozioni e se ci sia un "numero massimo" di rimozioni che possono essere effettuate.
Inoltre, dovrei stampare e operare in maniera "massiccia" su questo contenitore, quindi vorrei qualcosa che non implichi un pesante riallocamento... nel senso che (non saprei come spiegarmi in termini tecnici) non debba sempre stare a controllare dove sta messo nella ram.
A margine, vorrei sapere se per un numero moooolto elevato di elementi in un contenitore (che sia una lista o un vettore) sia sensato, per velocizzare i tempi di stampa, passare alla funzione di stampa un iteratore all'inizio del contenitore e un iteratore all'elemento successivo all'ultimo (ossia usare i metodi begin ed end della classe container) per evitare di ricopiare tutto il contenuto del contenitore passato.
Io a questa "chicca" non ci avevo pensato. L'ho letta su C++ primer (4° edizione) ma mi sto chiedendo se sia davvero una cosa sensata.
Grazie in anticipo
Ciao
Ho un problema esistenziale relativo alla scelta del contenitore.
Cerco di spiegare semplificando molto il problema, di modo che non ammazzo nessuno con un messaggio
(cosa che penso rientri nel campo dei reati informatici )
Allora, devo scegliere un contenitore... e fin qui ci siamo.
La scelta penso che si possa restringere tra una lista o un vettore della libreria standard del C++, in quanto non vorrei dover reinventare la ruota, ma preferirei usare qualcosa che preveda già tutti gli usuali metodi, senza che li implementi io ex novo.
Mi servirebbe capire quale è la migliore "idea" per un contenitore che preveda un numero elevato di rimozioni e un numero esiguo di inserimenti.
Ogni elemento del contenitore, a sua volta, è un vector di due coordinate intere.
(quindi il contenitore per cui ho aperto la discussione lo chiamo contenitore "superiore")
Io faccio delle operazioni su tali coordinate e quando si verifica una determinata condizione (che le coordinate siano entrambe nulle) devo rimuovere l'elemento dal contenitore "superiore" (quello che contiene tutti questi vector a due coordinate).
Il contenitore "superiore" può avere da pochi elementi (poche decine) fino a svariate centinaia di migliaia (e forse anche più).
Quale è il miglior contenitore "superiore", in termini di performance per questo tipo di rimozione?
La rimozione, sto pensando, la farei mentre faccio le operazioni sul vector a due coordinate (ovvero mentre scorro con un iteratore il contenitore "superiore").
Ossia, faccio l'operazione, controllo e se le coordinate sono entrambe nulle rimuovo tale elemento.
Tale rimozione, ovviamente, la farei stando attento a non far impazzire l'iteratore sul contenitore "superiore".
Ovvero (se per esempio il contenitore "superiore" fosse una lista):
Test selle coordinate del vettore (di interi) a due dimensioni:
Codice: Seleziona tutto
//test sulle coordinate
int originCheck(vector<signed long> x) {
if (x[0]==0 && x[1] == 0) {
return 1;
} else
return 0;
}
Codice: Seleziona tutto
void makeSmartMove(signed long m, list< vector<signed long> > &state, unsigned long &partCounter) {
list< vector<signed long> >::iterator it1;
list< vector<signed long> >::iterator it2;
int mossa;
for(it1=state.begin(); it1!=state.end(); /* l'incremento avviene dentro al corpo del ciclo */) {
mossa = lrand48() % 4;
//Faccio le operazioni su *(it1)[0] e *(it1)[1]
//che dipendono dal valore di mossa
//e che aggiornano la variabile partCounter
if(originCheck(*it1)) {
it2 = it1;
it1++;
state.erase(it2);
partCounter++;
} else {
it1++;
}
}
}
Inoltre, dovrei stampare e operare in maniera "massiccia" su questo contenitore, quindi vorrei qualcosa che non implichi un pesante riallocamento... nel senso che (non saprei come spiegarmi in termini tecnici) non debba sempre stare a controllare dove sta messo nella ram.
A margine, vorrei sapere se per un numero moooolto elevato di elementi in un contenitore (che sia una lista o un vettore) sia sensato, per velocizzare i tempi di stampa, passare alla funzione di stampa un iteratore all'inizio del contenitore e un iteratore all'elemento successivo all'ultimo (ossia usare i metodi begin ed end della classe container) per evitare di ricopiare tutto il contenuto del contenitore passato.
Io a questa "chicca" non ci avevo pensato. L'ho letta su C++ primer (4° edizione) ma mi sto chiedendo se sia davvero una cosa sensata.
Grazie in anticipo
Ciao