Doing mit Globals weg?

Question

Ich habe eine Reihe von Baumobjekte mit einer Tiefe irgendwo in den 20er Jahren. Jeder der Knoten in diesem Baum benötigt Zugriff auf seine Baumwurzel.

Ein paar Lösungen:

1. Jeder Knoten einen Verweis auf den Stammspeicher kann direkt (Abfälle Speicher)
   • kann ich die Wurzel zur Laufzeit berechnen, indem "going up" (Abfälle Zyklen)
   • kann ich statische Felder verwenden (aber diese beträgt Globals)

Kann jemand ein Design, das nicht einen globalen nicht verwendet (in jeder Variation), ist jedoch effizient, dass # 1 oder # 2 in beiden Speichern oder Zyklen jeweils?

Edit: Da ich eine Reihe von Bäumen haben, kann ich nicht einfach speichern sie in einem statischen, da es schwierig sein würde zwischen den Bäumen zu unterscheiden. (Dank maccullt)

Answer 1

übergeben Sie die Wurzel als Parameter je nachdem, welche Funktionen in den Knoten, die sie benötigen.

Edit: Die Optionen sind wirklich die folgenden:

1. Lagern Sie die Wurzel Referenz im Knoten
2. Speichern Sie nicht die Wurzel Bezug auf all
3. Speichern Sie die Root-Referenz in einem globalen
4. Speichern Sie die Root-Referenz auf dem Stapel (mein Vorschlag, entweder Besuchermuster oder rekursiv)

ich denke, das alle Möglichkeiten, gibt es keine Option 5.

Answer 2

Warum würden Sie brauchen, um mit Globals zu tun, weg? Ich verstehe das Stigma des Globals schlecht zu sein und alles, aber manchmal nur mit allen Elementen einer globale Datenstruktur, ist die schnellste Lösung.

Sie machen einen Kompromiss: Code Klarheit und weniger zukünftige Probleme für die Leistung. Das ist der Sinn sein ‚Optimieren Sie noch nicht‘. Da Sie in der optimize Bühne sind, manchmal ist es notwendig, einige Lesbarkeit und gute Programmierpraktiken zugunsten der Leistung auszuschneiden. Ich meine, bitweise Hacks sind nicht lesbar, aber sie sind schnell.

Ich bin mir nicht sicher, wie viele Baumobjekte Sie haben, aber ich würde persönlich mit der Option einer gehen. Es sei denn, Sie mit Tausenden es zu tun + von Bäumen, werden die Zeiger wirklich nicht viel mehr betragen als ein paar Saiten. Wenn der Speicher wirklich ein super-wichtiges Thema ist, versuchen beide Methoden (sie ziemlich einfach erscheinen zu implementieren) und es durch einen Profiler laufen. Oder die hervorragenden Prozess Explorer .

Edit: Eine der Apps Ich arbeite an hat einen Knotenbaum über 55K Knoten enthält. Wir bauen die Baumstruktur, sondern auch eine Anordnung für O (1) Lookups aufrechtzuerhalten. Viel besser als die O (m * n) wir bekommen wurden, wenn ein rekursive FindNodeByID Verfahren.

Answer 3

die Wurzel als Parameter ist in der Regel am besten. Wenn Sie irgendeine Art von Iterator verwenden, den Baum zu navigieren, eine Alternative ist eine Referenz auf Wurzel zu speichern, dass.

Answer 4

Der Punkt # 1 ist eine vorzeitige Speicher-Optimierung. # 2 ist eine vorzeitige Performance-Optimierung. wenn der Speicher oder CPU-Engpässe haben Sie profilierte Ihre Anwendung zu bestimmen, verursachen Probleme für Sie? Wenn nicht, warum opfert, um ein besser verwaltbar Design für eine „Optimierung“, die nicht Ihre Benutzern helfen?

Ich würde Sie empfehlen dringend mit # 2 gehen. Jedes Mal, wenn Sie etwas speichern, könnten Sie stattdessen berechnen, was Sie tun, Caching ist. Es gibt ein paar Mal, wenn Caching ist eine gute Idee, aber es ist auch eine Wartung Kopfschmerzen. (Zum Beispiel, was passiert, wenn Sie bewegen, um einen Knoten von einem Baum zum anderen von der Mutter ändern, aber vergessen, auch das Root-Feld zu aktualisieren?) Nicht gespeichert werden, wenn Sie nicht haben.

Answer 5

Sie können eine Klasse von TreeView ableiten und dann eine Singleton statische Eigenschaft hinzuzufügen. So können Sie effektiv ein globales Feld hinzufügen, der die einzige Instanz der Klasse verweist, haben aber den Vorteil, wobei Namensraum dieser Klasse scoped.

Answer 6

Das Ignorieren der Abneigung gegen die inneren Klassen, kann ich eine Tree-Klasse definieren und die Knoten als innere Klassen definieren. Jeder der Knoten würde den Zugang zu seinem Baum des Staates einschließlich seiner Wurzel.

Dies könnte auf das gleiche ist wie # 1 in Abhängigkeit von Ende, wie Java, die Knoten zu ihren Eltern betrifft. (Ich bin nicht sicher, und ich werde es Profil müssen)