Załóżmy, że mam 1 milion dowolnie ukształtowanych, arbitralnie zorientowanych N-wymiarowych elipsoid, rozrzuconych losowo w przestrzeni N-wymiarowej. Biorąc pod uwagę podzbiór elipsoid, chcę "szybko" określić zestaw wszystkich elipsoid, które przecinają elipsoidy z pierwszego zestawu.Algorytm szybkiego przecięcia elipsoidalnego (s)
Musi być algorytm do tego. Co to jest? Jaka jest złożoność "O"?
"O" złożoność cierpi z powodu przekleństwa wymiarowego , jeśli pozwalasz na N-wymiarowe dane. (Aby uzyskać więcej informacji, patrz this wikipedia article). I zalecane zaciągania z symulacji fizyki i podzielenie tego problemu w „fazie” szerokiego i wąskiego fazami
Faza wąska to prosty problem z geometrią obliczeniową polegającą na testowaniu przecięcia dowolnych elips. Dla szerokiej fazy będziesz chciał użyć struktury przestrzennej, takiej jak spacja przestrzenna, drzewo przestrzenne (drzewo R, drzewo Kd, drzewo X, drzewo UB, itp.) Lub struktura ad-hoc niektóre specjalne właściwości ładowanych danych (np. niewyważone drzewo lub hash).
Obecną popularną metodą jest drzewo Kd. Istnieje wiele dokumentacji i już zakodowanych wersji drzewa Kd, które można łatwo konfigurować, więc polecam przeglądać online. Zaletą korzystania z większości struktur drzewiastych jest to, że jeśli zestaw, dla którego szukasz skrzyżowań jest stosunkowo niewielki, możesz przeszukiwać drzewo tylko raz i znaleźć skrzyżowania bez konieczności wykonywania wielu przewijań drzewa . Pomoże to z wzorcami dostępu do pamięci podręcznej (zarówno z pamięci głównej, jak iz dysku). Ten sam algorytm może obsłużyć różne kwerendy. Prawdopodobnie wykonujesz pracę, która byłaby bardzo korzystna dzięki właściwościom kompaktowych zestawów zapytań.
Drzewo Kd nie rozwiąże problemów dla wszystkich elipsoid - na przykład, jeśli masz elipsoidę o wymiarze N, której główna oś jest od (0, 0, 0, 0, ...) do (1, 1, 1, 1, ...), ale z małymi lub nieistotnymi osiami pomocniczymi (i dalej nie przecinają się zbytnio) nadal będzie musiał być węzłem obejmującym [0,1] we wszystkich wymiarach N. Jeśli twoje elipsoidy mieszczą się w [0,1]^n, to każda elipsoida przetestuje przecięcie ze wspomnianą niewygodną elipsoidą. Jednak w przypadku danych rzeczywistych (a nawet najbardziej syntetycznych, chyba że naprawdę starasz się spowolnić drzewa Kd), podejście Kd-tree powinno być wygraną.
Jeśli spodziewasz się, że drzewo Kd będzie sukcesem dla elipsoid o wymiarze tysiąca, prawdopodobnie lepiej Ci będzie, gdy przeszukasz brutalną siłę. (Wspomniana klątwa wymiarowa.) Jednak ...
Milion wpisów nie jest tak źle, jeśli masz zoptymalizowaną implementację, ale jeśli robisz dużo zapytań (miliony), to będzie powolny (rzędu 10 sekund lub gorzej). Widziałem jednak niesamowite liczby pochodzące z dobrze zoptymalizowanego wektoryzowanego kodu. (Nawet przy użyciu niektórych produktów przy użyciu tej strategii.) Przy odpowiedniej spójności pamięci podręcznej wymuszanie wymuszania zajmuje maksymalnie milisekundy. Oznacza to albo ASM, albo wektor wewnętrzny w C/C++ - nie wiesz, w którym języku pracujesz.
Dla większości danych złożoność O (bez względu na przekleństwo wymiarowe) powinna być o zamortyzowanym O (m log n) dla zapytań (po zbudowaniu drzewa) gdzie m jest liczbą elips w zestawie zapytań, a n jest liczbą elips w zbiorze danych.Budowanie samych danych nie powinno być gorsze od O (n log n). Pomnóż wszystko przez Exp (d), gdzie d jest wymiarem - tak to się dzieje z takimi rzeczami.
Fascynujące! Dziękuję za wejście. Tak więc, moim przesłaniem jest to, że jeśli mogę przyjąć pewne założenia dotyczące maksymalnego rozmiaru elipsoid, mogę użyć drzewa Kd do szybkiego zmniejszenia przestrzeni do rozmiaru, który jest łatwiejszy w zarządzaniu w przypadku problemu z geometrią obliczeniową brutalnej siły . – JnBrymn
Zasadniczo tak. A jeśli naprawdę potrzebujesz z powodu ograniczeń przestrzeni, możesz to zrobić z dysku, ponieważ przechodzenie drzewa jest znacznie mniej zależne od przepustowości niż brute force. Ale dobrze zoptymalizowane rozwiązanie typu "brute force" (jeśli sprowadza się do niego z powodu wymagań, których tu nie znam) może nadal działać. W ciągu kilku milisekund na klatkę przesyłałem gry, które brutalnie wymuszały podobne problemy, ale to była bardzo ostrożna optymalizacja. – Kaganar
Jeśli nie chcesz używać wstępnie zwiniętej implementacji drzewa Kd, a zamiast tego wolisz używać własnej struktury, jeśli elipsoidy mają dość spójny rozmiar, przestrzenna struktura haszowania jest dużo łatwiejsza w implementacji i może mieć lepszą wydajność w zależności od samych danych. Kd-drzewa są generalnie bardziej agnostyczne dla danych, ale mają bardziej złożone operacje spowalniające je. Oba są bardzo wrażliwe na wymiar. – Kaganar
Dlaczego? Bez tego, to pachnie: "odrób moją pracę domową dla mnie". – spender
Czy możemy założyć, że twoje elipsoidy są przechowywane w jakiejś drzewiastej strukturze danych, takiej jak N-wymiarowy odpowiednik kwadratu? Jeśli nie, to jest to problem * O (MN) *, gdzie * M * jest wielkością podzbioru, a * N * jest rozmiarem zestawu. –
@spender - doskonale! Oznacza to, że odpowiedź będzie łatwa do zdobycia. Dlaczego tak jest, ponieważ chcę związać arbitralne rozkłady prawdopodobieństwa używając rodzin sfer. Ustalenie, która rodzina sfer nakłada się, pozwoli mi na dokonanie pierwszego cięcia przy rozwiązywaniu problemu uogólnionego prawdopodobieństwa. - nie, to nie jest zadanie domowe. – JnBrymn