Typ von Objekten dynamisch ändern

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
barfoos
User
Beiträge: 25
Registriert: Dienstag 29. Juli 2008, 09:46

Dienstag 29. Juli 2008, 10:03

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
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 29. Juli 2008, 10:52

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Dienstag 29. Juli 2008, 11:14

Code: Alles auswählen

node = FooTreeNode.fromSimpleTreeNode(my_simple_tree_node)
Erstell einfach ein neues Objekt.
barfoos
User
Beiträge: 25
Registriert: Dienstag 29. Juli 2008, 09:46

Dienstag 29. Juli 2008, 12:10

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
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 30. Juli 2008, 00:57

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
barfoos
User
Beiträge: 25
Registriert: Dienstag 29. Juli 2008, 09:46

Donnerstag 31. Juli 2008, 16:24

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
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Donnerstag 31. Juli 2008, 17:58

Du siehst es falsch ;-) Es werden nur die Referenzen kopiert aber nicht die ganzen Daten die dahinter stehen.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 31. Juli 2008, 18:05

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
barfoos
User
Beiträge: 25
Registriert: Dienstag 29. Juli 2008, 09:46

Freitag 1. August 2008, 08:54

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
barfoos
User
Beiträge: 25
Registriert: Dienstag 29. Juli 2008, 09:46

Freitag 1. August 2008, 09:52

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]
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 1. August 2008, 11:32

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten