View Full Version : [C] Calendario Eventi
Ciao a tutti..
in questo periodo sto sviluppando del codice per un' applicazione per la gestione del traffico ferroviario.
Il settore di cui mi occupo è quello del "calendario eventi".
In pratica è una lista ordinata cronologicamente di tutti gli eventi che si verificano sul traffico (es. semaforo verde fra 2 minuti, treno in partenza fra 30 sec., etc...)
La struttura di un singolo evento è generica: c'è un ID evento, il timestamp e altre variabili di servizio.
La lista deve poi essere aggiornata ogni secondo, perchè lo scorrere inesorabile del tempo, decreterà quali sono gli eventi scaduti (un semplice confronto tra il timestamp attuale e quello dell' evento).
Secondo voi, che struttura è preferibile usare per gestire questo calendario? non ci sono imposizioni sulla memoria (ovvero si può fare tutto statico), ma la gestione degli eventi deve essere veloce..
Dapprima pensavo ad un array statico di "struct evento", ma poi mi sono reso conto che per quanto intuitivo e semplice, è un bordello inserire eventi nelle locazioni interne dell' array, perchè bisogna shiftare di un posto tutti gli eventi che andranno a scadere successivamente..
Dunque penserei ad una lista singolarmente collegata..è più efficiente da gestire come struttura, ma è più fragile (con i puntatori non sai mai cosa può accadere ;) )
Cosa sarà meglio adottare? avete in mente altre soluzioni?
Grazie..ciao
Sicuramente la lista... E' l'ideale per una situazione del genere...
Evita la ricorsione...la differenza di velocità è minima, ma se gli eventi sono molti ti si potrebbe pienare lo stack...
grazie...
sto pensando ad una lista doppiamente collegata...
Se gli eventi + lontani vengono inseriti in coda non ha senso fare una lista doppiamente collegata...a meno che tu non li debba scorrere dal più lontano al + vicino...
infatti non lo faccio perchè devo scorrere il tempo all' indietro...
mi serve per migliorare l' inserimento di eventi nel mezzo della catena: per inserire al posto giusto, devo trovare l'evento che sta subito prima cronologicamente e quindi piazzare l'evento subito dopo..
Immagina una catena di 400 eventi...fatti 350 comparazioni di timestamp solo prchè l' evento si và ad inserire in 351 posizione...
invece così potrei partire dal 400 e farmi solo 49 comparazioni all' indietro...
ovviamente non sto qui a spiegare tutto l'algoritmo per capire se conviene partire dall'inizio o dalla fine (c'è anche un "segnalino" al centro della catena) ;)
comunque è carino questo progetto ;)
ciao
Accidenti :mad:
Mi hanno detto che non posso usare memoria dinamica! quindi niente malloc!
Se voglio usare le liste doppie, devo piazzarle dentro un array statico...
una lista in un array? Non conosco questa tecnica..mai usata...
sapete dirmi nulla in proposito...dove becco documentazione? con Google non ho trovato una mazza. ;)
Ciao
Scusa, ma come fai a non usare array dinimaci ? Limiti dimensionalmente il problema ?
La lista in un array è facile... E' uguale alla lista normale...
struct lista {
struct info i;
lista *next;
liste *prev;
int used;
};
Se ad esempio l'elemento corrente è prima dell'1 e dopo l'8 allora:
next == &vet[1] e prev == &vet[8]
In alternativa puoi fare next e prev interi che contengono l'indice dell'array...ma sono operazioni più complesse ogni volta che accedi ad un elemento...
La variabile used ti indicherà se l'elemento è in uso oppure no...
Io mi terrei il numero di elementi liberi e l'indice del primo elemento libero...inoltre ogni volta che fai un inserimento dovresti cercare il prossimo elemento libero (il metodo più veloce di ricerca dovresti studiartelo per bene)...
Grazie!
ora vediamo cosa tiro fuori... ;)
Come lo vedi se uso 2 array?
1 dove metto le struct evento e l'altro dove metto i puntatori ad ogni evento del primo array..
l'ordine temporale lo faccio ordinando l'array dei puntatori e non quello degli eventi (più pesante da gestire)..
Mi costerebbe tanto fare gli shift dei puntatori? Io penso sia leggero da fare..sempre meglio che shiftare le struct evento..
che dici?
ciao
Ottima idea, ma credo che si possa fare di meglio...
Con un cosa del genere:
struct evento *vett[N];
ad ogni cancellazione dovresti compattare l'array...
Invece facendo una cosa del genere:
struct lista {
struct lista *prev;
struct evento *e;
struct lista *next;
int usato;
};
struct lista l[N];
struct lista *primo_libero = l;
La cancellazione si riduce a:
cur->usato = 0;
if(cur < primo_libero) primo_libero = cur;
if(cur->prev) cur->prev->next = cur->next;
if(cur->next) cur->next->prev = cur->prev;
L'inserimento, la modifica e la ricerca sono circa della stessa complessità (magari leggermente più lenti in questo caso, ma proprio poco)...ma hai il grosso vantaggio della cancellazione...
che non è poco...
grazie..come al solito sei un buon intenditore ;)
Originariamente inviato da fedo
[...]
Dunque penserei ad una lista singolarmente collegata..è più efficiente da gestire come struttura, ma è più fragile (con i puntatori non sai mai cosa può accadere ;) )
Cosa sarà meglio adottare? avete in mente altre soluzioni?
Io ho lavorato su un sistema molto simile al tuo.
Ho fatto delle liste linkate.
Vai alla grande coi ptr e sono pure veloci.
Ho fatto un array di 1440 puntatori (un elemento per ogni minuto della giornata) ed ogni elemento era un ptr ad una lista di eventi
se mi passi il sorgente, ti bacio le mani ;)
Ci ho lavorato oltre dieci anni fa ;)
Ti definisci un array statico di 1440 elementi di puntatori ad una struttura EVENT. (Io ne avevo tre perché gestivo tre giorni: ieri, oggi e domani)
La struttura EVENT deve contenere, oltre ai dati che servono per descrivere l'evento, un puntatore alla struttura stessa Iinizialmente valorizzato a NULL per indicare la lista vuota).
typedef struct EVENT_T {
...
...
...
struct EVENT_T * Next;
} EVENT
EVENT ListaEventiGiornalieri [1440];
Ogni volta che devi inserire un evento, ti ricavi il minuto in cui quell'evento scatta (un intero compreso tra 0 e 1439) e vai ad allocare dinamicamente un elemento di tipo EVENT in corrispondenza dell'i-esimo elemento dell'array (con i = minuto_in_cui_scatta_evento), eventualmente aggiungendolo a quelli già presenti.
Se invece i tuoi eventi richiedono una risoluzione del secondo anziché del minuto, ti farai un array pari a 86400 elementi, tanti quanti sono i secondi di una giornata:)
L'accesso è velocissimo perché tu accedi all'array mediante un indice che è pari al minuto (o al secondo) che ti interessa gestire e poi scorri la lista di tutti gli eventi che devi far scattare.
Spero che sia chiaro :)
infatti una soluzione del genere l'avevo pensata...
grazie
Ma tu hai dettto che non puoi usare l'allocazione dinamica...
Comunque quella struttura è davvero ottima...non ci avevo pensato...
infatti...mi hanno detto che non posso usare malloc()...
quindi...niente mem. dinamica...
La storia di fare un array dove ogni indice indica 1 sec. trascorso, è ottima...
Però, mano a mano che gli eventi in testa scadono, come faccio a far scorrere l' array nel tempo?
Cioè, immaginatevi una sliding window....il mio array dovrebbe scorrere...
ciao
Fare un array di liste, come consigliato sopra, era la cosa migliore... Ma mano che passa il tempo deallochi la lista corrispondente a quel minuto della giornata... Purtroppo se non puoi usare memoria dianmica allora questa soluzione diventa quasi imporponibile... Visto che dovresti fare un vettori di vettori (contenti liste) ed avresti problemi di dimensionamento delle liste... A meno che tu non abbia un vincolo che ti dice al max quanti aventi si possono verificare in un dato minuto...
Originariamente inviato da fedo
Però, mano a mano che gli eventi in testa scadono, come faccio a far scorrere l' array nel tempo?
ListaEventiGiornalieri[ora*60+minuto] sarebbe la lista che contiene glie venti che stanno per verificarsi...
Originariamente inviato da cionci
ListaEventiGiornalieri[ora*60+minuto] sarebbe la lista che contiene gli eventi che stanno per verificarsi...
Esatto!
Inoltre, non potendo usare memoria dinamica (e non ne capisco il perché, a meno che non sia una esercitazione) l'unica cosa che ti resta è quella di utilizzare un array di array tutti staticamente dimensionati.
Il problema è sapere a priori il numero massimo di eventi che puoi avere in un dato istante (per istante intendo il generico minuto o secondo della giornata). Se puoi dimensionare questa entità, puoi fare:
#define MAX_NUM_EVENTI 200
#define MIN_PER_DAY 1440
#define SEC_PER_DAY 86400
#define RISOLUZIONE SEC_PER_DAY /* oppure MIN_PER_DAY */
...
...
EVENT ListaEventiGiornalieri [RISOLUZIONE] [MAX_NUM_EVENTI] ;
Originariamente inviato da fpucci
Esatto!
Inoltre, non potendo usare memoria dinamica (e non ne capisco il perché, a meno che non sia una esercitazione)
Vallo a dire al professore :rolleyes:
Per una cosa del genere, la memoria dinamica era praticamente necessaria... :cry:
La storia del vettore di vettori non mi piace...
Invece, non si può stabilire a priori quanti eventi accadranno nello stesso secondo...putroppo l' unica costante fornita dai requisiti di progetto è quella MAX numero Eventi gestibili...
ma gestibili dal calendario, non nello specifico istante....
CMQ siete grandi! grazie per l'aiuto....mi sembre un lavoretto interessante..
Originariamente inviato da fedo
Vallo a dire al professore :rolleyes:
Per una cosa del genere, la memoria dinamica era praticamente necessaria... :cry:
La storia del vettore di vettori non mi piace...
Un alternativa potrebbe essere quela di farsi un vettore con MAX_NUM_EVENTI_PER_CALENDARIO e ordinarli secondo l'istante in cui devono essere attivati.
Se gli eventi sono relativi a vari giorni della settimana, ti occorrerà un timestamp altrimenti ti basta un valore intero che ti riporti l'istante in cui l'evento deve scattare.
L'ordinamento del vettore lo puoi fare con il QuickSort fornito nella libreria del C (ad esempio)
La libreria C fornisce il QuickSort ? Non lo sapevo...
Secondo me gli conviene implementare una lista all'interno del vettore...
Tenere ordinato il vettore comporterebbe troppaperdita di tempo...
Ma le cancellazioni possono avvenire solamente in testa e gli inserimenti solamente in coda ? Oppure ovunque ?
Originariamente inviato da cionci
La libreria C fornisce il QuickSort ? Non lo sapevo...
la funz sort dovrebbe implementare quello
Originariamente inviato da Luc@s
la funz sort dovrebbe implementare quello
Attenzione che si parla di C...non di C++...
Nella libc esiste una funzione qsort, ma è standard ?
Originariamente inviato da cionci
La libreria C fornisce il QuickSort ? Non lo sapevo...
Secondo me gli conviene implementare una lista all'interno del vettore...
Tenere ordinato il vettore comporterebbe troppaperdita di tempo...
Ma le cancellazioni possono avvenire solamente in testa e gli inserimenti solamente in coda ? Oppure ovunque ?
Si, si chiama qsort() e si trova in stdlib.h ;)
Anche io credo che gli conviene puntare sulla lista all'interno del vettore (credo che tu intenda un vettore di vettori).
Il problema della cancellazione e degli inserimenti non si pone, nel caso specifico; iunfatti, non potendo usare memoria dinamica, si deve solo premunire di valorizzare un campo della struttura EVENT con un valore booleano per dire che quell'evento è buono oppure no.
Originariamente inviato da cionci
Attenzione che si parla di C...non di C++...
Nella libc esiste una funzione qsort, ma è standard ?
Yes;)
Originariamente inviato da fpucci
Anche io credo che gli conviene puntare sulla lista all'interno del vettore (credo che tu intenda un vettore di vettori).
Io intendo un unico vettore di dimensioni pari al max numero di eventi gestibili dal programma...e poi al suo interno sviluppare una specie di lista ordinata...vedi qualche post sopra...
gli eventi possono essere inseriti ovunque nel vettore...vi spiego meglio la storia:
altre persone stanno sviluppando un altro progetto che dovrà usare le mie funzioni..
loro faranno la parte "logica" (detta 'controller"), ovvero decideranno (in base a certi input) quando inserire un evento nel mio calendario.
Quando vorranno inserire un evento, invocheranno la mia funzione InserisciEvento(struct evento ev) , passandomi la struttura evento già bella e preparata in tutti i suoi campi.
i campi sono:
1- un ID evento
2- l' orario di scadenza dell' evento (timestamp in cui l'evento si
verificherà)
3- Altri parametri di servizio (sono struct..)
Da questo, capite bene che può accadere che si debba inserire un evento con timestamp posteriore all' evento di testa, ma anteriore all' evento di coda (perchè gli eventi sono temporalmente indipendenti)....ed ecco qua che gli inserimenti vanno fatti nel mezzo dell' array e vanno tenuti rigorosamente in ordine cronologico.
Putroppo possono verificarsi eventi con lo stesso timestamp! vanno gestiti.....
Questo per quanto riguarda l'inserimento.
Ora, il 'controller' invocherà in un loop continuo la funzione EventoScaduto(), la quale tornerà 1 se c'è un' evento scaduto...
anche questa funzione devo implementarla io..
per farla, ho bisogno che gli eventi siano ordinati cronologicamente nell' array, perchè io andrò a verificare sempre il timestamp dell' evento di testa e seguenti..in ordine..
Quando il controller andrà a trattare un evento scaduto, io posso toglierlo dal calendario con la EliminaEvento().
Devo farmi dire se il controller può rimuovere un Evento che sta in mezzo all' array, semplicemente perchè desidera toglierlo e non perchè sia scaduto...
Vi faccio sapere, sperando che queste info vi facciano inquadrare meglio il problema..
ciao
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.