[Risolto] [C++] Scelta contenitore e metodo di stampa

Linguaggi di programmazione: php, perl, python, C, bash, ecc.

[Risolto] [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » 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 ;D )

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;
}


Evoluzione e rimozione tutto in uno:
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++;
      }
   }
}


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 :)
Ultima modifica di l3on4rdo il giovedì 9 febbraio 2012, 18:17, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda Ikitt » giovedì 9 febbraio 2012, 20:07

l3on4rdo ha scritto:Mi servirebbe capire quale è la migliore "idea" per un contenitore che preveda un numero elevato di rimozioni e un numero esiguo di inserimenti.

Inserimenti  in testa, in coda o nel mezzo? L'uso di memoria puo` essere un problema?

Ogni elemento del contenitore, a sua volta, è un vector di due coordinate intere.

Se conterra` sempre e solo due coordinate io userei una std::pair o una struct.

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.

Non credo possa esistere tale limite.
Ikitt Non specificato
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1815
Iscrizione: ottobre 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » venerdì 10 febbraio 2012, 3:44

Ciao Ikitt, grazie per l'interessamento.

Andando in ordine:

1) In coda va benissimo, ma non c'è assolutamente una preferenza. Posso inserirli anche nel mezzo, se è più semplice.
Il vector rappresenta le coordinate di una pedina su una scacchiera, quindi gli inserimenti posso farli dove mi garba di più.
Che intendi con uso di memoria?
Le simulazioni girano su di un cluster di computer al dipartimento di fisica.
Se mi dici cosa devo controllare, chiedo all'amministratore del sistema.
Tra l'altro, le operazioni sulle varie coppie di coordinate sono indipendenti l'una dall'altra e sto anche pensando a come parallelizzare... ovvero a spezzare il container "superiore" in pezzetti e far gestire l'evoluzione di ogni pezzo separatamente.
Sono davvero ignorante in termini di programmazione parallela, ma devo dire che mi piacerebbe riuscirci :)

2) Mi aggiorno su pair, appena posso.
Coma mai suggerisci pair? quali sono i vantaggi?

ps:
e per la stampa, che mi dici? :)
Ultima modifica di l3on4rdo il venerdì 10 febbraio 2012, 4:10, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda Ikitt » venerdì 10 febbraio 2012, 20:24

l3on4rdo ha scritto:1) In coda va benissimo, ma non c'è assolutamente una preferenza. Posso inserirli anche nel mezzo, se è più semplice.
Il vector rappresenta le coordinate di una pedina su una scacchiera, quindi gli inserimenti posso farli dove mi garba di più.

Allora la soluzione che userei io e` un array (o vector) con inserimenti in coda fissi. Semplice e (per quel che ne sa ;)) efficiente.

Che intendi con uso di memoria?

La cosa piu` economica in assoluto e` marcare un elemento come libero invece che rimuoverlo effettivamente. Questo ovviamente ha un costo in termini di memoria, perche` non la si rilascia.
Ma e` semplice e veloce. (E molte preoccupazioni sono spesso infondate ;))
Tra l'altro, le operazioni sulle varie coppie di coordinate sono indipendenti l'una dall'altra e sto anche pensando a come parallelizzare... ovvero a spezzare il container "superiore" in pezzetti e far gestire l'evoluzione di ogni pezzo separatamente.

Con un array o vector e` piuttosto banale :)

Sono davvero ignorante in termini di programmazione parallela, ma devo dire che mi piacerebbe riuscirci :)

Da quel pochissimo che hai scritto sembrarebbe un problema adatto a map+reduce.

2) Mi aggiorno su pair, appena posso.
Coma mai suggerisci pair? quali sono i vantaggi?

Perche` e` C++, e il C++ e` ossessivamente orientato al controllo e al "non pagare quello che non usi". Se te hai sempre e solo due coordinate, avere un (sub)contenitore dinamico e/o generico e` uno spreco e sopratutto una complicazione evitabile.

ps:
e per la stampa, che mi dici?

Che non ho capito il problema :)
Ikitt Non specificato
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1815
Iscrizione: ottobre 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » sabato 11 febbraio 2012, 15:39

Allora la soluzione che userei io e` un array (o vector) con inserimenti in coda fissi. Semplice e (per quel che ne sa ) efficiente.

La mia perplessità nell'uso dei vector è che la rimozione di un elemento dovrebbe essere più lenta della rimozione di un elemento di una lista.
Io propendo per la lista per via delle frequenti rimozioni di elementi posizionati nell'interno del container... ma non sono affatto sicuro della scelta.
Non sarebbe meglio una lista di pair?
Tu che dici?


La cosa piu` economica in assoluto e` marcare un elemento come libero invece che rimuoverlo effettivamente. Questo ovviamente ha un costo in termini di memoria, perche` non la si rilascia.
Ma e` semplice e veloce. (E molte preoccupazioni sono spesso infondate )

Per la memoria non ho assolutamente problemi. Sono simulazioni che devono girare su dei cluster del dipartimento di fisica.
Quindi, almeno di questo aspetto, possiamo fregarcene.

In termini di distinzione tra coppie di coordinate non nulle e coppie di coordinate entrambe nulle, concordo con te, quando dici che basta un marcatore.
Il fatto è che quelle coppie di coordinate rappresentano la posizione di una pedina su una scacchiera.
La situazione è un po' "complessa" e provo a descriverla brevemente.
Se le coordinate non sono entrambe nulle, le pedine seguono una certa dinamica (random) per spostarsi (random walk sulla scacchiera).
Se invece capitano nell'origine (e quindi hanno coordinate entrambe nulle) restano ferme lì, in una sorta di trappola.
"Ogni tanto", se ci sono delle pedine bloccate in questa trappola, la trappola può sputarne una (sempre facendo tiri random contro una certa probabilità stabilita a priori quando si lancia la simulazione).

La probabilità che la particella prima o poi cada è data dalla teoria dei random walk... e praticamente è una "certezza".
La probabilità che la trappola possa riemettere se popolata la decido io... e di norma è moooolto esigua.

Praticamente io avevo pensato di usare un contenitore tipo lista/vector in cui tenere queste coordinate delle pedine, che all'inizio vengono posizionate in modo equiprobabile sulle caselle della scacchiera (esclusa ovviamente la trappola nell'origine).
Le pedine (che non hanno coordinate entrambe nulle) si muovono tutte "insieme", ad ogni iterazione della simulazione.
Pertanto io, ad ogni "turno", faccio un'iterazione sul contenitore e, a seconda di un "tiro random", aggiorno di volta in volta le coordinate della pedina.
Quando la pedina casca nella trappola la rimuovo dal contenitore lista/vector e aumento, di una unità, un contatore di particelle nella trappola.
Ad ogni turno, poi, dopo aver finito di muovere tutte le pedine, se il contatore (che ancora registra il numero di particelle intrappolate al turno precedente) è diverso da zero (il che significa che la trappola è popolata) faccio un ulteriore tiro random e, nel caso in cui la trappola emette, reinserisco in coda alla lista/vector la coppia di coordinate della pedina "sputata".

Ora, io mi chiedo... è più semplice rimuovere un elemento dal contenitore e aumentare (di uno) un contatore, quando la pedina cade nella trappola, e fare l'opposto (diminuire (di uno) un contatore e aggiungere le coordinate in coda) quando la trappola emette?
Oppure ci sono modi più "rapidi e sereni" di fare questa cosa?
Se metto un marcatore, come mi suggerisci (ovviamente senza che ti avessi spiegato tutta la manfrina, che è fondamentale :) ):
1) Ogni volta devo controllare il marcatore per capire se la pedina è fuori dalla trappola, per capire se la devo muovere secondo le logiche di un random walk su una griglia bidimensionale.
Molti controlli quindi saranno praticamente inutili e per questo avevo pensato di tenere dentro al contenitore "superiore" solo le coordinate non nulle... ovvero le pedine che si muovono.
2) Usando un marcatore, non so quante particelle sono nella trappola, cosa che invece a me purtroppo serve di monitorare.
Oppure devo usare una sorta di secondo marcatore.
3) Se la trappola emette... devo andare a cercare all'interno del contenitore la prima pedina con coordinate (0,0) e spostarla.

Insomma... ora che ho dato un po' di informazioni... come ti regoleresti?


Da quel pochissimo che hai scritto sembrarebbe un problema adatto a map+reduce.

Per il discorso sulla parallelizzazione... sono ancora una schiappa e sto al terzo capitolo del libro Patterns for parallel programming.
Inizio ad intuire che qui il problema si potrebbe risolvere dividendo il contenitore tra i vari processori e facendo gestire (ad ognuno di essi) l'evoluzione di un sottinsieme di pedine (di modo che ho più contenitori con meno pedine... addirittura penso si possa dividere la faccenda a seconda del numero di processori e di processi gestibili... ma sto ancora studiando le basi della programmazione parallela).
Ma siccome io sono ancora in alto mare... lasciamo stare la parallelizzazione ;)


Perche` e` C++, e il C++ e` ossessivamente orientato al controllo e al "non pagare quello che non usi". Se te hai sempre e solo due coordinate, avere un (sub)contenitore dinamico e/o generico e` uno spreco e sopratutto una complicazione evitabile.

In effetti io a std::pair non ci avevo proprio pensato e devo dire che è la soluzione migliore, per gestire la coppia di coordinate.
Inoltre posso confrontare direttamente che pair sia o meno uguale a un pair di int nulli... usando:
The header also overloads the relational operators ==, <, !=, >, >= and <= , so as to be able to compare pair objects of the same type directly



ps:
Io, nell'usare un contenitore per le pedine con coordinate non nulle e un contatore per le pedine cadute in trappola, ho pensato di spostare e rimuovere le eventuali pedine che cadono in trappola durante la stessa iterazione che si occupa dell'aggiornamento delle coordinate.
Ovvero mentre itero, aggiorno le coordinate; poi controllo le nuove coordinate: se sono (0,0) la rimuovo, altrimenti passo alla successiva.
Questo è solamente "pensato" per evitare di fare una prima iterazione di aggiornamento e una seconda iterazione di rimozione.
(calcolando che le pedine possono essere anche centinaia di migliaia per un totale di alcuni milioni di iterazioni di aggiornamento delle coordinate...)

pps:
per spiegare bene la parte relativa alla stampa, a breve posto un estratto del libro in cui ho letto la "dritta" :)
Ultima modifica di l3on4rdo il sabato 11 febbraio 2012, 16:09, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda Ikitt » domenica 12 febbraio 2012, 10:43

l3on4rdo ha scritto:
Allora la soluzione che userei io e` un array (o vector) con inserimenti in coda fissi. Semplice e (per quel che ne sa ) efficiente.

La mia perplessità nell'uso dei vector è che la rimozione di un elemento dovrebbe essere più lenta della rimozione di un elemento di una lista.

Non ricordo le specifiche di vector. Se ben ricordo non dovrebbe fare compattamento della memoria libera (rialloca, cioe`, solo aumentando dimensioni e non diminuendo).
Da li il mio suggerimento. Comunque implementare un simil-vector con le caratteristiche che ti servono non e` particolarmente difficile, eventualmente.
(https://bitbucket.org/france/cxkit/src/ ... arraykit.h)

[...]Se le coordinate non sono entrambe nulle, le pedine seguono una certa dinamica (random) per spostarsi (random walk sulla scacchiera).
Se invece capitano nell'origine (e quindi hanno coordinate entrambe nulle) restano ferme lì, in una sorta di trappola.
"Ogni tanto", se ci sono delle pedine bloccate in questa trappola, la trappola può sputarne una (sempre facendo tiri random contro una certa probabilità stabilita a priori quando si lancia la simulazione).
[...]
Praticamente io avevo pensato di usare un contenitore tipo lista/vector in cui tenere queste coordinate delle pedine, che all'inizio vengono posizionate in modo equiprobabile sulle caselle della scacchiera (esclusa ovviamente la trappola nell'origine).
Le pedine (che non hanno coordinate entrambe nulle) si muovono tutte "insieme", ad ogni iterazione della simulazione.
Pertanto io, ad ogni "turno", faccio un'iterazione sul contenitore e, a seconda di un "tiro random", aggiorno di volta in volta le coordinate della pedina.
Quando la pedina casca nella trappola la rimuovo dal contenitore lista/vector e aumento, di una unità, un contatore di particelle nella trappola.
Ad ogni turno, poi, dopo aver finito di muovere tutte le pedine, se il contatore (che ancora registra il numero di particelle intrappolate al turno precedente) è diverso da zero (il che significa che la trappola è popolata) faccio un ulteriore tiro random e, nel caso in cui la trappola emette, reinserisco in coda alla lista/vector la coppia di coordinate della pedina "sputata".

Le due scelte piu` ovvie sono appunto mantenere un contenitore di pedine in trappola o trovare un bit libero di informazioni nella rappresentazione della pedina per poter distinguere le pedine libere da quelle intrappolate. Per esempio, se la griglia ha una dimensione intera e minore di 2^31 potresti usare qualcuno dei bit piu` significativi delle coordinate.

Oppure ci sono modi più "rapidi e sereni" di fare questa cosa?

Piu` rapidi e sereni, su due piedi, mi viene veramente difficile trovarne :)

2) Usando un marcatore, non so quante particelle sono nella trappola, cosa che invece a me purtroppo serve di monitorare.
Oppure devo usare una sorta di secondo marcatore.

Non basta tenere un contatore separato di pedine in trappola?

3) Se la trappola emette... devo andare a cercare all'interno del contenitore la prima pedina con coordinate (0,0) e spostarla.

Anche qui potrebbe bastare un indice alla prima (o ultima) pedina in trappola.

Insomma... ora che ho dato un po' di informazioni... come ti regoleresti?

Come sempre, la soluzione piu` semplice che puo` funzionare dati i requisiti e test (in sviluppo e sul campo) per vedere se e quanto bene ci si ha preso :)

Vector (o simil-vector) di pedine, ogni pedina come struct (o class), marcatura di in trappola/libera, contatore di pedine in trappola, indicizzazione del primo (o ultimo) elemento da liberare. L'unico elemento che mi potrebbe sdubbiare e` come tener traccia degli altri elementi da liberare.
Ikitt Non specificato
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1815
Iscrizione: ottobre 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » mercoledì 15 febbraio 2012, 19:35

Ora che abbiamo scambiato i preliminari, veniamo al dunque :)
Ho aperto questa discussione per via di un problema che si verifica in maniera del tutto casuale e senza un motivo che io riesca a ricondurre a qualche errore nel codice di una simulazione che sto facendo.
In questo messaggio descrivo, inzialmente, il tipo di problema riscontrato.
Poi descrivo a grandi linee cosa fa la simulazione.
Infine posto il codice della simulazione
... o meglio faccio una domanda e in base alla risposta, in un prossimo messaggio posto il codice.


Presentazione del problema
Il problema (che illustro ora ma che ovviamente sarà chiarito nel corso del messaggio) consiste nel fatto che ad un certo punto la stampa dell'output della simulazione si blocca e comincia a stampare ciclicamente le ultime righe di output.
La stampa procede in maniera "normale", mettiamo, fino alla TOT-esima riga di output... poi decide di prendere le ultime N righe e stampare solo quelle ciclicamente fino alla fine (con una piccola differenza tra ogni ciclo di "ri"stampa, che a breve chiarisco).
È importante notare che:
  • Sia TOT, sia N variano in maniera tale che io non riesco a dargli un senso, né a ricondurlo a qualche errore nel codice.
  • Tale anomalia si presenta solo per un determinato valore di un parametro da cui dipende la simulazione, come spiegato nel dettaglio più avanti.

Le righe che vengono stampate nel file di output sono di questo tipo:
Codice: Seleziona tutto
{1: 0.946203, 2: 1.02234, 3: 1.00639, 4: 0.983212, 5: 1.00071, 6: 0.972706, 7: 0.994123, 8: 0.990442, 9: 0.998881, 10: 1.01909, 11: 1.00857, 'tempo': 0, 'trapped': 0}
{1: 0.931899, 2: 0.997133, 3: 1.00047, 4: 0.990522, 5: 0.988729, 6: 0.985936, 7: 0.984237, 8: 0.981894, 9: 1.00522, 10: 1.01475, 11: 1.01218, 'tempo': 200, 'trapped': 98}
{1: 0.832278, 2: 0.949309, 3: 1.00562, 4: 1.01238, 5: 0.995105, 6: 0.973542, 7: 0.985381, 8: 0.983326, 9: 0.999169, 10: 1.01155, 11: 1.01116, 'tempo': 400, 'trapped': 182}
{1: 0.714225, 2: 0.923777, 3: 0.981992, 4: 1.01542, 5: 1.00918, 6: 0.975327, 7: 0.988659, 8: 0.983942, 9: 1.00026, 10: 1.01125, 11: 1.00595, 'tempo': 600, 'trapped': 246}
{1: 0.690427, 2: 0.911372, 3: 0.987685, 4: 1.00982, 5: 0.992876, 6: 0.967907, 7: 0.984038, 8: 0.999183, 9: 1.00855, 10: 1.00444, 11: 1.00328, 'tempo': 800, 'trapped': 311}

Sono pensate come dei dizionari (python) per poi essere date in pasto a degli script di analisi dati che mi sono scritto (in python).
Le chiavi numeriche rappresentano delle etichette per indicare delle zone di una superficie (la superficie è la griglia su cui si muovono le pedine, di cui ho parlato nei messaggi iniziali della discussione), cui sono associati dei valori che rappresentano le densità medie di tali zone.
Le chiavi non numeriche sono il 'tempo' (che indica l'iterazione cui è arrivato l'algoritmo della simulazione) e un insieme di valori di cui devo monitorare l'evoluzione temporale nel corso della simulazione. Tale insieme, in questo caso, è dato dalla sola quantità 'trapped'.

Proprio nella simulazione di cui questo è un estratto della parte iniziale dell'output, avviene l'inceppamento di cui sopra.
Ad un certo punto, la simulazione impazzisce e si ha, fino alla fine del file, la stampa ciclica delle 4 righe:
Codice: Seleziona tutto
{1: 0.252025, 2: 0.332553, 3: 0.374517, 4: 0.371656, 5: 0.398688, 6: 0.401279, 7: 0.393009, 8: 0.409103, 9: 0.42026, 10: 0.419669, 11: 0.421743, 'tempo': 131200, 'trapped': 24017}
{1: 0.252041, 2: 0.332569, 3: 0.374092, 4: 0.371788, 5: 0.398798, 6: 0.401442, 7: 0.393052, 8: 0.408843, 9: 0.420419, 10: 0.419567, 11: 0.421775, 'tempo': 131400, 'trapped': 24017}
{1: 0.251915, 2: 0.332649, 3: 0.374089, 4: 0.371622, 5: 0.398989, 6: 0.401369, 7: 0.393097, 8: 0.408882, 9: 0.420356, 10: 0.419601, 11: 0.421754, 'tempo': 131600, 'trapped': 24017}
{1: 0.25193, 2: 0.332814, 3: 0.374345, 4: 0.371436, 5: 0.398959, 6: 0.401275, 7: 0.393013, 8: 0.409191, 9: 0.420057, 10: 0.419788, 11: 0.421714, 'tempo': 131800, 'trapped': 24017}

Come dicevo prima, le righe non vengono riprodotte in maniera "identica"... perché pare che il tempo continui a scorrere, ovvero:
Codice: Seleziona tutto
{1: 0.252025, 2: 0.332553, 3: 0.374517, 4: 0.371656, 5: 0.398688, 6: 0.401279, 7: 0.393009, 8: 0.409103, 9: 0.42026, 10: 0.419669, 11: 0.421743, 'tempo': 132000, 'trapped': 24017}
{1: 0.252041, 2: 0.332569, 3: 0.374092, 4: 0.371788, 5: 0.398798, 6: 0.401442, 7: 0.393052, 8: 0.408843, 9: 0.420419, 10: 0.419567, 11: 0.421775, 'tempo': 132200, 'trapped': 24017}
{1: 0.251915, 2: 0.332649, 3: 0.374089, 4: 0.371622, 5: 0.398989, 6: 0.401369, 7: 0.393097, 8: 0.408882, 9: 0.420356, 10: 0.419601, 11: 0.421754, 'tempo': 132400, 'trapped': 24017}
{1: 0.25193, 2: 0.332814, 3: 0.374345, 4: 0.371436, 5: 0.398959, 6: 0.401275, 7: 0.393013, 8: 0.409191, 9: 0.420057, 10: 0.419788, 11: 0.421714, 'tempo': 132600, 'trapped': 24017}
{1: 0.252025, 2: 0.332553, 3: 0.374517, 4: 0.371656, 5: 0.398688, 6: 0.401279, 7: 0.393009, 8: 0.409103, 9: 0.42026, 10: 0.419669, 11: 0.421743, 'tempo': 132800, 'trapped': 24017}
{1: 0.252041, 2: 0.332569, 3: 0.374092, 4: 0.371788, 5: 0.398798, 6: 0.401442, 7: 0.393052, 8: 0.408843, 9: 0.420419, 10: 0.419567, 11: 0.421775, 'tempo': 133000, 'trapped': 24017}
{1: 0.251915, 2: 0.332649, 3: 0.374089, 4: 0.371622, 5: 0.398989, 6: 0.401369, 7: 0.393097, 8: 0.408882, 9: 0.420356, 10: 0.419601, 11: 0.421754, 'tempo': 133200, 'trapped': 24017}
{1: 0.25193, 2: 0.332814, 3: 0.374345, 4: 0.371436, 5: 0.398959, 6: 0.401275, 7: 0.393013, 8: 0.409191, 9: 0.420057, 10: 0.419788, 11: 0.421714, 'tempo': 133400, 'trapped': 24017}
{1: 0.252025, 2: 0.332553, 3: 0.374517, 4: 0.371656, 5: 0.398688, 6: 0.401279, 7: 0.393009, 8: 0.409103, 9: 0.42026, 10: 0.419669, 11: 0.421743, 'tempo': 133600, 'trapped': 24017}
{1: 0.252041, 2: 0.332569, 3: 0.374092, 4: 0.371788, 5: 0.398798, 6: 0.401442, 7: 0.393052, 8: 0.408843, 9: 0.420419, 10: 0.419567, 11: 0.421775, 'tempo': 133800, 'trapped': 24017}
{1: 0.251915, 2: 0.332649, 3: 0.374089, 4: 0.371622, 5: 0.398989, 6: 0.401369, 7: 0.393097, 8: 0.408882, 9: 0.420356, 10: 0.419601, 11: 0.421754, 'tempo': 134000, 'trapped': 24017}
{1: 0.25193, 2: 0.332814, 3: 0.374345, 4: 0.371436, 5: 0.398959, 6: 0.401275, 7: 0.393013, 8: 0.409191, 9: 0.420057, 10: 0.419788, 11: 0.421714, 'tempo': 134200, 'trapped': 24017}

... e così via fino alla fine (del file e della mia salute mentale).

In questo esempio, quindi, N (il numero di righe ripetute) è quattro, mentre TOT (il numero dell'ultima riga stampata "correttamente") è 656:
Codice: Seleziona tutto
{1: 0.261709, 2: 0.330952, 3: 0.364284, 4: 0.379183, 5: 0.394826, 6: 0.405324, 7: 0.394472, 8: 0.410913, 9: 0.416415, 10: 0.423693, 11: 0.420384, 'tempo': 131000, 'trapped': 24017}



In cosa consiste la simulazione
La simulazione la cui stampa presenta questo problema è la seguente.
Si immagini una griglia quadrata (tipo una scacchiera) il cui lato è arbitrariamente scelto come parametro iniziale.
Si immagini di scegliere un numero (arbitrario) di pedine e che tali pedine (dal programma) vengano disposte sulla scacchiera, distribuite in modo equiprobabile tra tutte le caselle (ovviamente su una stessa casella possono capitare più di una pedina), ad eccezione di una casella particolare posta nel centro della griglia.
(dal momento che si immagina che nel centro della scacchiera ci sia una casella "particolare", per questioni di simmetria, la griglia può avere solo lati con un numero dispari di caselle)
Una volta disposte, le particelle (ad ogni turno) si muovono secondo un random walk bidimensionale indipendente, sulla griglia, con condizioni periodiche al contorno (se escono da un lato, rientrano da quello opposto).
I random walk sono indipendenti, nel senso che le pedine non interagiscono in nessun modo tra di loro, non vedendosi, e possono anche stare in "gruppo" sulla stessa casella.
La casella nel centro ha la "particolarità" data dal fatto di essere "appiccicosa".
Se una particella ci capita sopra, vi rimarrà intrappolata.
Se la trappola è popolata, può emettere (una particella per turno, fino a che eventualmente si svuota) con una probabilità (normalizzata ad uno) passata alla simulazione come parametro.

Lo scopo è analizzare l'evoluzione temporale delle densità medie (mediate spazialmente e temporalmente su un "ciclo di stampa") in sezioni della scacchiera.
Le sezioni possono essere corone circolari o cornici rettangolari concentriche.
Praticamente si decide una durata della simulazione ed un intervallo di stampa.
Per tutta la durata, si fa evolvere il sistema, come spiegato, e si stampano le densità mediate nel tempo (l'intervallo di stampa) e nello spazio (il numero di siti nella corona circolare o rettangolare).
Si stampano inoltre, altri valori mediati, associati alle chiavi non numeriche di cui sopra.


Codici della simulazione
La simulazione è composta dai moduli:
  • parseLib.cpp
    un parser per la riga di comando, brutto e minimale, ma che fa quello che mi serve.
  • libSys.ccp
    per gestire il controllo sull'esistenza e la creazione delle directory in cui poi vengono creati i file di output
  • libEvolSmart.cpp
    si occupa dell'inizializzazione del sistema, delle routine di aggiornamento delle posizioni delle particelle, della gestione della trappola
  • libDens.cpp
    si occupa delle routine per calcolare la densità nelle varie corone circolari o rettangolari
  • libPrint.cpp
    si occupa della stampa su file
  • randwalmain.cpp
    il main

Prima di postare il codice (o di caricarlo in qualche sito di hosting e postare i link), avrei un dubbio.
Sto facendo alcune modifiche alla gestione dei dati, o meglio sto cambiando alcuni contenitori.
Per esempio, su tuo suggerimento, non uso più dei vector bidimensionali, per le coordinate delle pedine, ma le memorizzo in una std::pair.
Di conseguenza stanno cambiando un po' di funzioni.
Gli algoritmi sono esattamente gli stessi, cambiano solo i contenitori.

Che faccio?
Posto il codice attuale?
O quello con i contenitori modificati?
Ad occhio e croce, visto che il problema della stampa si verifica da "parecchie versioni" della simulazione (e nel tempo ho cambiato vari contenitori), si verificherà anche se uso pair al posto di vector e se faccio piccole modifiche nel codice :)
È una domanda da "idiot", me ne rendo conto.
Ho però il timore di trovare/risolvere il problema per l'attuale codice con cui faccio le simulazioni... ma, visto che sto apportando tali modifiche, trovarmi poi con una soluzione per un codice che non uso più, perché modificato per esempio con pair al posto di vector.

Ciao e grazie infinite per la disponibilità, Ikitt!!!
Ultima modifica di l3on4rdo il mercoledì 15 febbraio 2012, 20:08, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda Ikitt » sabato 18 febbraio 2012, 9:53

l3on4rdo ha scritto:[...]
Che faccio?
Posto il codice attuale?
O quello con i contenitori modificati?
Ad occhio e croce, visto che il problema della stampa si verifica da "parecchie versioni" della simulazione (e nel tempo ho cambiato vari contenitori), si verificherà anche se uso pair al posto di vector e se faccio piccole modifiche nel codice :)
È una domanda da "idiot", me ne rendo conto.
Ho però il timore di trovare/risolvere il problema per l'attuale codice con cui faccio le simulazioni... ma, visto che sto apportando tali modifiche, trovarmi poi con una soluzione per un codice che non uso più, perché modificato per esempio con pair al posto di vector.

Ciao e grazie infinite per la disponibilità, Ikitt!!!

A giudicare dal post la cosa piu` probabile sembra essere che (sottolineo "sembra essere" e in particolare "sembra") sia un problema di accumulo di errori di arrotondamento di double che alla fine ti fa sballare una condizione o un pezzo di evoluzione. Ripeto che e` solo una intuizione al volo, potrebbe essere orribilmente errata.

Per pubblicare il codice, va bene l'ultima versione compilabile che riproduce il problema.
Se pubblichi il codice su internet, ricordati di scrivere chiaramente la licenza e la nota di copyright. Userei al tuo posto un sito apposito tipo bitbucket, github, google code: roba tipo (il fu) megaupload sarebbero da evitare.

Chiaramente e` meglio se indichi dei parametri che causano e permettano di riprodurre il problema :)
Cosi` su due piedi non posso dirti altro... Se non che, purtroppo, anche se dai tutte queste altre informazioni non e` detto che si riesca ad isolare il problema.
Ikitt Non specificato
Entusiasta Emergente
Entusiasta Emergente
 
Messaggi: 1815
Iscrizione: ottobre 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » domenica 19 febbraio 2012, 3:32

Sto testando il codice modificato.
Dovrebbe funzionare.
Poi vedo se riproduce l'errore, visto che, oltre ad un parametro particolare, questo si verifica a seconda del seme di inizializzazione di srand... seme che stampo in un file di report per cercare di capire se, rifacendo la simulazione con quel seme, viene riprodotto l'errore.

Appena sono sicuro che tutto funzioni, posto i link ai codici.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda bite » domenica 19 febbraio 2012, 14:47

Sei sicuro che sia un errore? Puoi escludere che si tratti di attrattori?

Prova a stampare più decimali; se sono cicli limite c'è da aspettarsi che le ripetizioni non siano identiche.
Avatar utente
bite Non specificato
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 3798
Iscrizione: maggio 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » domenica 19 febbraio 2012, 15:50

Se pubblichi il codice su internet, ricordati di scrivere chiaramente la licenza e la nota di copyright. Userei al tuo posto un sito apposito tipo bitbucket, github, google code

Una cosa non mi è chiara.
Come si gestisce questa faccenda della licenza a nota di copyright?
Devo metterla come premessa al main? In ogni file?
Non saprei proprio come regolarmi.

@ bite
È molto improbabile che siano cicli limite o qualcosa di simile.
Provo a stampare più decimali (se intendi aumentare la precisione di stampa con cout).
... hai visto mai che mi danno una medaglia Fields ;D
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda bite » domenica 19 febbraio 2012, 16:15

l3on4rdo ha scritto:... per cercare di capire se, rifacendo la simulazione con quel seme, viene riprodotto l'errore.


Se così non fosse ci sarebbe da preoccuparsi... memoria non inizializzata o altri casini
Avatar utente
bite Non specificato
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 3798
Iscrizione: maggio 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » lunedì 20 febbraio 2012, 21:16

Allora, ho completato la modifica del codice e appena capisco come si inseriscono le licenze metto il tutto in rete.
Dove posso leggere e capire come si inseriscono le licenze?  :-[

Per quanto riguarda la compilabilità, è compilabile a meno di un warning (penso banale, poi mi direte :) )
Per quanto riguarda la riproducibilità dell'errore, "fortunatamente" li riproduce... anzi stampa dei file di output identici.
La verifica sulla stampa, ovviamente, l'avevo già fatta, ma non per le simulazioni con problemi.
Nel senso che avevo visto già che rifacendo la stessa simulazione (anche con lo stesso seme, ovviamente) ottenevo lo stesso identico file di output.
Ora ho constato che anche in caso di "scappellamento" si riproduce la stessa identica cosa.

Quindi in pratica, oltre ai dati iniziali con cui lancio le simulazioni, riesco ad individuare anche i semi che danno problemi.
Ovviamente, insieme al codice, vi metto anche alcuni dati per riprodurre simulazioni (non troppo "onerose") che diano questi problemi.

ps:
bite ha scritto:
l3on4rdo ha scritto:... per cercare di capire se, rifacendo la simulazione con quel seme, viene riprodotto l'errore.


Se così non fosse ci sarebbe da preoccuparsi... memoria non inizializzata o altri casini

Per quanto sono assurdi questi errori* non mi sarei meravigliato se non fossero ricapitati in una seconda simulazione che lancio con gli stessi dati iniziali che hanno causato l'errore in una simulazione precedente.
(ovvero stessi dati più il seme che mi faccio stampare in un file apposito per controllarlo)

*)
Io ci avevo pensato, all'ipotesi di un ciclo limite o una distribuzione asintotica che si verifica in determinate circostanze... ma quando ventilai l'ipotesi alla relatrice la risposta fu una risatina beffarda :)
Sto però spulciando tutti i file in cui c'è un numero di cifre significative "elevato", per vedere di capire meglio questa cosa.
... anche se non ci spero molto
Ultima modifica di l3on4rdo il lunedì 20 febbraio 2012, 21:50, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda bite » martedì 21 febbraio 2012, 17:06

l3on4rdo ha scritto:
bite ha scritto:
l3on4rdo ha scritto:... per cercare di capire se, rifacendo la simulazione con quel seme, viene riprodotto l'errore.


Se così non fosse ci sarebbe da preoccuparsi... memoria non inizializzata o altri casini

Per quanto sono assurdi questi errori* non mi sarei meravigliato se non fossero ricapitati in una seconda simulazione che lancio con gli stessi dati iniziali che hanno causato l'errore in una simulazione precedente.
(ovvero stessi dati più il seme che mi faccio stampare in un file apposito per controllarlo)


Hai chiarito questo punto? Se gli stessi dati iniziali e lo stesso seme possono dare risultati diversi, si sa già in che direzione cominciare a cercare (memoria, probabilmente allocata dinamicamente, non inizializzata).
Avatar utente
bite Non specificato
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 3798
Iscrizione: maggio 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » martedì 21 febbraio 2012, 17:12

Al momento, ogni simulazione lanciata con gli stessi dati iniziali (intesi come parametri che passo io e come seme di inizializzazione dei generatori di numeri casuali) dà gli stessi identici output, sia che la simulazione fili liscia, sia che produca l'inceppamento nella stampa.
Come vedrete, il codice è davvero elementare. :)

Ho chiarito, al bar, la questione relativa a come mettere la licenza e a quale scegliere.
Sto facendo gli ultimi controlli.

Entro domani dovrei riuscire a postare i codici dei programmi con tutte le indicazioni per capire cosa faccia il programma e come si riproducano le simulazioni difettose.
Posto il programma in due varianti, anche se in sostanza cambia solo una minima parte di codice.
In questo modo dovrebbe essere più facile individuare il problema, perché si presenta (con semi differenti) in entrambi i casi.
Poi vi spiego nel dettaglio ;)

Grazie di cuore (e anche di fegato!)
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda bite » mercoledì 22 febbraio 2012, 1:16

l3on4rdo ha scritto:Io ci avevo pensato, all'ipotesi di un ciclo limite o una distribuzione asintotica che si verifica in determinate circostanze... ma quando ventilai l'ipotesi alla relatrice la risposta fu una risatina beffarda :)


Falle vedere il gioco della vita di Conway  (yes)
Avatar utente
bite Non specificato
Imperturbabile Insigne
Imperturbabile Insigne
 
Messaggi: 3798
Iscrizione: maggio 2007

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » mercoledì 22 febbraio 2012, 3:32

bite ha scritto:
l3on4rdo ha scritto:Io ci avevo pensato, all'ipotesi di un ciclo limite o una distribuzione asintotica che si verifica in determinate circostanze... ma quando ventilai l'ipotesi alla relatrice la risposta fu una risatina beffarda :)


Falle vedere il gioco della vita di Conway  (yes)

Beh, ma lì è differente.
Nel senso che comunque ci sono delle regole e alcune figure funzionano come "figure di equilibrio" e cose del genere.
Da me la dinamica è parecchio differente.
Sono radom walk indipendenti. Le pedine, in pratica, neanche si vedono.
Quindi dubito che, anche se ancora ci spero, l'anomalia possa dipendere da qualcosa di "sensato"  :(

Comunque, ho quasi finito di sistemare e, domani, al massimo in serata, cerco di postare il tutto.
Anche se devo ammettere che sono un pochino intimorito dalla figuraccia che farò con questo codice indecente :)
Da una parte mi fa davvero piacere se gli date un'occhiata e (magari) trovate pure l'errore.
Dall'altra... vorrei essere più bravo e postare qualcosa di più "serio" :)

Appena concludo, posto i link per scaricare il codice... con tutte le istruzioni che penso possano chiarirvi le idee
(viene da sé, che sarò a disposizione per ogni chiarimento)

Ciao
Ultima modifica di l3on4rdo il mercoledì 22 febbraio 2012, 3:34, modificato 1 volta in totale.
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda paper0k » mercoledì 22 febbraio 2012, 8:57

l3on4rdo ha scritto: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")


Creare/aggiungere/rimuovere/cancellare oggetti comporta CPU ed uso intenso della memoria (è c'è sempre la variabile swap). Dipende dai casi ovviamente, ma hai fini prestazioni generalmente si preferisce usare vettori a dimensione fissa ed eventualmente "marcare" gli elementi ad indicare se sono disponibili o meno (quelli non disponibili possono essere usati per accogliere i nuovi dati).
Inoltre, un consiglio, oltre ai contenitori standard usa anche gli algoritmi standard, nel tuo caso il remove_if, sono molto utili anche se (purtroppo) spesso ignorati dai "programmatori" C++ ;)

l3on4rdo ha scritto: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.


Se ho capito bene di cosa stiamo parlando... si, non hai la necessità di sapere qual'è l'ultimo elemento per ogni iterazione nel loop, è un dato certo, predefinito
Esempio:

Codice: Seleziona tutto
std::vector<int>::iterator I = lista.begin();
std::vector<int>::iterator Iend = lista.end();
for (; I!=Iend; ++I) { ... }


è meglio di

Codice: Seleziona tutto
for (std::vector<int>::iterator I = lista.begin(); I!=lista.end(); I++) { ... }


La fine del vettore è nota, non cambia all'interno del ciclo. Inoltre notare come si dovrebbe incrementare l'iteratore tra il primo ed il secondo caso.
Quando scrivi "I++" in compilatore dovrebbe trasformare la cosa in:

Codice: Seleziona tutto
T tmp(I);
I=I+1;
return tmp;


mentre con "++I"

Codice: Seleziona tutto
I=I+1;
return I;


è facile capire che così risparmi qualche ciclo di CPU (certamente non è sempre applicabile) ;)

Un ulteriore consiglio... in linea di massima, la regola è semplice, in un algoritmo (in qualsiasi linguaggio/applicazione) devi compiere "solo" quelle azioni che non puoi fare prima. Qualsiasi cosa che puoi eseguire/costruire prima, è da fare prima ;)
Ultima modifica di paper0k il mercoledì 22 febbraio 2012, 8:59, modificato 1 volta in totale.
Chiunque può essere ragionevole, ma esser sani di mente è raro (Oscar Wilde)
Wiki|Blog|Twitter|Identi.ca|last.fm
Avatar utente
paper0k Maschile
Rampante Reduce
Rampante Reduce
 
Messaggi: 7216
Iscrizione: ottobre 2006

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » mercoledì 22 febbraio 2012, 16:15

Ciao Paper0k, grazie per l'intervento.

Creare/aggiungere/rimuovere/cancellare oggetti comporta CPU ed uso intenso della memoria (è c'è sempre la variabile swap). Dipende dai casi ovviamente, ma hai fini prestazioni generalmente si preferisce usare vettori a dimensione fissa ed eventualmente "marcare" gli elementi ad indicare se sono disponibili o meno (quelli non disponibili possono essere usati per accogliere i nuovi dati).

Cerco di spiegare il processo logico che mi ha guidato verso le scelte nel mio programma.
Io parto con una quantità anche molto elevata di elementi.
Di questi elementi, molti andranno "estratti" dal contenitore (nel senso di "ignorati in seguito").
L'ipotesi di un marcatore, che avevo preso in considerazione, l'ho dovuta scartare semplicemente perché avrebbe comportato, per ogni iterazione della simulazione, (fino ad) alcune decine di migliaia di controlli "inutili"... e il tutto si ripete per un numero di iterazioni dell'ordine di alcune centinaia di miglia (fino ad un massimo di qualche milione...)
Quindi ho optato per l'effettiva rimozione delle pedine che devo ignorare in seguito.
Una volta "deciso" che era meglio rimuovere gli elementi, ho optato per una lista in quanto qui, ho letto:
Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

... ovvero, per l'estrazione di elementi "interni", list funziona meglio di un vector.

Inoltre, un consiglio, oltre ai contenitori standard usa anche gli algoritmi standard, nel tuo caso il remove_if, sono molto utili anche se (purtroppo) spesso ignorati dai "programmatori" C++

Il fatto che molti ignorano... lo condivido :)
Io per primo c'ho messo un po' prima di scoprire e fare amicizia con std::algorithm.
Anzi, a dire il vero ne ho ignorato a lungo la stessa esistenza.
Il discorso su remove_if, invece, l'avevo inizialmente preso in considerazione (mi pare su suggerimento di Zoff in un'altra discussione).
Il fatto è che, o decido di fare una prima iterazione sulla lista per muovere tutte le pedine e poi faccio una successiva iterazione di rimozione con remove_if, oppure decido di fare una singola iterazione sulla lista, come poi ho deciso di fare.
Durante la singola iterazione sulla lista, prima muovo la pedina e successivamente controllo se va rimossa.
(la rimuovo con il metodo list::erase, che permette la rimozione in sicurezza di un elemento di un contenitore su cui si sta iterando, durante la stessa iterazione).
In questo modo, mi è sembrato che la simulazione andasse più spedita. E in effetti impiega meno tempo.


La faccenda sul preincremento e sul postincremento la conoscevo (ne parla proprio C++ Primer, per esempio)
Stavo però facendo un discorso differente, che avevo buttato lì come domanda "a margine" e che riprenderei in un secondo momento perché attualmente è un problema davvero secondario (e inoltre temo di averlo espresso anche malamente ;) )


Un ulteriore consiglio... in linea di massima, la regola è semplice, in un algoritmo (in qualsiasi linguaggio/applicazione) devi compiere "solo" quelle azioni che non puoi fare prima. Qualsiasi cosa che puoi eseguire/costruire prima, è da fare prima

Qui invece hai preso in pieno tutto il mio cruccio relativo al "muovere le pedine e rimuovere quelle in una determinata posizione", il tutto in una sola iterazione.
Da un punto di vista di modularità (spero di aver preso il termine giusto), è più sensato muovere le particelle in una prima iterazione e rimuovere dal contenitore (o marcarle) in un seconda iterazione.
Dal punto di vista delle performance, invece, è più efficace fare una singola iterazione che gestisca entrambe le cose.

Purtroppo sono un semplice fisico matematico e non ho studi in programmazione alle spalle, a parte un ridicolo corso di C.
Inoltre mi intrippo parecchio con questioni di performance e mi faccio svariate pippe che spesso si rivelano inutili.
:)
l3on4rdo
 

Re: [C++] Scelta contenitore e metodo di stampa

Messaggioda l3on4rdo » mercoledì 22 febbraio 2012, 18:31

Allora, ho finito e posso postare il codice.

Pur avendo letto il consiglio di Ikitt:
Se pubblichi il codice su internet, ricordati di scrivere chiaramente la licenza e la nota di copyright. Userei al tuo posto un sito apposito tipo bitbucket, github, google code: roba tipo (il fu) megaupload sarebbero da evitare.

ho strutturato la cosa pensando che avrei caricato la cartella zippata contenente tutti i file del programma, non tenendo in considerazione che in quei siti si posta direttamente il codice (se ho capito bene  :-[ )

Pertanto mi scuso e il codice lo allego a questo messaggio.
È una directory (da 52 kB) zippata (e ridotta a poco meno di 22 kB)

Contiene la gnu gnp v2 nel file COPYING e le varie condizioni di copia all'inizio di ogni modulo che compone il programma.

Per la compilazione, non sono ancora in grado di fornire un file make, ma i comandi sono:
Codice: Seleziona tutto
g++ -Wall -pedantic -c *.cpp

per ottenere i file .o
E un successivo:
Codice: Seleziona tutto
g++ -o MetastableRandWalk *.o


Io ho compilato il programma su Ubuntu 10.04 64 bit (kernel 2.6.32-38-generic) e con il compilatore:
Codice: Seleziona tutto
l3on4rdo@l3on4rdo-laptop:~$ g++ --version
g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


Ho ottenuto solo un warning, nella compilazione del modulo libDens.cpp:
Codice: Seleziona tutto
libDens.cpp: In function ‘int externalSitesCheck(long int, long int, long unsigned int)’:
libDens.cpp:124: warning: comparison between signed and unsigned integer expressions

e credo (ma smentitemi pure ;) ) che non sia un problema, almeno per la casistica in cui ricadono le simulazioni.

Venendo alle simulazioni, una volta compilato, il programma si lancia in questo modo:
Codice: Seleziona tutto
./MetastableRandWalk -set SET -file FILE -part PART -bound BOUND -step STEP -visc VISC -length LENGTH -print PRINT

Ad eccezione di VISC (che è un numero compreso tra 0 e 1), gli altri valori per i parametri sono tutti interi (senza segno) e stanno a significare:
Codice: Seleziona tutto
SET -> numero di set
FILE -> numero di file
PART -> numero di particelle coinvolte
BOUND -> semilato della scacchiera (che quindi sarà (2*BOUND + 1)^2 )
STEP -> passo con cui viene sezionata la scacchiera in corone circolari e rettangolari (le zone di cui studio le variazioni di densità)
VISC -> la viscosità della trappola (e quindi, se la trappola è popolata, la probabilità di emissione di una particella ad ogni turno è "1 - VISC")
LENGTH -> il numero di iterazioni della simulazione
PRINT -> il numero di iterazioni tra una stampa e la successiva


Questo modo di lanciare il programma prevede che le particelle siano messe (con una scelta equiprobabile tra tutte le caselle) anche nella trappola.
Inoltre il seme di inizializzazione delle funzioni di generazione dei numeri casuali, in questo modo di lanciare il programma, è inizializzato con il "classico" time.

Si possono però aggiungere i parametri:
Codice: Seleziona tutto
-trap [TRAP]
-seed [SEED]

Il passaggio del parametro -trap (senza valore associato), prevede che la trappola non sia considerata, nel posizionare le pedine.
Quindi si avranno PART particelle distribuite nella scacchiera... ad esclusione dell'origine.
Se però si passa anche il valore TRAP, questo sarà il numero (a parte) di pedine che andranno a popolare la trappola nel momento dell'inizializzazione del sistema.
Quindi si avranno PART particelle nella scacchiera e TRAP particelle nella trappola.
Il passaggio del parametro -seed, comporta che il seme sia SEED.
Questo l'ho aggiunto solo per poter riprodurre le simulazioni problematiche.
Nel senso che una simulazione ha i dati iniziali che io passo e generalmente (per quello che serve a me) si "crea" un seme con time.
Per riprodurre le simulazioni problematiche (ovviamente) devo ripassare quei dati iniziali, e quel seme particolare "che mi ha causato lo scappellamento della stampa".

Sia che si decida di popolare la trappola a parte, con TRAP, sia che si decida di decidere il seme a priori, la simulazione genera, nella directory che contiene l'eseguibile, una directory di nome(senza le virgolette):
Codice: Seleziona tutto
./set"SET"-"BOUND"-"STEP"-"VISC"-"PART"-"LENGTH"-"PRINT"

All'interno di questa, sarà creata una ulteriore directory di nome:
Codice: Seleziona tutto
simulazione"FILE"

con i file di output di nome:
Codice: Seleziona tutto
crown_dens.txt
frame_dens.txt
events_count.txt

Le anomalie di cui sopra si riscontrano nei primi due.
Mentre il secondo è solo un file per il conteggio di alcuni eventi particolari e che include le "caratteristiche" della simulazione.

Sperando che fin qui sia tutto chiaro, datemi cinque minuti e vi posto alcuni esempi di righe di comando per lanciare simulazioni, non troppo avide di risorse, ma che riproducano il problema.

(edit:
mi stanno cacciando dalla biblioteca, quindi aspetto di arrivare a casa per postare le righe di comando "incriminate")
Allegati
MetastableRandWalk.zip
(99.48 KiB) Scaricato 14 volte
Ultima modifica di l3on4rdo il giovedì 23 febbraio 2012, 19:05, modificato 1 volta in totale.
l3on4rdo
 

Successiva

Torna a Programmazione

Chi c’è in linea

Visualizzano questa sezione: Gisnio e 7 ospiti