Wann wechseln Sie von ungeordneten Listen zu sortierten Listen? [Optimierung

Question

Ich muss einen Algorithmus implementieren, um 3D -Volumina in Voxel zu zerlegen. Der Algorithmus beginnt zunächst, welche Scheitelpunkte auf jeder Seite des Schnittplans und in einem zweiten Schritt den Rand des Schneidplans durchqueren.

Dieser Prozess könnte durch die Nutzung der sortierten Liste optimiert werden. Das Identifizieren des Split -Punktes ist o log (n). Aber ich muss eine solche sortierte Liste pro Achse und diese für Scheitelpunkte und Kanten verwalten. Da dies von GPU verwendet werden soll, habe ich auch einige Einschränkungen für die Speicherverwaltung (dh CUDA). Aufdringliche Listen/Bäume und C werden auferlegt.

Mit einer vollständigen "Voxelisierung" erwarte ich mit ~ 4000 Punkten und 12000 Kanten. Glücklicherweise kann dies durch eine intelligentere Strategie optimiert werden, um verarbeitete Voxel loszuwerden und Restvolumina zu bestellen, um ihre Anzahl auf ein Minimum zu halten. In diesem Fall würde ich weniger als 100 Punkte und 300 Kanten erwarten. Dies macht den Prozess komplexer zu verwalten, könnte aber effizienter werden.

Die Frage ist daher, die Kriterien zu identifizieren, um festzustellen, wann der Nutzen einer sortierten Datenstruktur im Vergleich zu einfachen, intrusiven verknüpften Listen den Aufwand und die Komplexität wert ist.

Answer 1

Die Frage wird immer darauf zurückschlossen, welcher Bediener am häufigsten ist, zugreift oder hinzufügt. Wenn Sie eine nicht ordnungsgemäße Liste haben, dauert es keine Zeit, und der Zugriff auf bestimmte Elemente kostet zusätzliche Zeit. Wenn Sie eine sortierte Liste haben, benötigt das Hinzufügen mehr Zeit, aber der Zugriff ist schneller.

Die meisten Anwendungen geben die meiste Zeit damit, auf die Daten zugreifen, anstatt sie hinzuzufügen. Dies bedeutet, dass der (laufende) Zeitaufwand beim Erstellen einer sortierten Liste normalerweise ausgeglichen oder abgedeckt wird, wenn der Zeitpunkt beim Zugriff auf die Liste gespeichert wird. Wenn Ihre Daten viel Abwanderung haben (was nicht so klingt), ist die Aufrechterhaltung einer sortierten Liste nicht unbedingt ratsam, da Sie die Liste ständig als beträchtliche CPU -Kosten zurückgreifen.

Die Komplexität der Datenstrukturen ist nur dann wichtig, wenn sie kann nicht auf nützliche Weise sortiert werden. Wenn sie sortiert werden können, müssen Sie an der Heuristik von gehen

Anzahl der Zugriffe: Anzahl der Änderungen

Um festzustellen, ob die Sortierung eine gute Idee ist.

Answer 2

Chmike, das klingt wirklich nach der Art von Dingen, die Sie zuerst auf einfachere Weise tun möchten und sehen, wie es sich verhält. Jede Art von GPU -Voxelisierungsansatz ist für Systemdetails ziemlich zerbrechlich, sobald Sie zumindest in große Bände eingehen (was Sie nicht zu haben scheinen). In Ihren Schuhen möchte ich auf jeden Fall die unkomplizierte Implementierung zuerst haben, wenn auch aus keinem anderen Grund, um sich gegen ...

Answer 3

Nachdem ich alle Antworten in Betracht gezogen hatte, stellte ich fest, dass die spätere Methode zur Vermeidung doppelter Berechnung aufgrund der Aufrechterhaltung und Navigation in der Datenstruktur weniger effizient ist. Außerdem ist die anfängliche Methode unkompliziert, um mit einigen kleinen Kernelroutinen parallel zu parallelisieren und somit besser für die GPU -Implementierung geeignet zu sein.

Überprüfung meiner ersten Methode Ich fand auch signifikante Optimierungsmöglichkeiten, die die Volumenschnittmethode weit hinter sich lassen.

Da ich eine Antwort auswählen musste, entschied ich mich für Devinb, weil er die Frage beantwortete, aber Simons Kommentar, der von Tobias Warre -Kommentar unterstützt wurde, war für mich genauso wertvoll.

Vielen Dank an Sie alle, dass Sie mir geholfen haben, dieses Problem zu lösen. Stack Overflow ist ein beeindruckender Service.