La tua domanda sulla scelta appropriata della struttura dei dati non fornisce abbastanza dettagli sul problema che stai cercando di risolvere. Domande che avrei chiesto di persona quando tento di aiutarti a includere:
- Quante sessioni attive ti aspetti in media e al massimo? Cioè, qual è il valore N di cui dobbiamo preoccuparci per la complessità asintotica delle operazioni?
- Quali sono i tuoi limiti di latenza di risposta e consumo di memoria?
- Qual è il mix relativo di operazioni di aggiunta / rimozione / query?
- Puoi fare una stima ragionevolmente affidabile di quali TID di ordine arriveranno? (Se sì, la maggior parte delle operazioni sulla nostra struttura dati sarà all'inizio o alla fine, con un minimo bisogno di operazioni di ricerca)
- Sai per certo che tutti i TID che hai in mano riceveranno alla fine un aggiornamento? (Alternativa: alcuni elementi nella tua struttura dati in memoria corrispondono a TID che non vedrai mai più, perché non ti è sempre garantito di vedere un evento di "fine sessione").
Non conoscendo queste cose (non conosco il dominio dell'applicazione o la "dimensione" se il tuo sistema pianificato) posso solo fare supposizioni ragionevoli, ma ti prego di perdonarmi se indovino sbagliato.
Ho intenzione di indovinare:
- Molti; consentire alla struttura dati risultante di riempire la memoria, se necessario.
- I requisiti di latenza sono compresi nell'intervallo da 1 ms a 100 ms, il che significa che dovremmo idealmente evitare gli accessi al disco, in questo caso le operazioni evitabili del database. I requisiti di consumo di memoria sono molto più vaghi ma supponiamo di non poter utilizzare una struttura di dati sparsa (ad esempio una tabella hash). La logica è che se abbiamo una certa quantità di memoria, probabilmente ci sono altri tipi di dati che è più utile conservare di questa informazione (di nuovo, se sapessi di più sul tuo dominio applicativo, ciò sarebbe di aiuto ...)
- aggiungi: rimuovi: i rapporti di query sono vicini a 1: 1: 1.
- Supponiamo di non poter prevedere l'ordine di arrivo del TID
- Supponiamo che non possiamo essere sicuri che vedremo tutte le sessioni ordinatamente chiuse (quindi dobbiamo adottare una struttura dati che permetta a qualche tipo di processo separato di governante di eliminare occasionalmente TID stantii).
Se queste ipotesi sono più o meno corrette, probabilmente utilizzerei un mucchio. Gli heap sono più densi degli elenchi collegati e molto più densi delle tabelle hash. Ogni voce heap conterrà il TID come chiave e qualsiasi altro dato di payload che possiedi (non hai detto, ma se non c'è un carico utile aggiuntivo, va bene anche così).
Usare un heap significa che tutte le operazioni (inserimento, cancellazione, ricerca) sono O (log (N)). Se le query sono molto più comuni di insert / delete, dovremmo considerare di pagare la memoria per ottenere velocità (ad esempio usando una tabella hash, le operazioni sono O (1) ma viene utilizzata più memoria). Al contrario, se la tua struttura dati potrebbe diventare molto grande, dovresti considerare l'uso di un heap B invece di un heap binario regulat, perché è più gentile con il sistema di memoria virtuale. Vedi Stai sbagliando di Poul-Henning Kamp , che descrive un sistema di cache con alcuni (piuttosto piccolo) grado di somiglianza con quello che stai facendo.
Se il tuo heap è rappresentato come una matrice, potresti avere problemi a crescere oltre la dimensione iniziale dell'array. Utilizzando lo schema tradizionale di raddoppiamento della dimensione dell'array quando si riempie, si ammortizzerà il sovraccarico dell'operazione di copia in modo da poter mantenere le prestazioni logaritmiche. Ma vorrebbe dire che occasionalmente, una delle operazioni di inserimento richiederà molto, molto più tempo di altre. L'altra proprietà di un heap è che la maggior parte delle implementazioni sono progettate per l'utilizzo a thread singolo. Se uno di questi due problemi sarà un problema per te, considera l'utilizzo di un albero bilanciato invece di un heap.