Odpowiedni algorytm sortujący

Question

mam problem który wymaga szybkiego najlepiej wielowątkowego sortowania tablicy i nie wiem jaki algorytm będzie do tego optymalny ponieważ zupełnie nie zależy mi na czasie wykonywania w średnim czy najgorszym przypadku tylko w przypadku lekkiego wymieszania gdzie liczby są prawie na swoim miejscu zależy mi też na efektywności na dużych zbiorach powiedzmy 30 000 elementów

zastanawiam się nad "odd even sort" ale jako że słabo znam się na takich algorytmach to nie wiem czy w moim przypadku będzie blisko tego optymalnego

Comments

Prawdopodobnie najprościej będzie samemu popróbować wiele wariantów i wybrać ten który na Twoich konkretnie danych będzie najlepszy. (nie dodałeś też, o jakim typie danych mówisz i czy musi być stabilny)

Masz może przykład danych które chcesz posortować? Możesz pokazać przykład takiego lekkiego pomieszania?

---

ciężko podać przykład takiego lekkiego pomieszania ale mogę dokładnie wyjaśnić na czym polega problem

mianowicie robię prostą symulację fizyczną 2D w której jest bardzo wiele kulek i zamiast sprawdzać kolizję każda z każdą to zrobiłem optymalizację polegającą na tym że mamy oprócz tablicy samych kulek również tablice intów które są takimi kluczami do tablicy kulek znaczy że każdy int jest indeksem i odpowiada za jedną kulkę w tablicy kulek

zakładając że mamy posortowaną tablice intów pod względem tego jak bardzo na lewo jest lewa strona odpowiadającej mu kulki to wykonujemy następujący algorytm
iterujemy po tablicy intów i dla każdego inta bierzemy odpowiadającą kulkę powiedzmy A dla każdej takiej kulki A iterujemy po następnych posortowanych kulkach B sprawdzamy czy prawa strona A nie jest po lewo od lewej strony kulki B jeżeli tak to sprawdzamy dokładniej czy kolizja zachodzi (używając prawa pitagorasa i sprawdzając czy odległość od środków jest mniejsza niż suma promieni) jeżeli tak to obliczamy nowe prędkości bla bla bla natomiast w przeciwnym wypadku czyli gdy prawa strona kuli A jest po lewo od lewej strony kuli B to przerywamy tą pętle ponieważ dalsze sprawdzanie kolizji nie ma sensu gdyż jak mówiłem kulki są posortowane pod względem tego jak bardzo po lewo jest ich lewa strona a jeżeli już lewa strona jest za bardzo po prawo to w przypadku następnych kulek będzie tak samo dzięki temu obcinamy sprawdzanie prawie wszystkich kolizji

oczywiście sprawdzanie kolizji dla różnych kulek A robię na różnych wątkach aby to zoptymalizować równomiernie używając całego procesora

aby to działało muszę sortować te kulki to znaczy tablice intów co klatkę a gdy robię to sortowanie na jednym wątku to pozostałe wątki nic nie robią i zaczną działać dopiero po posortowaniu tablicy przez co w menadżerze zadań widzę że główny wątek jest używany na maksa a inne do połowy bo przez drugą połowę czasu czekają i symulacja działa na pół gwizdka

tablica jest prawie posortowana ponieważ po jednej klatce nie za wiele się może zmienić ale jednak się zmienia więc tablice trzeba posortować

---

A ok, czyli robisz uproszczony wariant https://en.wikipedia.org/wiki/Sweep_and_prune (czy dobrze interpretuję z tego co napisałeś, że wszystkie kulki mają u Ciebie równy promień?).

Na pewno nie możesz pokazać kodu? Albo chociaż części dotyczącej sortowania (i kolizji)?

Mierzyłeś, ile to sortowanie trwa (lub ogólnie profilowałeś)? Bo na intuicję 30k rzeczy powinno się sortować w znacznie mniej niż 1ms, więc nie powinno dominować czasu klatki.

Jakby co, istnieją jeszcze potężniejsze sposoby optymalizowania kolizji, jest lista np na wiki https://en.wikipedia.org/wiki/Collision_detection#Broad_phase ;

Jednym z najpopularniejszych jest pewnie quadtree, opisany w wielu wielu miejscach, np tutaj: https://stackoverflow.com/a/48355534 https://stackoverflow.com/a/48330314 (ale jeśli Twoja symulacja ma równie równo obiekty, to możesz sobie pozwolić na znacznie prostszą równą siatkę 2D o jakiejś rozdzielczości którą sobie wybierzesz, zamiast pełnego quadtree).

---

kulki nie mają równych promieni i używam póki co jakiegoś domyślnego algorytmu sortowania który jest w c# w System.Collections.Generic w taki sposób
sortedBalls.Sort(Sort);
a to Sort w środku to reguła sortowania która wygląda tak

int Sort(int b1, int b2)
{
    if (balls[b1].position.X - balls[b1].radius - (balls[b2].position.X - balls[b2].radius) < 0)
        return -1;
    else if (balls[b1].position.X - balls[b1].radius - (balls[b2].position.X - balls[b2].radius) > 0)
        return 1;
    else
        return 0;
}

nie jestem pewien jaki algorytm jest tutaj używany ale na pewno jest to wykonywane na jednym wątku

napisałem teraz na szybko sprawdzanie czasu w kilku miejscach i jestem w szoku ponieważ sortowanie zajmuje aż 6 ms a cała reszta czyli poruszanie kulek i sprawdzanie kolizji w zależności od średnicy kulek bo gdy mają większą średnice to więcej jest kulek które po takim zrzutowaniu na 1D na siebie nachodzą od 4 do 10 ms więc to sortowanie musi być bardzo bardzo wolne być może dzieje się tak przez skomplikowaną regułę sortowania tak czy siak dużo zyskam gdy sortowanie będzie kilka razy szybsze

poprawiłem kod reguły sortowania ale skróciło to czas z 6 do 5 ms czyli wciąż bardzo długo

 

int Sort(int b1, int b2)
{
    if (balls[b1].position.X - balls[b1].radius < balls[b2].position.X - balls[b2].radius)
        return -1;
    else
        return 1;
}

 

---

nie jestem pewien jaki algorytm jest tutaj używany ale na pewno jest to wykonywane na jednym wątku

Wciąż wydaje mi się że akurat wielowątkowość jest tutaj mniej ważna, a lepiej by przemyśleć algorytmy i struktury (jak np partitioning z wcześniejszego linku do wikipedii; siatka 2d lub bardziej wyrafinowany quadtree ma potencjalnie mniejszą złożoność czasową obsługi niż sortowanie (i są warianty gdzie w ogóle jakąkolwiek pracę robisz tylko gdy obiekt przekroczy granicę komórek), a przy okazji pozwoli Ci też ograniczyć samo sprawdzanie kolizji do elementów bliskich w obu wymiarach, a nie tylko w jednym).

Wracając do sortowania, osobiście wątpię że jakikolwiek ręcznie napisany algorytm w C# będzie znacznie szybszy od wbudowanego, choćby dlatego że w Twoim kodzie kompilator łatwo nie wyrzuci bounds checków.

A z drobnych poprawek, rozważ jeszcze sortowanie List<Ball> bezpośrednio zamiast List<int>, powinno być trochę szybsze.

---

dzięki za pomoc spróbuje zaimplementować inne sprawdzanie kolizji ale najpierw jednak spróbuje zrobić lepsze sortowanie
 

i dlaczego sortowanie od razu listy kuli ma być szybsze jeżeli są to całe obiekty które zawierają w sobie kilka rzeczy? chyba że podczas takiego sortowania pod maską przerzucały by się jedynie wskaźniki do tych kulek a ja jak debil sortuje jakąś inną listę intów i dokładam dodatkową warstwę która wszystko spowalnia

---

i dlaczego sortowanie od razu listy kuli ma być szybsze jeżeli są to całe obiekty które zawierają w sobie kilka rzeczy? chyba że podczas takiego sortowania pod maską przerzucały by się jedynie wskaźniki do tych kulek a ja jak debil sortuje jakąś inną listę intów i dokładam dodatkową warstwę która wszystko spowalnia

Znowu problem polega na tym, że nie pokazałeś kodu. Czy Twój Ball to class czy struct? Jeśli class, to z definicji każda referencja do obiektu to wskaźnik; taki `List<Ball>` to jest w środku tablica wskaźników, nie bezpośrednio tablica obiektów. Tak, sortowanie takiej listy to tylko sortowanie wskaźników.

---

(A właśnie, jak już o tym mówimy, to - nie wiem jakiego typu jest `ball.position`, ale jeśli to jakieś Twoje własne `class Position { double X; double Y; }`, to przy okazji możesz przemyśleć zamianę tego na `struct`. Ball już nie ofc.)

---

używam Vector2 z frameworka który jest strukturą więc tu jest ok

---

W każdym razie może się okazać że jeśli wyrzucisz List<int> również z samego szukania kolizji, to też przyśpieszy :)

Answer 1

Nikt ci nie powie jaki algorytm w twoich przypadku będzie optymalny, ale to brzmi jak sytuacja w której algorytm parzyste nie parzyste by się idealnie sprawdził.
Jako że masz wstępnie posortowane dane możesz też przetestować gnoma, sortowanie przez wstawianie i sortowanie przez podział naturalny. Prawdopodobnie któryś z tych algorytmów będzie bliski optymalnemu. Na 99% optymalny będzie jakiś algorytm kombinowany, ale żeby taki wybrać trzeba dokładniej znać problem.