Coda implementata con blocchi

Concetti di programmazione, algoritmi, design pattern, stime, tempi sviluppo software

Moderatori: Toki, M.A.W. 1968

Regole del forum
Leggi: IProgrammatori.it - Regolamento Forum
Avatar utente
Alan_Reloaded
Utente Junior
Messaggi: 81
Iscritto il: 27 ago 2015, 23:41
Località: Roma

Coda implementata con blocchi

Messaggioda Alan_Reloaded » 19 mag 2017, 12:50

Ciao Forum,

Poiché mi serviva una coda per bufferizzare la seriale, trattandosi di singoli byte e di una quantità di elementi molto variabile (fossi stato certo di un limite superiore ovviamente tutto sarebbe stato banale) ho pensato di implementare la coda come una lista concatenata di blocchi di bytes più dati ausiliari. In pratica la mia struttura dati contiene un array di bytes, i puntatori ai blocchi precedente e successivo (so che si può fare con uno solo ma sono abituato così) e gli indici che delimitano la parte di blocco effettivamente usata. Se devo estrarre il primo elemento lo copio e diminuisco l'indice superiore, se il blocco si svuota viene deallocato, se il primo blocco ha indice zero ne alloco uno nuovo e lo inserisco a inizio lista, e così via.

Il tutto mi funziona apparentemente bene ma non essendo io un ingegnere del software non sono certo di aver creato una serie di test abbastanza esaustiva da farmi escludere bachi. Dato che il mio progetto sta diventando un po' grande ho paura che un baco in parti a basso livello possa passarmi inosservato e farmi cercare a vuoto.

Dunque, la domanda è: implementazioni come quella che ho messo in piedi, si fanno o è una soluzione goffa? E nel caso, che nome hanno così posso cercare in rete? Esistono che voi sappiate librerie con relativa test suite? Magari potrei tentare qualche confronto.

grazie e ciao!

A.
Avatar utente
LPs
Utente Senior
Messaggi: 209
Iscritto il: 09 mag 2017, 21:34

Re: Coda implementata con blocchi

Messaggioda LPs » 19 mag 2017, 13:31

Sinceramente, per come hai descritto la situazione, mi sembra che tu abbia puntato un po' troppo sul complicato.

Forse sarebbe bastata una coda circolare semplice (un array) con due indici (p_in e p_out), ma non conoscendo il sistema e i requirements, non so se sia applicabile.
L'immaginazione è più importante della conoscenza. La conoscenza è limitata, l'immaginazione abbraccia il mondo - Albert Einstein

LPs-On StackOverflow
Avatar utente
Alan_Reloaded
Utente Junior
Messaggi: 81
Iscritto il: 27 ago 2015, 23:41
Località: Roma

Re: Coda implementata con blocchi

Messaggioda Alan_Reloaded » 19 mag 2017, 13:38

Forse è come dici, probabilmente sono troppo condizionato dall'8088 e sprecare memoria mi dà fastidio; so che oggi non è un problema nemmeno su Raspberry ma è più forte di me. Inoltre, uno dei requisiti che mi ero prefissato è quello di poter conservare tutti i dati della seriale ovviamente ponendo un limite superiore alla memoria usata. In pratica se i dati vengono letti è chiaro che un solo array basta e avanza (parliamo di qualche k al massimo) ma se si accumula qualche decina di mega mi dispiacerebbe allocare tanto spazio per il caso peggiore, spazio che resterebbe quasi sempre inutilizzato.
Avatar utente
LPs
Utente Senior
Messaggi: 209
Iscritto il: 09 mag 2017, 21:34

Re: Coda implementata con blocchi

Messaggioda LPs » 19 mag 2017, 13:56

Beh nel caso, se usi delle liste stai comunque allocando dinamicamente, quindi potresti permetterti di realloc-are il tuo buffer in base alle evenienze.

Dipende comunque dalla complessità dei dati che ti arrivano: un buon DMA potrebbe tranquillamente gestire quasi interamente la gestione scaricandoti da molto lavoro.

Comunque il tuo approccio è valido in ogni caso, un pelino poco debuggabile (opinione puramente personale), ma in ogni caso funzionante.
L'immaginazione è più importante della conoscenza. La conoscenza è limitata, l'immaginazione abbraccia il mondo - Albert Einstein

LPs-On StackOverflow
Avatar utente
Alan_Reloaded
Utente Junior
Messaggi: 81
Iscritto il: 27 ago 2015, 23:41
Località: Roma

Re: Coda implementata con blocchi

Messaggioda Alan_Reloaded » 19 mag 2017, 14:10

LPs ha scritto:Beh nel caso, se usi delle liste stai comunque allocando dinamicamente, quindi potresti permetterti di realloc-are il tuo buffer in base alle evenienze.


Ci avevo pensato ma non ero certo di saper valutare l'impatto delle operazioni di copiatura. Avevo valutato anche l'idea di una sorta di sistema adattativo che regolasse la dimensione del buffer su qualche retta di regressione ottenuta con la quantità di elementi utilizzati negli ultimi N accessi ma mi sono detto che sono soluzioni sempre "pericolose" perché non danno garanzia sulla velocità media. Ho comunque la curiosità di capire se le operazioni di riallocazione sono sufficientemente "risparmiose" come velocità, il tutto da contrapporre alla maggior complessità della soluzione che ho adottato.
Avatar utente
LPs
Utente Senior
Messaggi: 209
Iscritto il: 09 mag 2017, 21:34

Re: Coda implementata con blocchi

Messaggioda LPs » 19 mag 2017, 14:36

... se le operazioni di riallocazione sono sufficientemente "risparmiose" come velocità,...


Non saprei darti una valutazione oggettiva, dipende dalla piattaforma, dalle sue features e anche dalla toolchain/SDK che stai utilizzando.
Il buon vecchio benchmarking penso sia la via giusta per capirlo.
L'immaginazione è più importante della conoscenza. La conoscenza è limitata, l'immaginazione abbraccia il mondo - Albert Einstein

LPs-On StackOverflow
Avatar utente
Alan_Reloaded
Utente Junior
Messaggi: 81
Iscritto il: 27 ago 2015, 23:41
Località: Roma

Re: Coda implementata con blocchi

Messaggioda Alan_Reloaded » 19 mag 2017, 16:41

Visto quanto mi è costata l'implementazione (niente di difficile, solo che controllare tutto porta via tempo) quasi quasi la re-implemento con la riallocazione e metto al lavoro il profiler confrontando le due versioni... credo che MinGW ne abbia uno, è il momento di imparare come usarlo ^_^

Torna a “Ingegneria del Software”

Chi c’è in linea

Visitano il forum: Nessuno e 13 ospiti