Sortieralgorithmus mit geeignetem Container
-
Hallo,
ich stehe vor folgender Problemstellung:
In einem Behälter befinden sich viele Teilchen (z.B. 100000) die umher schwirren. Der Algorithmus erfordert dass die Teilchen jeweils nur um die kleinste Kollisionszeit weiterbewegt werden.
Aufgrund der vielen Teilchen im System dauert die Kollisionszeitberechnung sehr lange. Um den Algorithmus zu beschleunigen sollen deshalb die kleinsten z.B. 100 Kollisionszeiten mit den jeweiligen Pointern auf die kollidierenden Teilchen (hierbei handelt es sich um Objekte einer Klasse) gespeichert werden.Z.B: Es werden 100000 Kollisionszeiten t berechnet. Davon sollen die 100 kleinsten t sortiert gespeichert werden, um sie der Reihe nach (beginnend mit der kleinsten Zeit) wieder auslesen zu können.
t1 (ptrTeilchen_x, ptrTeilchen_h)
t2 (ptrTeilchen_b, ptrTeilchen_n)
t3 (ptrTeilchen_h, ptrTeilchen_z)
t4 (ptrTeilchen_j, ptrTeilchen_d)
....
t100 (ptrTeilchen_r, ptrTeilchen_t)mit t1 < t2 < t3 < t4 < ... < t100 (< als alle anderen Kollisionszeiten)
Mit welchem Container kann ich am schnellsten die 100 kleinsten Zeiten ermitteln und sortieren (speichern, umspeichern, damit die Reihenfolge stimmt; größere Zeiten verwerfen und kleinere Zeiten, wenn möglich an der richtigen Stelle zwischen 2 Zeiten einfügen) und wie handhabe ich dabei die Pointer, damit diese nach dem Sortieren noch immer mit der richtigen Zeit korrelieren?
Ginge dies mit einer List List <*ptrTeilchen> <float> ? Toll wäre es wenn Ihr mir eine Vorgehensweise skizzieren könntet.
Vielen Dank!
-
Das klingt nach einem Fall für std::multimap. Das ist ein sortierter(!) Container, der einen Schlüssel (deine Kollisionszeit) mit einem Wert (deine Pointer) verknüpft. Du würdest die Kollisionszeiten berechnen und gleich zusammen mit dem Pointerpaar in der Map speichern. Beim abspeichern werden diese automatisch an der passenden Stelle eingefügt. Wenn du alle Zeiten berechnet hast, kannst du ganz einfach auf die 100 ersten Elemente zugreifen 8welche zu den 100 kleinsten Schlüsseln gehören) und dir deren Werte (die Pointer) geben lassen.
Das Abspeichern der Elemente geht logarithmisch mit der Containergröße, der Zugriff ebenfalls. Das ist log(N) für den Zugriff auf den vollen Container, plus etwas das kleiner ist als log(N) für das Einsortieren, also insgesamt Komplexitätsklasse log(N). Die studierten Informatiker mögen mich korrigieren, wenn ich dies gerade falsch mache.
Erst in einem vector oder einer list Abspeichern und dann Sortieren braucht mindestens schonmal N*log(N) für das Sortieren. Und bei N=100.000 mögen die Konstanten noch so groß sein, da wirst du mit Komplexitätsklasse log(N) auf jeden Fall schneller sein.
-
Danke für die rasche Antwort.
-
rickie schrieb:
Aufgrund der vielen Teilchen im System dauert die Kollisionszeitberechnung sehr lange.
Wie wird die denn überhaupt berechnet? ...nur mal so aus Neugier gefragt.
-
Die Berechnung erfolgt nach der Formel (30) auf der Seite 102 des Papers
-
Aufgrund der vielen Teilchen im System dauert die Kollisionszeitberechnung sehr lange.
Schon mal ueber Quadtree oder Octree nachgedacht?
-
rickie schrieb:
Die Berechnung erfolgt nach der Formel (30) auf der Seite 102 des Papers
Heheh. So meinte ich das eigentlich nicht. Dass es für jedes Paar von Partikeln bei konstanter Geschwindigkeit und Kugelform auf eine quadratische Gleichunge hinausläuft, wusste ich. Ich habe mich nur gefragt, ob es eine intelligente Datenstruktur für solche Fälle gibt, die die zahl der nötigen Anwendungen von "Formel 30" stark reduzieren kann. Ich zitiere:
For each particle tje smallest collusion time is determined by scanning all relevant collision parters for a possible collision.
Aber wie es aussieht, werden dazu "neighbour lists" erzeugt. Von "Zellen" ist auch die Rede. Aber das kann ich beim Überfliegen nicht auf die Schnelle nachvollziehen. Müsste ich mehr Zeit investieren.
-
Genau. Der Behälter in dem sich die Teilchen befinden wird in würfelförmige Zellen unterteilt. Die Anzahl der möglichen Kollisionspartner wird schon vor der Berechnung der Kollisionszeit reduziert, indem nur die Interaktion mit Teilchen in den Nachbarzellen betrachtet wird (neighbour cell list Konzept). Anschließend werden alle Teilchen um die kleinste Kollisionszeit weiterbewegt und die Kollision zwischen den Kollisionspartnern wird durchgeführt (die neuen Geschwindigkeiten der beiden Teilchen werden berechnet). Dann wird wieder die kleinste Kollisionszeit ermittelt. usw.
Um nicht ständig die Kollisionszeit (was sehr viel Resourcen benötigt) berechnen zu müssen, war ich auf der Suche nach einer Möglichkeit (geeignetem Container) um die kleinsten z.B. 100 Kollisionszeiten während der Berechnung geordnet (sortiert nach der Zeitdauer) mit den Pointern auf die jeweiligen Kollisionspartner speichern zu können. Ich wollte den Container auslesen und die Teilchen weiterbewegen, bis er leer ist und erst dann die neuen Kollisionszeiten wieder berechnen.
Ich habe mir das Konzept von map bzw. multimap durchgelesen und es klingt sehr geeignet für meinen Algorithmus: Mit dieser Containerform kann ich leicht sämtliche Zeiten speichern, sortieren und danach die ersten z.B 100 Zeiten auslesen. Auch kann ich mit map leicht einzelne Einträge wieder löschen, was notwendig ist wenn z.B. zwei unterschiedliche Kollisionszeiten für dasselbe Teilchen vorkommen. In diesem Fall ist der Eintrag mit der größeren Kollisionszeit zu löschen. Ebenso können leicht neue Kollisionszeiten richtig platziert hinzugefügt werden.
Vielen Dank für all die guten Vorschläge! Ihr habt mir sehr geholfen!
