Che cos'è una buona raccolta di dati per rappresentare una corsa di cavalli?

Question

Ho un oggetto del percorso di gara che è un oggetto ArrayList che contiene oggetti Horse. Ho scelto ArrayList perché è facile da implementare. Tuttavia, lo svantaggio di usare un ArrayList è che non posso facilmente tenere traccia delle posizioni di ogni cavallo senza andare ripetutamente in giro attraverso la collezione. Ad esempio, se voglio trovare 2 cavalli che si trovano entro una distanza X di distanza l'uno dall'altro, dovrei ripetere iterando attraverso n^2 volte.

Esiste una strategia migliore per farlo?

MODIFICA: Molte richieste per essere specifiche sul mio modello di gara, quindi elaborerò qui.

Il modello viene aggiornato ogni iterazione. Quindi ogni cavallo ha la sua velocità, accelerazione, distanza percorsa, ecc. E ogni iterazione attraverso la raccolta aggiorna questi valori. È necessario che, se un cavallo è vicino a un altro, esso rallenti, cosa che ho intenzione di fare confrontando i valori della distanza percorsa.

Answer 1

Suppongo che si possano aggiungere oggetti Horse alla raccolta TreeSet. Dovresti implementare un'interfaccia comparabile nella classe Horse e sovrascrivere il metodo compareTo(), quindi ordinare i cavalli per distanza. Quindi puoi usare operazioni specifiche su treeSet come "higher()" che restituirà il primo cavallo che viene eseguito più di uno dato, ecc. Puoi leggere di più su questa collezione here. Inoltre tutte le operazioni sono O (lgN) per complessità temporale.

Answer 2

Se si mantiene un elenco ordinato sugli aggiornamenti della posizione del cavallo, è possibile determinare tutte le coppie di cavalli X distanti tra loro in una scansione, N ora (bilanciamento mantenendo la lista ordinata, log (n) per aggiornamento).

Se si desidera che tutti i cavalli siano a distanza di X da un dato cavallo H. È inoltre possibile mantenere una mappa hash di cavallo all'indice di array e potenzialmente evitare di ripetere l'intero array.