(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,