nicht angemeldet
Hallo Markus**,
Fakt ist, dass es offenbar ein bißchen schneller ist, aber im Großen und Ganzen konnte ich die Verarbeitungszeit um 1/3 von 15 auf 10 sek. und nicht auf ein drittel reduzieren.
Die 1/3 bezogen sich nicht auf die Laufzeit, sondern auf das nötige Verhältnis von Gesammtseitenlänge zu Umgebungsseitenlänge, damit der Algorithmus besser ist.
Um den Bruchteil q der Laufzeit zu erreichen, muss eine engere Bedingung gelten:
8*n²*d²/s² = q*(n² - n)
8*n*d²/s² = q*(n - 1)
d²/s² = q/8 - q/(8*n)
Für "große" n gilt dann:
d²/s² ~= q/8
Im Fall von 2/3 müsste d/s ~= (2/(3*8))^1/2 = 1/12 ~= 0.083
Wäre bei Deinem Abstand von 20 also eine Seitenlänge von 240.
Kommt das bei Deinen Daten hin? Wäre eher überraschend, wenn das so gut stimmen würde ;-)
Allerdings habe ich noch einen ganz anderen Lösungsansatz verfolgt, der ein gutes Resultat erzielt. Und zwar habe ich für jede Zufallskoordinate (5000stk) auf meiner Testmatrix von 10000x10000 Punkten eine Art Matrize erstellt, die ich absolut simpel ohne großen Aufwand vergleichen kann. Damit komm ich auf durchaus aktzeptable Resultate, <= 1 sekunde.
Ich verstehe ehrlich gesagt nicht, was Du da jetzt tust.
Was ich mir vorstellen könnte, ist, dass die Testmatrix geordnet ist, dann kann man die Umgebung zu einem Punkt ja sehr schnell bestimmen, weil man nicht mit jedem Punkt vergleichen muss. Theoretisch sollte man aber ja schon verloren haben, wenn man diese Matrix überhaupt aufbaut.
Mir ist übrigens noch folgendes aufgefallen:
Wenn man annimmt, dass die Anzahl der Punkte im Umkreis konstant ist, gilt:
c = n/(s/d)²
(s/d)²=n/c
Damit ergibt sich für die Komplexität:
8*n²/(s/d)² - n = 8*n²*c/n - n = 8*c*n - n
Damit wäre der Algorithmus sogar linear in der Anzahl der Punkte bzw der Fläche des betrachteten Gebiets. Zumindest asymptotisch geht es also gar nicht mehr besser. (Da das gesuchte Ergebnis schon lineare Größe hat, kann der Algorithmus auch nicht schneller sein, da er schon für die Ausgabe diese Zeit benötigt).
Vergrößert man dagegen c (also im Prinzip die "Auflösung" der Daten), hat man, da n natürlich mit c wächst, wieder quadratische Komplexität.
Für die Praxis sagt das aber natürlich immer noch relativ wenig, vor allem, wenn man noch recht kleine Zahlen hat. Und 5000 Datensätze ist ja im Prinzip noch relativ wenig.
Grüße
Daniel