[C] Calendario Eventi

[fedo]

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

[cionci]

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...

[fedo]

grazie...

sto pensando ad una lista doppiamente collegata...

[cionci]

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...

[fedo]

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

[fedo]

Accidenti

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

[cionci]

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)...

[fedo]

Grazie!

ora vediamo cosa tiro fuori...

[fedo]

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

[cionci]

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...

[fedo]

che non è poco...

grazie..come al solito sei un buon intenditore

[fpucci]

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

[fedo]

se mi passi il sorgente, ti bacio le mani

[fpucci]

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

[fedo]

infatti una soluzione del genere l'avevo pensata...


grazie

[cionci]

Ma tu hai dettto che non puoi usare l'allocazione dinamica...

Comunque quella struttura è davvero ottima...non ci avevo pensato...

[fedo]

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

[cionci]

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...

[cionci]

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...

[fpucci]

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