9
następującą funkcją:Jak mogę poprawić złożoność funkcji, która sortuje listę dla każdego punktu na niej?
sortByDist :: (Ord a, Floating a, RealFrac a) => [V2 a] -> Map (V2 a) [V2 a]
sortByDist graph = Map.fromList $ map sort graph where
sort point = (point, sortBy (comparing (distance point)) graph)
odwzorowuje każdy punkt P na liście do wykazu uporządkowanej według odległości P. Tak więc, na przykład, sortByDist [a, b, c, d] Map.! b lista [b, a, c, d] jeśli a jest najbliższym punktem b, c jest drugim najbliższym, d jest trzecim.
Ponieważ wykonuje sortowanie n * log n dla każdego elementu, złożoność jest n^2 * log n. Zgadza się to z punktami odniesienia wymaganymi do posortowania listy N punktów:
points time
200 0m0.086s
400 0m0.389s
600 0m0.980s
800 0m1.838s
1000 0m2.994s
1200 0m4.350s
1400 0m6.477s
1600 0m8.726s
3200 0m39.216s
Ile można poprawić teoretycznie? Czy można to obniżyć do N * log N?
Wygląda na to, że może się przydać jakaś odmiana quadtree. – luqui
Wydaje mi się "oczywiste", że nie można zejść poniżej "N^2" z tym formatem wyjściowym - jest to jego rozmiar, i mało prawdopodobne jest, aby mieć niezawodne udostępnianie. Nie, żebym wiedział, jak to zrobić. –
Czy na pewno nie można rzetelnie udostępniać treści? Ponieważ każdy element wyjścia jest posortowaną reprezentacją tego samego wykresu, przypuszczam, że jest w nim znaczna ilość zduplikowanych informacji. – MaiaVictor