Seite 1 von 1
Typ von Objekten dynamisch ändern
Verfasst: Dienstag 29. Juli 2008, 10:03
von barfoos
Hallo
Ich habe gelesen, dass es eher nicht ratsam ist, zu Versuchen, den Typ eines Objektes zu ändern. Deshalb möchte ich fragen, wie sich folgendes Szenario schön umsetzen lässt.
Es geht darum Baumstrukturen mittels Python zu traversieren und zu transformieren.
Ich würde am liebsten eine Klasse "TreeNode" anlegen, und von dieser Klasse mehrere Unterklassen bilden -- etwa "SimpleTreeNode" und "ForkingTreeNode". Allen TreeNodes ist gemein, dass sie eine Reihe von Nachfolgern/Branches habe.
Es soll für alle TreeNodeKlassen jeweils eine Methode Simplify() geschrieben werden.
Simplify arbeitet im wesentlichen rekursiv.
So soll beispielsweise ForkingTreeNode.Simplify() zunächst die Simplify()-Methode aller Branches aufrufen. Dadurch sollen die Branches des ForkingTreeNodes verändert werden. Im nächsten Schritt soll ForkingTreeNode.Simplify() unter bestimmten Bedingungen durch den ForkingTreeNode durch einen SimpleTreeNode ersetzen. Und da liegt das Problem!
Ein Aufruf der Form:
Code: Alles auswählen
def Simplify(self):
i = self.GetBestBranch()
self = self.branch[i]
funktioniert nicht.
Also dachte ich eigentlich als nächstes an folgendes:
Code: Alles auswählen
def Simplify(self):
i = self.GetBestBranch()
self.__class__ = self.branch[i].__class__
self.branches = self.branch[i].branches
Das bringt aber eben auch Probleme mit sich.
Meine momentane Lösung sieht so aus, dass ich statt verschiedener Unterklassen von TreeNode nur noch die Klasse TreeNode verwende.
Jedes TreeNode-Objekt hat ein zusätzliches Attribut, welches den TreeNode-Typ ausdrückt.
Der Voreilt ist: Ich kann den "Typ" der TreeNodes dynamisch ändern:
Code: Alles auswählen
def Simplify(self):
...
i = self.GetBestBranch()
self.treenodetype = self.branch[i].treenodetype
self.branches = self.branch[i].branches
...
Der Nachteil ist: ich kann muss mich selbst um die Überladung der Simplifymethode kümmern:
Code: Alles auswählen
def Simplify(self):
if self.treenodetyp == TreeNode.FORKING_NODE:
...
elif self.treenodetyp == TreeNode.SIMPLE_NODE:
...
else:
raise Exception("Simplify not implemented for" + self.treenodetyp)
Was fällt euch dazu ein? Wie löst man das elegant?
Danke und gruß
barfoos
Verfasst: Dienstag 29. Juli 2008, 10:52
von Leonidas
Ich würde das so lösen, dass ``simplify()`` (was ich übrigens nach PEP8 wie eine Methode benennen würde und nicht wie eine Klasse) einfach einen vereinfachten Subtree zurückgibt, der dann vom Caller verwendet werden kann um den Node durch den von ``simplify()`` zurückgegebenen Node (+ Subnodes) zu ersetzen.
Hint: für verarbeitung von Bäumen habe ich Multimethods als ziemlich praktisch empfunden, siehe
VisitorRevisited.
Verfasst: Dienstag 29. Juli 2008, 11:14
von audax
Code: Alles auswählen
node = FooTreeNode.fromSimpleTreeNode(my_simple_tree_node)
Erstell einfach ein neues Objekt.
Verfasst: Dienstag 29. Juli 2008, 12:10
von barfoos
Danke für eure Vorschläge.
Einfach neue Objekte zu erstellen ist sicher die einfachste Lösung.
Es wird bei mir aber so sein, dass sich ppro ausgeführtem Simplify kaum etwas ändert am Baum. Ein komplettes Umkopieren halte ich daher für zu langsam.
Ich muss aber zugeben, das nicht nachgemessen zu haben.
Es ist nur ein Bauchgefühl, welches mir sagt, dass es so wie ich es bis jetzt mache recht schnell geht.
Liege ich total daneben mit meinem Bauchgefühl?
Danke und gruß
barfoos
PS: um es noch etwas zu präzisieren: mein Simplify wird in den allermeisten Fällen entweder gar nichst machen, oder aber den aktuellen Knoten durch einen seiner Branches ersetzen". Dafür jedesmal den Baum zu kopieren erscheint mir sehr ungünstig
Verfasst: Mittwoch 30. Juli 2008, 00:57
von Leonidas
barfoos hat geschrieben:Einfach neue Objekte zu erstellen ist sicher die einfachste Lösung.
Es wird bei mir aber so sein, dass sich ppro ausgeführtem Simplify kaum etwas ändert am Baum. Ein komplettes Umkopieren halte ich daher für zu langsam.
Wer sagt denn was von kopieren? Pro Simplify-Aufruf und Node wird maximal ein Objekt neu erstellt, wenn überhaupt, sonst werden ja nur immer Referenzen auf bereits bestehende Objekte verwendet (Pythons Namen sind Referenzen auf Objekte, die gut und gerne auch mehrere Namen haben lönnen und von vielen Namen referenziert werden können).
Letztendlich macht dein im ersten Post vorgeschlagenes Konzept auch nichts anderes, der Baum wird dort ebensowenig wie in meinem Vorschlag kopiert nur versuchst du das Objekt zu ändern wärend ich dir rate ein neues Objekt zu erstellen, was das alte Objekt obsolet macht.
Verfasst: Donnerstag 31. Juli 2008, 16:24
von barfoos
Danke für deinen Vorschlag.
Ändert es etwas, wenn ich erwähne, dass die Bäume auch mal groß werden können?
Ich glaube, wir meinen zwei unterschiedliche Sachen, wenn wir kopieren sagen. Mir ist klar, dass die Blätter des Baumes nicht kopiert werden. Allerdings wird quasi durch das Erstellen eines neuen Objektes für jeden Baumknoten, zumindest der Baum kopiert. Zwar wird der alte Baum sofort verworfen, aber zuvor wird er kopiert, oder sehe ich das falsch?
Ich denke in der Größenordnung 10.000 Knoten und 1000 Simplify-Aufrufe pro Sekunde. Das dass nie im Leben funktioniert ist mir klar. Nur versuche ich mich der Sache optimistisch anzunähern. Wahrscheinlich müsste ich auf C++ oder etwas ähnliches Umsteigen, um wirklich performant zu werden. Aber das ist für einen Prototyp zum umständlich. Am Ende soll das ganze nur so gut werden, dass man es wenigstens mal ein Beispielen der realen Welt ausprobieren kann.
Danke und gruß
barfoos
Verfasst: Donnerstag 31. Juli 2008, 17:58
von EyDu
Du siehst es falsch
Es werden nur die Referenzen kopiert aber nicht die ganzen Daten die dahinter stehen.
Verfasst: Donnerstag 31. Juli 2008, 18:05
von Leonidas
barfoos hat geschrieben:Ich glaube, wir meinen zwei unterschiedliche Sachen, wenn wir kopieren sagen. Mir ist klar, dass die Blätter des Baumes nicht kopiert werden. Allerdings wird quasi durch das Erstellen eines neuen Objektes für jeden Baumknoten, zumindest der Baum kopiert. Zwar wird der alte Baum sofort verworfen, aber zuvor wird er kopiert, oder sehe ich das falsch?
Ja, denn warum sollte man den Baum kopieren?
Ich illustriere das mal mit einem kleinen Schnippsel (das ohne simplify auskommt, aber das musst du dir einfach dazudenken)
Code: Alles auswählen
In [5]: class Node(object):
...: pass
...:
In [6]: root = Node()
In [7]: root.left = Node()
In [8]: root.right = Node()
In [9]: root, root.left, root.right
Out[9]:
(<__main__.Node object at 0x20426d0>,
<__main__.Node object at 0x1e8e290>,
<__main__.Node object at 0x1e8e210>)
In [10]: new_node = Node()
In [11]: new_node.left = root.right
In [12]: new_node.right = root.left
In [13]: root = new_node
In [14]: root, root.left, root.right
Out[14]:
(<__main__.Node object at 0x1e8e250>,
<__main__.Node object at 0x1e8e210>,
<__main__.Node object at 0x1e8e290>)
Node ist einfach mal eine Klasse, die bei dir dann ein ``simplify`` enthält. Zuerst habe ich den ursprünglichen Baum, ``root`` mit den Child-Nodes ``left`` & ``right``. Du siehst auch in der Darstellung die Adressen, damit du siehst welche Objekte das sind. Nun stelle ich fest, dass ich den Baum transformieren will (= ``simplify``), also erstelle ich einen neuen ``Node`` der jetzt irgendwie anders ist als der ursprüngliche. In diesem Beispiel sind die Child-Nodes vertauscht. Daraufhin überschreibe ich den alten root-Node und zeige es wieder an.
Man sieht nun, dass der Parent-Node ein anderer ist aber die Child-Nodes immer noch die gleichen Objekte referenzieren wie vor der Transformation - also nicht kopiert worden sind.
Verfasst: Freitag 1. August 2008, 08:54
von barfoos
Ah, ich glaube jetzt verstehe ich dich
Mein Simplify sähe dann so aus:
Code: Alles auswählen
class Node(object):
...
class ComplexANode(Node):
def simplify():
left = self.__left.simplify()
right = self.__right.simplify()
if left.canBeIgnored():
return right
if right.canBeIgnored():
return left
self.__left = left
self.__right = right
return self
class ComplexBNode(Node):
....
Mein Denkfehler lag in Zeile 13 bis 15. Ich hatte irgendwie geglaubt ich müsste dort return ComplexANode(left,right) schreiben.
Das hätte in der Tat eine komplette Baumkopie ergeben.
Danke für die Unterstützung
gruß
barfoos
Verfasst: Freitag 1. August 2008, 09:52
von barfoos
Nachtrage:
ich bin der Sache mit dem Visitor-Pattern nochmal nachgegangen und habe
hier eine in meinen Augen sehr elegante Schreibweise dafür gefunden.
Allerdings frage ich mich, woher ich die @visit und @dispatch Dekorationen nehmen soll. Sind das Standard-Pythonkonstrukte?
Danke und gruß
barfoos[/url]
Verfasst: Freitag 1. August 2008, 11:32
von Leonidas
Wobei ich wenn ``simplify`` uninteressante Nodes zurückgibt None zurückgeben würde, statt den Node, wo man nochmal eine Funktion aufruft.
barfoos hat geschrieben:ich bin der Sache mit dem Visitor-Pattern nochmal nachgegangen und habe
hier eine in meinen Augen sehr elegante Schreibweise dafür gefunden.
Allerdings frage ich mich, woher ich die @visit und @dispatch Dekorationen nehmen soll. Sind das Standard-Pythonkonstrukte?
Nein. Ich habe dir schon in meiner
ersten Antwort einen Link auf VisitorRevisited gegeben, in der Multimethods vorgestellt werden. PJE nutzt da RuleDispatch, welches ich auch verwendet habe (
Beispiel). Inzwischen wird aber RuleDispatch vom Autor durch
PEAK-Rules ersetzt. Ansonsten gibt es noch
PyDispatcher und
Louie (welches ein weiterentwickeltes PyDispatcher ist).
Multimethods sind überigens Standardkonstrukte die in Common Lisps CLOS verwendet werden.