Krautkanal.com

Veröffentlicht am 2016-04-23 21:20:28 in /prog/

/prog/ 8733: C#-Laufzeitoptimierung

adhiardana Avatar
adhiardana:#8733

Hallo /prog/
Dieser Bernd hier programmiert seit 5 Jahren in C#, das meiste habe ich mir selbst beigebracht, nie ein Informatikstudium besucht, sondern mich eher auf das Handwerk konzentriert. Ein Punkt mit dem ich mich nur sehr beiläufig befasst habe ist die Berechnung der Komplexität von einzelnen Anweisungen. Aktuell gehe ich es so an, dass ich mir ansehe was die Anweisung genau tut, welche Datenstrukturen verwendet werden und wie häufig sie iteriert werden müssen. Generell arbeite ich ohne UML-Diagramme und Unit-Tests, da es mir beim Programmieren hauptsächlich um den Spaß geht (wie ein Musiker der Freistil spielt)

Das Anwendungsbeispiel das ich hier habe beschäftigt sich mit dem Aufbau eines Stromnetz für ein Spiel, in dem es hauptsächlich um den Transport von Waren und der Produktion von Energie geht. Hierbei sieht meine die aktuelle Lösung vor dass jedes Modul (Gebäude, meist eine Fabrik) einen PowerGridConnector besitzt, in dem befinden sich Settings gespeichert was für eine Art von Connector er ist, über ein Bitfeld kann er sowohl Produzent, Batterie und Konsument sein. Er erschafft sich ein Powergrid (Ein Stromnetz das alle Teilnehmer verwaltet) und versucht es mit anderen zu verbinden.

Da sich andere Stromnetze um ein Netz herum befinden kann es zT einen sehr großen Aufwand bedeuten diese zu finden. Aktuell nutze ich dafür 3 verschachtelte For-Schleifen und rufe dazu auch noch die fragliche Funktion rekursiv auf. Klingt bereits nach einen kombinatorischen Albtraum.

Bei wenigen Netzen mit jeweils wenigen Teilnehmern die nah beieinander sind hat der Code wohl einen Optimalfall abgedeckt.
Falls sich der Spieler jedoch entschließen sollte ein einziges riesiges Powergrid mit tausenden von Teilnehmern über die ganze Karte verteil zu bauen wird es schwieriger.

Der Code für das Aufbrechen des Netzes ist nur kurz hingehackt worden um überhaupt was zu haben.

Wie könnte ich die Komplexität in den Griff bekommen oder überschätze ich das Problem?
Ist eine Anwendung von Quadtrees für die weitere Aufteilung der Netze in kleinere die einzige Möglichkeit die ich habe?

http://pastebin.com/vsnKwZxf

cat_audi Avatar
cat_audi:#8743

Hä?

Wer definiert die Stromleitungen? Also welche Produzenten, Batterien und Konsumenten verbunden sind?

hoangloi Avatar
hoangloi:#8745

>>8743
Strom soll über die Luft übertragen werden, Batterien und Produzenten sollen dabei eigenständig ein Netz aufbauen und ihre Energie an Konsumenten und Batterien weiterleiten.

Im Grunde hat jeder Produzent eine Reichweite, es kann dabei aber auch vorkommen, dass ein Produzent der eine größere Reichweite hat weiter von einem Konsumenten weg ist als ein anderer und wegen seiner Reichweite zum Netz dazu gehört.

Da hier viel mit Entfernungen im 3D-Raum gearbeitet wird versuche ich alles im quadrierten Bereich zu berechnen um die Wurzeln zu sparen. Bringt aber nichts in Zeile 114, dort komme ich wohl nicht um die 3. Schleife rum.

Später sollen auch noch bewegliche Konsumenten dazu kommen.

Eine "Stromleitung" ist also nur eine Referenz die in dem Netz gesetzt ist wenn der Produzent/Verbraucher in Reichweite ist.

Shriiiiimp Avatar
Shriiiiimp:#8746

>>8745
>Da hier viel mit Entfernungen im 3D-Raum gearbeitet wird versuche ich alles im quadrierten Bereich zu berechnen um die Wurzeln zu sparen.
Würde mich wundern, wenn das was bringen würde. Du hast einen zusätzlichen function call, und das Ergebnis wird so oder so an die andere Funktion übergeben, die die Wurzelberechnung übernimmt. Das kommt jetzt auf den Compiler drauf an, ob das jetzt irgendwie über lookup-tables geregelt wird, oder trotzdem ganz normal berechnet wird. Würde ignorieren und mich auf das Hauptproblem konzentrieren, und das sind deine 3 verschachtelten foreach-Schleifen. Das geht so überhaupt nicht, deine Komplexität ist viel zu hoch.

Du könntest bei CheckGridFusion() deinen Grids noch irgendwelche Koordinaten mitgeben, um gleich mal zu schauen, ob sie überhaupt genauer überprüft werden sollen. z.B. 2x XYZ Koordinaten (2x wg. Radius), und dann schauen, ob die Koordinaten vom überprüfenden Element irgendwo dazwischen liegen. Könnte u.U. was bringen. So müsstest du nicht jedes einzelne Element durchlaufen. Könnte man dann noch weiter optimieren, um beispielsweise die Liste der Grids über die Koordinaten durch zu sortieren und dann über divide-and-conquer schnell mögliche Kandidaten rauszufiltern.

Hab mir jetzt den Kot nicht genauer durchgelesen und bin auch etwas müde, aber was mir gleich aufgefallen ist: Wenn du schon eine Liste für jeden verschiedenen Typen hast, dann nutze sie auch. Ich sehe du überprüfst oft, ob ein Objekt zu einem bestimmten Typen gehört. Würde ich lieber vermeiden, eine zweite Schleife hinzufügen und die zwei getrennten Listen durchlaufen.

Auch vielleicht das mal durchlesen:
http://www.performancesimulations.com/wp/how-to-get-big-speed-increases-in-unitys-physics-or-any-math-heavy-code/


zl;ng wollte noch meer schreiben aber mir ging die Puste aus

LG schlechter Informatiker

subburam Avatar
subburam:#8749

>>8746
>Würde mich wundern, wenn das was bringen würde. Du hast einen zusätzlichen function call, und das Ergebnis wird so oder so an die andere Funktion übergeben, die die Wurzelberechnung übernimmt. Das kommt jetzt auf den Compiler drauf an, ob das jetzt irgendwie über lookup-tables geregelt wird, oder trotzdem ganz normal berechnet wird.

Habe leider keine Quelltexteinsicht, gehe aber hier von einer Berechnung aus

>Würde ignorieren und mich auf das Hauptproblem konzentrieren, und das sind deine 3 verschachtelten foreach-Schleifen. Das geht so überhaupt nicht, deine Komplexität ist viel zu hoch.
Dies, macht Sinn da erst Hand an zu legen wenn das wirklich einen spürbaren Performanceeinfluss hat.
Dummerweise sehe ich keine Möglichkeit die 3 Schleifen loszuwerden. Funktionieren wird aber wohl:

>Könnte man dann noch weiter optimieren, um beispielsweise die Liste der Grids über die Koordinaten durch zu sortieren und dann über divide-and-conquer schnell mögliche Kandidaten rauszufiltern.
Das vermutlich dann mit Bäumen sowohl in der Gridübersicht als auch in den Grids selber. Dann aber am besten dann wohl mit Quadtrees, wobei diese vermutlich dann dynamisch generiert werden müssten.
Ich werde es mal probieren sie an Hand einer relativen Entfernung zum Mittelpunkts des gesammten Grids aus in Untergruppen zu packen.
Vermutlich wird aber dann das rebalancen wieder recht performanceintensiv.
Will ich denn überhaupt bei diesen Checks anfangen zu sortieren? Gerade Sortiervorgänge dauern doch besonders lang?

irsouza Avatar
irsouza:#8750

>>8749
>Will ich denn überhaupt bei diesen Checks anfangen zu sortieren?
Nein, ich wollte noch "im Hintergrund" schreiben, falls das irgendwie machbar ist. Hab ich wohl verschluckt.

samscouto Avatar
samscouto:#8751

>>8750
PS: Würde mir aber darüber weniger Gedanken machen, ist für Spiele die in Echtzeit laufen als Optimierungsmethode wohl eher ungeeignet. Habe ich nur mal so in den Raum geworfen.

Aber das ganze in eine sortierte (nach Koordinaten bspw.) Liste zu packen, um dann nur wenige potentielle Kandidaten überprüfen zu müssen, erscheint mir als die beste Lösung um die Zeitkomplexität zu reduzieren.

evandrix Avatar
evandrix:#8753

>>8745
Oke, du willst also wissen, welche Punkte (Batterien, Konsumenten) innerhalb von Kugeln (Produzenten und mit Reichweite) liegt.

Was spricht dagegen das einmal für alle Teilnehmer mit Komplexität O(n^9000) auszurechnen und die Ergebnisse zu cachen?

Einen Eintrag aus dem Cache holen sollte O(n) kosten.

Den Cache müsstest du dann nur mit geringer Komplexitat aktualisieren wenn ein Teilnehmer
a) zerstört wird
b) erschaffen wird
c) sich bewegt

hampusmalmberg Avatar
hampusmalmberg:#8758

>>8753
>Einen Eintrag aus dem Cache holen sollte O(n) kosten.
topkek

>Was spricht dagegen das einmal für alle Teilnehmer mit Komplexität O(n^9000) auszurechnen und die Ergebnisse zu cachen?
Weil er offensichtlich öfter sowas machen will, nicht nur einmal.

>Den Cache müsstest du dann nur mit geringer Komplexitat aktualisieren wenn ein Teilnehmer
so wie es momentan schon im Kot steht? hurr

erikdkennedy Avatar
erikdkennedy:#8760

Hab mir den Code nicht durchgelesen, aber Cachen ist bei sowas keine schlechte Idee. Jeder Connector merkt sich, welche Grids in Reichweite sind, und du aktualisierst nur, wenn ein neuer Connector oder Grid hinzukommt.

snowwrite Avatar
snowwrite:#8777

>>8758
> Weil er offensichtlich öfter sowas machen will, nicht nur einmal.
Das ist offensichtlich der Fall. Ich zweifle aber an, dass das Sinn macht.

> so wie es momentan schon im Kot steht? hurr
Nein, Bernd.
Er rechnet alles neu bei einer Änderung. Da ist kein ordentliches caching.

Auch:
Verpisse dich nach /b/. Oder noch weiter.