Controlla se i messaggi speciali ricevuti dal flusso di dati

2

Ricevo continuamente flussi di dati di messaggi di registro. In ogni flusso di dati ci sono alcuni messaggi speciali che rappresentano stati.

Ora voglio monitorare se tutti gli stati sono stati raggiunti fino alla fine del flusso di dati. E se no, quale stato raggiunto alla fine.

Non so come implementarlo in modo efficiente. Stavo pensando di usare due liste. Una lista statica in cui sono memorizzati tutti gli stati possibili. E una lista dinamica in cui posso aggiungere tutti gli stati attualmente riceventi all'interno del flusso di dati corrente. In modo che possa controllare ogni messaggio, se il messaggio è nell'elenco statico, allora posso aggiungerlo all'elenco dinamico.

E quando il flusso di dati termina, posso vedere quali stati ho ricevuto e quali stati sono mancanti. Per il flusso di dati successivo posso cancellare l'elenco dinamico e ricominciare.

È un modo generale di fare qualcosa del genere? O conosci un modo più efficiente?

    
posta CPA 16.09.2016 - 13:50
fonte

1 risposta

1

(Concentrandoti sul tuo problema di rendimento)

Non sono sicuro di aver compreso i limiti del tuo problema, ma nonostante questo implichi ovviamente un algoritmo online, c'è questa supposizione che può aiutare molto verso un'implementazione semplice ed efficiente:

l'ipotesi è che tu conosca in anticipo l'insieme di tutti i possibili messaggi distinti che potrebbero (o non potrebbero) provenire dal tuo stream di input, in modo che:

(scusate lo pseudo codice qui sotto, è solo che preferisco che il mio arrugginito Java non si intrometta in modo così scorretto da confondere e oscurare l'idea, ma potrei dare una possibilità a una versione C # qualche tempo dopo se c'è interesse in questo)

Fase iniziale

1) in una prima coppia di mappe, costruisci una volta per tutte una perfetta funzione di hash (in effetti, una biiezione, anche) del tuo corpus di messaggi (ad esempio, digitato con un semplice tasto intero):

(cache di, per esempio, funzione / direzione "mapBy", nella notazione della firma)

mapBy : Integer -> Message

cioè.,

1 -> message 1

2 -> message 2

etc...

e

(cache inversa di "mapBy", alias "hashOf" function / direction)

hashOf : Message -> Integer

cioè.,

message 1 -> 1

message 2 -> 2

etc...

Naturalmente, la costruzione / inizializzazione di mapBy è banale, poiché si enumerano tutti i messaggi noti e si assegna una chiave intera distinta a ciascuno di essi (zero o chiave basata su uno o negativa, anche, che non importa qui - riguarda solo l'unicità)

La costruzione / inizializzazione di hashOf segue direttamente.

2) crea una terza mappa hash Integer - > Messaggio (diciamo "raccolto"), inizialmente vuoto

gathered : Integer -> Message

Fase online

3) mentre leggi e analizzi il tuo input nei messaggi da ciascun "datagramma" di quel flusso, uno dopo l'altro, solo "calcola" (in realtà, una semplice ricerca):

key = hashOf[message]

e metti quella (chiave, messaggio) nella raccolta, se la chiave non è già presente lì. Chiaramente, sia la ricerca della chiave che i tempi di inserimento raccolti saranno O (1) e senza collisioni sugli inserimenti di sempre (grazie all'utilizzo di un numero intero di chiavi raccolte) come bonus.

Puoi semplicemente tenere traccia di una variabile locale (o membro di istanza, se l'elaborazione del tuo stream è stateful a causa di altri requisiti) dell'ultima coppia (chiave, messaggio) che hai dovuto inserire raccolti (a causa dell'incontro di quella chiave / messaggio per la prima volta, a quel punto nello stream).

Risultati

4) quando hai terminato di leggere il flusso, riunito ha tutti quelli dei tuoi "messaggi speciali" che sono stati letti e riconosciuti in tutto lo stream e che puoi quindi enumerare con:

(Pseudo codice)

for each (key in gathered) {
    message = mapBy[key]
    // do something with message...
}

Naturalmente, saprai anche se hai individuato tutti i messaggi possibili / noti, raccolti, se e solo se:

count(gathered) == count(mapBy) ( == count(hashOf) )

o se è solo un sottoinsieme di quelli, altrimenti.

Infine, naturalmente, se il corpus di possibili messaggi è molto più ricco / più grande di un set di "costanti di stringa" abbastanza piccolo (e quindi non può stare in memoria per memorizzare mapBy e hashOf), ma può ancora essere abbinato in modo inequivocabile come una parola di un linguaggio (regolare o privo di contesto) (ad es., regex di stringhe, uno per "tipo di messaggio"), probabilmente andrai per una variante allo stesso modo:

(nella notazione della firma)

mapBy : Integer -> Regex

hashOf : Regex -> Integer

e

gathered : Regex -> List of Message

mentre il passaggio (3) diventa:

(Pseudo codice)

regex = find the first regex (e.g., in mapBy) that matches message // details omitted
if (regex == null) {
    throw error
}
if (regex in gathered (as a key)) {
    list = gathered[regex] // meaning: lookup list of message, by regex
} else {
    list = new list of message
    gathered[regex] = list // meaning: add (regex, list) to gathered
}
if (not message in list) {
    add message to list
    last = message
}

Ref.

Hash perfetto:

link

'HTH,

    
risposta data 17.09.2016 - 00:06
fonte

Leggi altre domande sui tag