Co to jest dobry zbiór danych do reprezentowania wyścigów konnych?

Mam obiekt kursu wyścigowego, który jest ArrayList, który przyjmuje obiekty Horse. Wybrałem ArrayList, ponieważ jest łatwy w implementacji. Jednak wadą korzystania z ArrayList jest to, że nie mogę łatwo śledzić pozycji każdego konia bez przechodzenia kosztownych iteracji przez kolekcję. Na przykład, jeśli chcę znaleźć 2 konie, które znajdują się w odległości X od siebie, musiałbym iterować przez n^2 razy.Co to jest dobry zbiór danych do reprezentowania wyścigów konnych?

Czy istnieje lepsza strategia, aby to zrobić?

EDYCJA: Wiele próśb o szczegóły dotyczące mojego modelu wyścigowego, więc opiszę tutaj.

Model jest aktualizowany w każdej iteracji. Dlatego każdy koń ma swoją własną prędkość, przyspieszenie, przebytą odległość itd., A każda iteracja poprzez kolekcję aktualizuje te wartości. Istnieje wymóg, aby koń znajdujący się w pobliżu innego pojazdu zwolnił, co planuję zrobić, porównując wartości "przebytej odległości".

Źródło

2016-02-25 Evil Washing Machine

Możesz znaleźć takie pary koni, sortując ich pozycje i iterując, czyli 'O (n log n)'. –

być specyficzne: 1. Czy trzeba kwerendy i zmienić wartości losowo? lub 2. Czy (wielokrotnie) {aktualizuje wartości, a następnie wykonuje zapytania}? case 1. -> tree with remove and re-insert, case 2. -> array: repeat {zaktualizuj wartości, sortuj, wykonaj kwerendy} – BeyelerStudios

jest również trzeci przypadek: czy wartości (tj. pozycje wyścigu) mogą być losowe? czy mogą poruszać się tylko w górę iw dół? w tym trzecim przypadku potrzebujesz listy skanowania (która jest posortowaną tablicą), a przesuwanie w górę lub w dół jest równe zamianie pozycji w tablicy. – BeyelerStudios

Przypuszczam, że możesz dodawać obiekty Horse do kolekcji TreeSet. Powinieneś zaimplementować porównywalny interfejs w klasie Horse i zastąpić metodę compareTo(), sortując konie na odległość. Następnie możesz użyć określonych operacji na drzewieSet, takich jak "higher()", które zwrócą pierwszego konia, który jest uruchamiany więcej niż dany, itp. Możesz przeczytać więcej o tej kolekcji here. Również wszystkie operacje są O (lgN) według złożoności czasowej.

Źródło

2016-02-25 10:16:54

Ograniczeniem jest tutaj, że TreeSet nie automatycznie ponownie sortuje się, jeśli właściwości wartości, które wpływają na kolejność sortowania, są zmieniane po wstawieniu. –

Oczywiście, ale nie jestem do końca pewien, co to jest. Ale masz rację. Ale obiekt można usunąć i dodać ponownie w czasie O (lng). –

Ale TreeSet nie zezwala na duplikaty. W ten sposób możesz stracić konie z tej samej odległości – Eva

Jeśli utrzymujesz posortowaną listę na aktualizacjach pozycji konia, możesz określić wszystkie pary koni Odległość X w jednym skanie, czas N (kompromis polega na utrzymywaniu listy posortowanej, log (n) na aktualizację).

Jeśli zamiast tego chcesz, aby wszystkie konie X były oddalone od danego konia H. Możesz również zachować mapę haszującą konia na indeks tablicy i potencjalnie unikać iteracji całej tablicy.

Źródło

2016-02-25 10:27:59 Alireza

Co to jest dobry zbiór danych do reprezentowania wyścigów konnych?

Odpowiedz

Powiązane problemy