Gleichheit von Bäumen feststellen

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.
BlackJack

Beitragvon BlackJack » Freitag 11. Januar 2008, 15:13

@BlackVivi: Statt ``not self.__eq__(other)`` würde ich ``not (self == other)`` schreiben.

@Nikolas: Kannst Du in der `__eq__()` nicht ganz einfach ``return self.args == other.args`` schreiben? Die Vergleichsmethode von Dictionaries vergleicht die Einträge dann schon rekursiv mit ``==``, also auch `Node`-Objekte wieder mit deren `__eq__()`-Implementierung.

Und Du hast meinen Einwand bezüglich der Grösse des Graphen beim Vergleich glaube ich nicht ganz verstanden. Wenn man so etwas "generisch" implementieren möchte, würden diese Graphen alle Objekte enthalten, die an so einem Ausgangs-Objekt transitiv dranhängen. Das ist *richtig* viel. Oder es müsste eine Möglichkeit geben diese Menge explizit ein zu schränken ─ dann kann man aber genau so gut explizit selber vergleichen.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Beitragvon Nikolas » Freitag 11. Januar 2008, 15:33

also erst mal ein großes dankeschön an euch alle :lol:

das __ne__ habe ich einfach übersehen. (wer die ge-packt serie nicht kennt: das ist grob schriftgröße 8...)

> Kannst Du in der `__eq__()` nicht ganz einfach ``return self.args == other.args`` schreiben?
öhm doch. hab ich ganz übersehen. Aber da die Liste bei mir als zweites Argument geführt ist und ich das jetzt nicht umbauen will, würde diese kurze Lösung eine längere Ausführungszeit haben, da zwei riesige Bäume, die sich nur im Wert der Wurzel unterscheiden, erst ganz durchlaufen werden, bevor die Wurzel angeschaut wird.

Das mit de Größe war mir nicht bewusst. Wie viele Objekte hängen denn da intern dran?
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Freitag 11. Januar 2008, 15:40

Nikolas hat geschrieben:das __ne__ habe ich einfach übersehen. (wer die ge-packt serie nicht kennt: das ist grob schriftgröße 8...)
Dann leg ich dir einfach mal das an's Herz:

http://rgruet.free.fr/

@BlackVivi
Danke. Ist wesentlich lesbarer.
BlackJack

Beitragvon BlackJack » Freitag 11. Januar 2008, 16:06

@Nikolas: Das kann passieren, muss aber nicht, das hängt wohl davon ab, welche Schlüssel in den Dictionaries zufällig als erstes verglichen werden.

Allerdings finde ich den Entwurf die Attribute, die man auf einem Knoten-Objekt erwarten würde, nochmal in ein extra Dictionary zu stecken sowieso nicht so gut. Warum sind `value` und `children` nicht direkt Attribute des Objekts? Dann liesse sich die `__eq__()`-Methode als ``return self.value == other.value and self.children == other.children`` schreiben und das Problem mit der Reihenfolge ist gelöst.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Beitragvon Nikolas » Freitag 11. Januar 2008, 16:14

Ich habe das gemacht, um später verschiedene Funktionen einfach benutzen zu können. Will ich z.B. testen, ob ein Baum ein Suchbaum ist, mache ich eine LinksMitteRechts Traversierung und schreib mir die Werte auf, und schau dann, ob diese Liste sortiert ist.
Will ich jetzt rausfinden, ob mein Baum ein Binärbaum ist, mache ich das gleiche, schreibe mir aber die Kinderanzahl in meine Liste.
Die beiden Funktionen unterscheiden sich nur in einem parameterstring ("value" oder "childCnt") und in der Listenauswertung am Schluss.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
BlackJack

Beitragvon BlackJack » Freitag 11. Januar 2008, 16:31

Dann holst Du Dir eben die Attribute in der Funktion vom Objekt statt aus dem Dictionary. Siehe die Funktion `getattr()`.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Beitragvon Nikolas » Freitag 11. Januar 2008, 16:35

aha. wieder was gelernt. Das ist wirklich eine Alternative und hat auch die schönere __eq__-Funktion.
Gibts denn da auch eine entsprechung für dict.keys()? Sonst wirds wieder mit der Testreihenfolge beim __eq__ schwierig.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot], Google [Bot]