Newsgroup: it.comp.lang.c++
Titolo: Algoritmo per Parsing

Salve a tutti!
Faticosamente cerco di *ammaestrarmi* al C++ e cosa c'e' di meglio per
imparare
se non mettere le zampe in qualche progettino utile?
Bene, devo risolvere un problema (per quasi tutti voi sara' di facile
soluzione)
che tentero' ora di spiegare nel modo piu' chiaro possibile.
Oggetto: PARSING di un buffer (o file).
Per snellire la spiegazione ho semplificato la struttura dei dati:
typedef struct {
   TipoComando Comando;
   TipoDato    Dato;
   TipoTime   TimeStamp;
} Event;
typedef Event* LPEVENT;
a disposizione c'e' una funzione del tipo:
 LPEVENT ReadEvent(TipoBuffer* Buffer)
che legge sequenzialmente il buffer di input.
A corredo ci sono anche altre funzioni che restituiscono il
numero di record di tipo Event, che riposizionano il pointer
all'inizio del buffer e volendo c'e' anche una funzione che
permette l'accesso casuale al file (SeekEvent)
Il buffer contiene un numero _nEvents_ di blocchi di tipo Event
esempio:
 Comando        Dato        TimeStamp
   On                  A               T1
   On                  B               T2
   On                  C               T3
   .....                  ...              .......
   Off                  A               Tk
   ....                   ...               .......
   Off                  B                Tj
    .....                ...                .......
   On                  A                Ti
     ....                 ...               .......
   Off                  A               Tq
   Off                  C               Tr
etc...
Il vincolo che il buffer sia ordinato *sempre e comunque* sulla
base di TimeStamp crescenti non e' assicurato (lo devo ancora
verificare),
mentre e' strettamente osservato il vincolo che un comando _On_ *precede
sempre*
un comando _Off_ che si riferisce allo *stesso* Dato (*non* si hanno,
cioe',
due comandi di tipo _ON_ (_Off_) consecutivi afferenti allo stesso
Dato).
Inoltre un Dato puo' essere innescato (On) e successivamente disattivato
(Off)
un numero arbitrario di volte,
LA SPECIFICA:
Quello che devo fare, in sostanza, e' un parsing del buffer in esame e
collezionare
in un buffer (meglio ancora un <Vector>, dato che una volta costruito
l'oggetto in
questione non necessita di essere modificato dinamicamente se non
eccezionalmente)
oggetti del tipo:
typedef struct {
   TipoDato  Dato;
   TipoTime  IstanteInizio;
   TipoTime  Durata;
} DecEvent;
Il Buffer (array) deve essere poi ordinato per valori crescenti degli
attributi IstanteInizio.
Per l'esempio precedente si dovrebbe ottenere:
 Dato     IstanteInizio     Durata
  A              T1                 D1=T1-Tk
  B              T2                 D2=T2-Tj
  C              T3                 D3=T3-Tr
  A              Ti                  Di=Ti-Tq
Quello che mi interessa e' un algoritmo che esegua il parsing in maniera
"intelligente". Il mio credo che non lo sia affatto:
1- per ogni record di tipo Event letto avente comando _On_ creo una
istanza di DecEvent
   e la metto nel buffer con Durata = 0.
2- per ogni record letto con comando Off scandisco il buffer di output
alla ricerca
   del primo (e unico) record con stesso Dato e con Durata = 0: aggiorno
la durata.
3- Alla fine: un bel algoritmino di ordinamento.
Va da se che questa soluzione e' inefficiente perche' per ogni record
letto con
comando _Off_ devo scandire tutto (nella versione piu' ingenua) il
buffer di output alla
ricerca del record con stesso Dato e con Durata = 0.
Una soluzione alternativa che mi viene or ora in mente e' mantenere due
buffer di output
uno per le istanze di DecEvent "completate" (con durata non nulla)
uno per quelle istanze con comando _Off_ pendente (con durata nulla)
Questo mi limiterebbe la scansione al solo secondo buffer, poi quando è
stato trovato il
record opportuno lo "metto" nel primo buffer.
Al termine della scansione, se tutto e' filato via liscio, dovrei avere
il primo buffer
"pieno" e il secondo vuoto.
Cosa ne pensate?
Il problema e' puramente concettuale (di buona programmazione e stile),
dato che da una prima analisi di stringenti requisiti di efficienza non
ne dovrei
avere data l'esigua dimensione degli oggetti in esame e dall'esiguo
numero di essi
(da qualche centinaio a poche migliaia al massimo).
Ciao
  Il Tasso.

...
    [snip]
Riassumendo: il parsing c'entra poco, comunque: l'input
e` una sequenza di eventi (strutture con tre campi: un
Comando, ON o OFF, un Dato, quello a cui si riferisce
il Comando, e un Timestamp, l'evento del comando),
col vincolo che per ogni certo dato gli ON e gli OFF si
alternano (e la possibilita`, non certezza, che i time
stamp siano in ordine crescente); l'output deve essere
una sequenza di "intervalli" (strutture con tre campi:
un Dato [quello dei comandi On e Off], un Timestamp
[quello del comando On di questo intervallo] e la
durata [differenza fra timestamp di OFF e ON]), il
tutto rigorosamente ordinato in ordine di timestamp
crescente.
iltasso riporta lo schema di una soluzione funzionante,
il cui "problema" e` quello, quando arriva un evento Off,
di trovare il corrispondente evento On in una "pila" di
eventi "pendenti" (non ancora matchati).  Naturalmente
se l'ordine crescente di timestamp non e` garantito in
input ma dev'esserlo in output occorrera` un passo di
sort sulla sequenza finale di risultato.  Pero` lo schema,
ha due piccoli difetti, di cui iltasso nota il primo:
-- il tempo di ricerca di un "evento On corrispondente"
    e` lineare nel numero di diversi dati.
    [Questo, se occorre, puo` essere ovviato con
     facilita` mantenendo una std::map<> che porta
     (in tempo logaritmico) dal Dato, all'evento ON
     ad esso corrispondente -- piccola ottimizzazione,
     se tale e`, applicabile "localmente" (ma non e`
     detto che convenga, se i dati pending sono pochi)
-- se anche le timestamp sono garantite crescenti in
    input, qui non e` piu` garantito che lo siano in output,
    es. la sequenza: ON-A, ON-B, OFF-B, OFF-A,
    provoca prima l'emissione dell'intervallo di B anche
    se e` iniziato dopo quello di A, solo perche` e` anche
    *finito* dopo.  Quindi risulta *comunque* necessario
    un sort sulla sequenza-risultato.
Quest'ultimo difetto si puo` rimediare (se le timestamp
sono garantite crescenti in input, evitando la "grossa"
spesa del sort alla fine) come segue:
tenere tre strutture:
    -- la coda degli eventi pending (si e` visto solo l'ON)
        [ed eventuale mappa Dato->Evento x accelerare];
    -- la struttura/sequenza di output come nell'algoritmo
        originale;
    -- un'altra struttura di risultati (intervalli) "gia`pronti ma
        non ancora emessi come output"
Quando arriva un On: metterlo sulla prima coda
Quando arriva un Off: trovare l'On corrispondente
    nella prima coda, toglierlo dalla coda stessa,
    formare l'intervallo risultante, poi:
    -- SE l'On rimosso era IL PIU` VECCHIO (timestamp
        piu` bassa) della coda pending, allora, emetterlo
        sull'output, poi, sino a quando la timestamp del
        risultato piu` vecchio sulla struttura e` piu` vecchia
        di quella dell'evento piu` vecchio rimasto sulla coda
        pending, emettere risultati dalla struttura all'output;
    -- ALTRIMENTI, mettere l'intervallo risultante nella
        struttura
Si vede chiaramente che la "struttura" non e` altro che
una "coda a priorita`" (priority queue) agevolmente
realizzabile come std::priority_queue<> delle librerie
standard C++ -- i risultati pronti ma non ancora emessi
vi sono immessi "a caso", ma in qualsiasi momento
interessa vedere solo il "minimo" (piu` vecchio) di quelli
che sono sulla struttura in questo momento.
Questa, se le timestamp d'ingresso sono crescenti e
l'ingresso (e quindi l'uscita) lunghi, puo` essere una
ottimizzazione cruciale perche` risparmia un passo di
sort NlogN con N=lunghezza dell'uscita (inoltre, e in
certe applicazioni puo` essere importante, ogni item
di output e` emesso "appena possibile", mentre se si
dovesse fare un sort non si potrebbe dare NESSUN
output sino a che l'input non e` del tutto terminato...!).
Alex