>Mamy dużo piłek, coś jak te cząstki gazu, które są rozsypane w zadanym obszarze,
>każda ma swoją prędkość...
>I teraz zadanie: wyliczyć wszystkie najbliższe kolizje pomiędzy tym piłkami.
>Znaczy należy utworzyć: n/2 par + czas zderzenia (tego najbliższego).
>Tradycyjne podejście wymaga tu wyliczenia aż n^2/2 kolizji, co przekracza możliwości komputera, bo
>już dla n = 1 milion otrzymamy: milion^2 = 10^12,
>co daje czas obliczeń chyba kilka miesięcy, a może i lat.
>Zatem należy to zredukować do rozsądnych wielkości, np.:
> n*log(n) byłoby super w porównaniu do n^2: log(mln) * mln = 20 mln, czyli sekundy, zamiast lat!
>Ma ktoś pomysł jak to zrobić?

Ja nie miałem nigdy swojego pomysłu, ale przewinął mi się kiedyś przez oczy jakiś 'standardowy' algorytm dot. symulacji zderzeń cząstek i jestem pewien, że to nie ma nic wspólnego z sortowniem.

Może istnieja jakieś algorytmy zoptymalizowane do odnajdywania 1go zderzenia, ale ja zacząłbym od algorytmów symulujących zderzenia (bo tylko takie mi się gdzieś w pamięci przewijają). Nie skupiałbym się na tym jak połączyć cząstki ze sobą (tj jak przez nie 'przelecieć' by nie sprawdzać każdej z każdą), ale raczej na tym jak liczyć zderzenie -to ten problem zadecyduje o złożoności i to jest główna trudność w tym algorytmie!

To nie jest trywialny problem i nie mam ani czasu ani chęci tym się zajmować, ale wyciągając jakieś strzępy z otchłani pamięci rozważ to:
1. Zastanów się jaki jest model (czy cząstki są zamkniete w jakiejś klatce czy nie)
2. Zastanów się jakie masz podejście - czy algorym działa sekwencyjnie (przechodzi po jednostkach czasu - typowe podejście w symulacjach) czy próbuje liczyć czas na podstawie wektora prędkości i położenia (to raczej będzie miało większą złożoność niż kwadratowa, nie wiem nawet czy to się da policzyć inaczej niż sekwencyjnie, bo cząstki zmieniają kierunek po odbiciach i musisz cały czas przeliczać wszystkie bo przecież nie ta dla której liczysz właśnie 1sze zderzenie może się zderzyć z inną cząstką, która już wielokrotnie się zderzyła z innymi)
3. Jak dzielisz przestrzeń (na jakieś 'cele' czy jest ciągła - komputer w praktyce nie radzi sobie z czymś co może niedyskretną wartość)
4. Wg mnie nie powinineś się skupiać na obliczaniu oddziaływania pomiędzy pozostałymi cząstkami (bo wtedy algorytm o złożoności kwadratowej to optymizm - niektóre cząstki mogą się nigdy nie zderzyć, a inne mogą się zderzyć 1szy raz z cząstką, która już wielokrotnie się zderzyła) tylko na sprytnym podziale przzestrzenii i algorytmie sekwencyjnym.
5. Jeśli podzielisz przestrzeń to w algorytmie sekwencyjnym idziesz jednostka po jednoste czasu i zapamiętujesz zderzenia tak długo aż wszystkie cząstki się zderzą jeden raz (albo po pewnym czasie nie wyliczysz, że niektóre uciekły - jeśli przestrzeń nie jest zamknięta).
6. Przy jakimś sprytnym podziale przestrzenii być może w każdym kroku masz tylko do sprawdzenia sąsiednie 'cele' więc to jest stała liczba - algorytm O(N) x ileś jednostek czasu = O(N) ? (liczba jednostek czasu zależy od prędkości najwolniejszej cząstki, najszybszej cząstki i wielkości 'świata', w której się zderzają a nie od liczby cząstek)

Podejrzewam, że jeśli układ jest zamknięty i nie liczysz zderzeń ze ścianą to nie ma gwarancji, że skończysz kiedyś obliczenia (odnajdziesz momenty, w którym każda cząstka zderzy się 1szy raz - bo to może trwać w nieskończoność). Jeśli zadowala Cię zderzenie ze ścianą to myśle, że idąc tym tokiem rozumowania dojdziesz do algorytmu O(N).

Pozdrawiam
Paolo Monstro

Wyliczenie kolizji trwa niewiele.

Trudność symulacji dużej ilości cząstek polega na ciągłym sprawdzaniu kolizji,
a ponieważ każda może się zderzyć z każdą, wiec musisz to przeliczać:
n(n-1)/2, co jest rzędu n^2 - w każdym kroku!

zatem wiadomo że tego n^2 nie wyrobisz już nawet dla kilku tysięcy, bo tu otrzymasz już n = 10000 tysi, jako limit -> n^2 = miliard, co jest zbyt wielkie (pecet ma spi rzędu tylko GHz czyli miliard /s ), więc należy to inaczej robić.

I jest metoda jak to robić - liniowo!,
no ale na starcie - tylko raz, i tak potrzebuję wyliczyć te pary,
tj. najszybsze kolizje - potencjalne tylko bo po każdej kolizji to się i tak zmienia...

i wtedy to trzeba realizować po kolei: od najwcześniejszej, a potem kolejne -
dlatego to wiele wspólnego z sortowaniem!

momenty kolizji:
tk = 0.1ns, 1ns, 2.5ns, ... to jest zawsze na pewno posortowane.

Podział obszaru zmniejsza trochę: n^2/k, dla k - liczba działek...
co jest nadal kwadratowe... no, może dla k = n, byłoby to liniowe,
ale wtedy byłaby to sieczka, a nie symulacja:
uwzględnianie przejścia pomiędzy sektorami i... inne fikcyjne kłopoty,
których wyliczenie kosztowałoby... tyle samo co jazda z tym n^2.

>Wyliczenie kolizji trwa niewiele.
>Trudność symulacji dużej ilości cząstek polega na ciągłym sprawdzaniu kolizji,
>a ponieważ każda może się zderzyć z każdą, wiec musisz to przeliczać:
>n(n-1)/2, co jest rzędu n^2 - w każdym kroku!
Napisałem Ci powyżej - zmień podejście. Jeśli będziesz dla każdej kulki sprawdzał kolizje z pozostałymi to N^2 jest optymizmem nawet, bo możesz mieć pierwsze zderzenie z kulką, która się już zderzyła wielokrotnie, a to nawet pachnie rekurencją.

Pomyśl o tym tak jak napisałem, algorytmem sekwencyjnym w czasie i zamiast sprawdzać kolicje z każdą pozostałą kulką sprawdz dla każdej kulki czy jest coś w przestrzenii wokól niej, np. jak podzielisz przestrzeń na małe sześcianiki:
0. czas = 0
1. dla każdej kulki policz pozycję
2. dla każdej kulki sprawdź cele obok niej + celę, w której sama się znajduje ( w sumie jest tych cel/sześcianików 27 dokładnie)
3. jesli zderzenie zwieksz licznik zderzen dla kulek w zderzeniu, zapamietaj czas czy co tam chcesz zapamiętać
4. IF dla wszysktkich kulek licznik >= 1 THEN wyjdz
5. czas = czas + jednostka
6. goto 1.

to powyzej ma zlozonosc O(N). Jestem pewien, że taki algorym widziałem. Poszukaj w Internecie jeśli mi nie wierzysz.

Pozdrawiam
Paolo Monstro

>Napisałem Ci powyżej - zmień podejście. Jeśli będziesz dla każdej kulki sprawdzał kolizje z pozostałymi to N^2 jest optymizmem nawet, bo możesz mieć pierwsze zderzenie z kulką, która się już zderzyła wielokrotnie, a to nawet pachnie rekurencją.

Nie rozumiemy się.
Mi właśnie o to chodzi żeby zignorować wpływ kolizji... na dalsze kolizje.

Mamy wyliczyć jedynie czas tej pierwszej potencjalnej kolizje dla każdej,
czyli tak statycznie jakby:

bierzemy kulę nr 1 i sprawdzamy kiedy ona się zderzy z inną: z 2, z 3, ... z n-tą.
I otrzymujemy np. że ona zderzy się (jest na linii kolizji): z 5-tą, z 6-tą i ze 150-tą ale najprędzej z 6-tą,

co notujemy w postaci pary:

(1,6, czas=17ps);

następnie to samo dla 2-ej: ...

(2, 11, t=2ps)

itd. aż do wyczerpania kul !
........

Niekiedy wystąpią tu.. kłopoty, np.:

kula 7 zderza się też z 6, i prędzej niż 6 z 1, więc teraz 7 wygrywa:
(7, 6, t67);

zatem kula 1 straciła swoją parkę, więc musi być od nowa rozpatrywana...
(1, 150, t...)

.........
Finalnie z tego mamy otrzymać listę par:

(a, b, t_kolizji);

i to będzie dopiero punkt wyjścia do symulacji!

start: t = 0;

1. para z najbliższym czasem - to jest na pewno prawdziwa kolizja
2. zatem przesuwamy czas do momentu: t = t_first,
i rozliczamy tę kolizję, czyli modyfikujemy prędkości itd.
3. te dwie kule po zderzeniu muszą być od nowa przeliczone:
szukamy dla nich inne do pary...

4. i teraz jesteśmy znowu w 1.

i tak biegnie symulacja - nie potrzeba mi żadnych kroków: t + dt,
bo tu same kolizje dają postęp w czasie.

Proponuję otworzyć projekt np. w github lub innym publicznym, i wtedy się pobawimy.