Nehmen wir an, ich habe 1 Million willkürlich geformte, willkürlich orientierte N-dimensionale Ellipsoide, die zufällig durch den N-dimensionalen Raum verteilt sind. Bei einer Untermenge von Ellipsoiden möchte ich "schnell" die Menge aller Ellipsoide bestimmen, die die Ellipsoide aus der ersten Menge schneiden.
Dafür muss es einen Algorithmus geben. Was ist es? Was ist es "O" Komplexität?
Die "O" -Komplexität leidet unter dem Fluch der Dimensionalität , wenn Sie N-dimensionale Daten zulassen. (Siehe diesen Wikipedia-Artikel für mehr darüber). Ich empfehle, aus der Physiksimulation zu leihen und dieses Problem in eine "breite Phase" und eine enge Phase zu unterteilen:
Die enge Phase ist ein einfaches Berechnungsgeometrieproblem beim Testen auf einen Schnittpunkt zwischen beliebigen Ellipsen. Für die breite Phase sollten Sie eine räumliche Struktur wie einen räumlichen Hash, einen räumlichen Baum (R-Baum, Kd-Baum, X-Baum, UB-Baum usw.) oder eine gegebene Ad-hoc-Struktur verwenden einige spezielle Eigenschaften der Daten, die Sie laden (z. B. ein unausgeglichener Baum oder Hash).
Die aktuelle populäre Methode ist ein Kd-Baum. Es gibt eine Menge Dokumentation und bereits codierte Versionen des Kd-Baumes, die leicht konfigurierbar sind, daher empfehle ich Ihnen, online zu schauen. (Google ist Ihr Freund in diesem Fall.) Der Vorteil der Verwendung der meisten Baumstrukturen ist, dass wenn Sie nach Kreuzungen mit relativ kompakten suchen, Sie nur einmal durch den Baum suchen und die Schnittpunkte finden können, ohne mehrere Baumdurchquerungen durchführen zu müssen . Dies hilft bei Cache-Zugriffsmustern (sei es vom Hauptspeicher oder von der Festplatte). Der gleiche Algorithmus kann unterschiedliche Gliederungsabfragen handhaben. Es ist jedoch wahrscheinlich, dass Sie Arbeiten ausführen, die von den Eigenschaften der kompakten Abfragesätze profitieren würden.
Ein Kd-Baum wird Ihre Probleme nicht für alle Ellipsoide beheben - zum Beispiel, wenn Sie ein Ellipsoid der Dimension N haben, dessen primäre Achse von (0, 0, 0, 0, ...) bis (1 , 1, 1, 1, ...), aber mit kleinen oder unbedeutenden sekundären Achsen (und von nun an nicht mehr viel) wird immer noch ein Knoten sein müssen, der [0,1] in allen N Dimensionen abdeckt. Wenn Ihre Ellipsoide in [0,1] ^ n fallen, dann wird jedes Ellipsoid auf einen Schnitt mit dem oben erwähnten unbequemen Ellipsoid prüfen. Mit realen Daten (und sogar am synthetischsten, wenn man nicht wirklich versucht, Kd-Bäume langsam zu machen) sollte der Kd-Tree-Ansatz ein Gewinn sein.
Wenn Sie erwarten, dass der Kd-Baum ein Erfolg für tausenddimensionale Ellipsoide ist, sind Sie wahrscheinlich besser mit einer Brute-Force-Suche. (Der oben erwähnte Fluch der Dimensionalität.) Allerdings ...
Eine Million Einträge ist nicht schlecht, wenn Sie eine optimierte Implementierung haben, aber wenn Sie viele Abfragen (Millionen) durchführen, wird es langsam (in der Größenordnung von 10 Sekunden oder schlechter). Ich habe jedoch einige erstaunliche Zahlen aus gut optimiertem vektorisiertem Code gesehen. (Sogar einige Produkte wurden mit dieser Strategie ausgeliefert.) Mit der richtigen Cache-Kohärenz würde Brute-Forcening höchstens Millisekunden benötigen. Dies bedeutet entweder ASM oder Vektor-Intrinsics in C / C ++ - nicht sicher, in welcher Sprache Sie arbeiten.
Für die meisten Daten sollte die O-Komplexität (abgesehen vom Fluch der Dimensionalität) etwa amortisierten O (m log n) für Abfragen sein (sobald der Baum erstellt wurde), wobei m die Anzahl der Ellipsen im Abfragesatz ist und n der Anzahl der Ellipsen im Datensatz. Die Daten selbst sollten nicht schlechter als O (n log n) sein. Multiplizieren Sie alles mit Exp (d), wobei d die Dimension ist - das ist die Art, wie es mit dieser Art von Ding geht.
Tags und Links algorithm geometry complexity-theory computational-geometry