La migliore collezione da usare? [chiuso]

Question

Sto leggendo i file di registro ma non tutte le righe vogliono essere elaborate immediatamente. Sto usando una coda / buffer per memorizzare le linee mentre attendono di essere elaborate.

Questa coda viene regolarmente sottoposta a scansione per determinate linee: quando vengono trovate, vengono rimosse dalla coda (possono trovarsi ovunque in essa). Quando non è possibile trovare una linea particolare, le linee vengono rimosse dall'inizio della coda una per una per essere elaborate.

Pertanto, la coda richiede quanto segue:

• In grado di essere ridimensionato (o dare quell'impressione)
• Rimuovi elementi da qualsiasi luogo
• Aggiunta di elementi (sarà sempre alla fine della coda)
• Scansione rapida
• A seconda delle prestazioni, avere un puntatore su dove è arrivato nell'ultima scansione.

Inizialmente ho scritto il codice quando avevo poca esperienza con Java o l'API, e ho appena usato un ArrayList perché sapevo che avrebbe funzionato (non necessariamente perché era l'opzione migliore).

Le sue prestazioni ora stanno peggiorando con sempre più registri che devono essere elaborati - quindi, quale raccolta consiglieresti di usare in questa situazione? C'è sempre la possibilità di scrivere anche la mia.

Grazie

Answer 1

LinkedHashSet potrebbe essere di interesse. È effettivamente un HashSet ma mantiene anche un LinkedList per consentire un ordine di iterazione prevedibile - e quindi può anche essere usato come una coda FIFO, con il piacevole vantaggio che non può contenere voci duplicate.

Dato che è anche un HashSet, le ricerche (al contrario delle scansioni) possono essere O (1) se possono corrispondere su equals()

Answer 2

Un LinkedList sarebbe probabilmente il più appropriato. Ha tutte le proprietà richieste e consente di rimuovere i collegamenti dalla metà in tempo costante, piuttosto che il tempo lineare richiesto per un ArrayList.

Se hai una strategia specifica per trovare l'elemento successivo da rimuovere, una PriorityQueue o anche un set ordinato potrebbero essere più appropriati.

Answer 3

La scansione rapida implica generalmente un'implementazione basata su hash di qualche tipo, una ConcurrentSkipListMap potrebbe essere una buona implementazione. Accedi (n) sulla chiave contenente, rimuovi e ottieni metodi, ed è ordinato in modo da poter avere una sorta di priorità associata ad esso.

Answer 4

Non voglio ordinare le righe da leggere (devono essere mantenute nel loro ordine originale). Tuttavia, potrei potenzialmente bloccare le linee in base a un ID di sessione che ha ciascuna linea registrata (più linee registrate per sessione).

Pensandoci, potrei potenzialmente avere un:

HashMap<String,LinkedList<String>>

e fornisci l'id di sessione come chiave e popola la LinkedList con le righe appartenenti alla sessione.

La mappa fornirebbe un modo rapido per cercare le linee da fare con la sessione X, e quindi l'elenco collegato fornirebbe le migliori prestazioni per aggiungere / rimuovere le linee (le prestazioni di ricerca consistevano nel trovare le linee da fare con la sessione x, quindi le righe effettive che hanno a che fare con la sessione x possono essere lette e rimosse dall'inizio alla fine - spinte / saltate).

Esiste una raccolta migliore dell'elenco collegato che si ridimensionerebbe, con le linee aggiunte alla fine e sempre prese dall'inizio? Credo che la raccolta di code estenda comunque l'elenco collegato?

Answer 5

Poiché è necessario rimuovere e aggiungere elementi dal set e cercare valori specifici, forse una struttura migliore potrebbe essere qualcosa che implementa SortedSet, come TreeSet. Questa classe garantisce le prestazioni del registro (n) per aggiungere, rimuovere e contenere.

Answer 6

Suppongo che alcuni thread scriveranno in coda e ne leggerà un altro.

In questo caso dovresti guardare le code nel pacchetto java.lang.concurrent.

Puoi usare un PriorityBlockingQueue per permettergli di ordinare gli elementi per te, o un LinkedBlockingQueue se vuoi iterare su di esso e scegliere tu stesso gli elementi da rimuovere.

Answer 7

Sono d'accordo con AVI e l'elenco collegato sarebbe la tua migliore opzione. Puoi ridimensionare facilmente, aggiungere rapidamente alla fine dell'elenco, rimuovere rapidamente da qualsiasi luogo. La ricerca non sarà veloce, ma non peggio di qualsiasi altro elenco non ordinato.

Answer 8

Guava può essere d'aiuto.

  

Il progetto Guava contiene diverse librerie di base di Google su cui facciamo affidamento nei nostri progetti basati su Java: raccolte, memorizzazione nella cache, supporto di primitive, librerie di concorrenza, annotazioni comuni, elaborazione di stringhe, I / O e così via.