Struttura dati ordinata in modo efficiente che supporta chiavi duplicate

Question

Sto cercando una struttura dati che ordini gli oggetti all'inserimento in modo efficiente. Vorrei ordinare questi oggetti (in questo caso gli individui) in base al valore di una particolare variabile (in questo caso l'idoneità).

La struttura dati deve consentire chiavi duplicate poiché un particolare valore di fitness può verificarsi in individui diversi. Questo è un problema perché, ad esempio, la struttura dati TreeMap non consente chiavi duplicate. Preferirei usare questo tipo di struttura ad albero a causa della sua efficienza O (log N).

Se inserissi le persone in una lista ordinata, l'efficienza sarebbe scesa a O (n), e l'ordinamento delle persone dopo che sono state inserite non sarebbe molto efficiente.

C'è una struttura dati che è efficiente, mantiene gli individui ordinati e supporta chiavi duplicate?

Aggiungo e rimuovo le voci molto spesso dopo che la struttura dei dati è stata creata, quindi ordinare gli oggetti dopo che la struttura è stata creata sarebbe molto costoso.

Answer 1

Entrambe Apache Commons e Guava supporto multimaps, che sono quello che stai cercando.

In alternativa, a seconda del caso d'uso, si potrebbe raccogliere gli elementi di un ArrayList e ordinare che poi in O (n lg n) tempo totale.

Oppure, è possibile definire un confronto che verifichi prima la forma fisica e altre proprietà di distinzione degli articoli se l'idoneità è uguale.

Answer 2

Se ti interessa solo l'ordine una volta che tutte le persone sono state aggiunte, e non aggiungere alcun nuovo individuo in seguito, quindi l'ordinamento di un ArrayList è probabilmente l'opzione più veloce.

Altrimenti, è possibile utilizzare un set di alberi e disporre di un comparatore che confronta prima per idoneità, quindi per identity hash code se le condizioni sono uguali (o per qualsiasi altra proprietà distinta). Tutti i tuoi oggetti saranno quindi diversi, ma saranno ordinati per idoneità.

Answer 3

Nell'informatica classica, la struttura dati che si sta cercando è denominata Priority Queue.

Si dà il caso che da java 1.5, la libreria di classi java standard abbia un'implementazione: java.util.PriorityQueue.

Vorrei usarlo.

Answer 4

Se si desidera utilizzare un normale TreeMap, è possibile effettuare il wrapper del valore di archiviazione anziché i valori stessi. Questi wrapper quindi memorizzerebbero più con la stessa chiave.

Altrimenti è possibile utilizzare una sorta di struttura di elenco ordinata, basata su un albero di ricerca binario. Ne ho scritto uno qualche tempo fa, che è disponibile qui: http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/ ma sono sicuro che esistono più implementazioni standard. Il vantaggio di questo tipo di struttura è che il metodo contains(Object) viene eseguito in tempo logaritmico anziché in tempo lineare.