Gleichheit von Bäumen feststellen

[Nikolas]

Hallo

Ich habe gerade mit einem größeren Projekt angefangen und habe mir dafür eine BaumKlasse definiert.

Code: Alles auswählen

class Node():
    def __init__(self,value=None, childs = []):

        self.arg={"value":value,
                  "childs":childs}
        (...)

also grob: ein node ist ein dictionary aus Werten, wobei einer dieser Werte eine Liste an nodes ist.

Als braver Programmierer habe ich mir gleich Testfälle geschrieben und habe jetzt das Problem, dass ich zwei Bäume nicht vergleichen kann:

>>> a=Node(43)
>>> b=Node(43)
>>> a==b
False

Ich könnte mir jetzt eine rekursive Funktion schreiben, die immer alle Einträge in den dicts vergleicht und sich für die Kinder aufruft, aber so schön fände ich es nicht.

Alternativ habe ich mir überlegt, so ein Objekt per Pickle in ein Binärformat umzuwandeln und dann davon eine Prüfsumme zu berechnen, aber das finde ich fast schon zu hackish.

Wenn Python doch eigentlich 'batteries included' heisst, müsste es doch da auch was passendendes für mich geben.

[BlackVivi]

Du könntest __eq__ dafür verwenden.

Code: Alles auswählen

In [17]: class Baum(object):
   ....:
   ....:     def __init__(self, foo):
   ....:         self.foo = foo
   ....:
   ....:     def __eq__(self, other):
   ....:         if other == self.foo:
   ....:             return True
   ....:         else:
   ....:             return False
   ....:
   ....:

In [18]: a = Baum(1)

In [19]: b = Baum(1)

In [20]: a == b
Out[20]: True

P.S.: Ein Blick in's PEP8 könnte nicht schade, keine Mahnung oder sowas, nur'n Hinweis!

[Rebecca]

Zeile 7 ist nicht ganz korrekt, du willst ja mit other.foo vergleichen. Ausserdem kannst du dir die if-Abfrage sparen:

Code: Alles auswählen

def __eq__(self, other):
    return self.foo == other.foo

[EyDu]

Noch eine kleine Anmerkung: Der Plural von "child" lautet "children". "childs" gibt es nicht.

[Nikolas]

>P.S.: Ein Blick in's PEP8 könnte nicht schade, keine Mahnung oder sowas, nur'n Hinweis!
wegen was denn?

Code: Alles auswählen

   ....:         if other == self.foo:
   ....:             return True
   ....:         else:
   ....:             return False

Im PEP steht aber fast sicher, dass solcher Code zu vermeiden ist...
da steht doch einfach nur

Code: Alles auswählen

return (other == self.foo)

Dein Vorschlag hilft mir leider nicht weiter, da ich so eine Lösung eigentlich vermeiden wollte. Ich müsste das ja rekursiv weitermachen, da ich eine Liste an weiteren Knoten habe und die kann ich nicht einfach per == vergleichen.

Aber das mit == überladen sieht gut aus, das werde ich dann integrieren.

[BlackVivi]

Zeile 7 ist nicht ganz korrekt, du willst ja mit other.foo vergleichen. Ausserdem kannst du dir die if-Abfrage sparen:

Code: Alles auswählen

def __eq__(self, other):
    return self.foo == other.foo

Ich hab's nur ausgeschrieben, damit man die ganze IF Abfrage halt aufbauen kann und es klar ist, was ich mein...

Aber wieso ist es nicht korrekt? Beim Vergleich wird jeweils das __eq__ aufgerufen, oder?

Dein Vorschlag hilft mir leider nicht weiter, da ich so eine Lösung eigentlich vermeiden wollte. Ich müsste das ja rekursiv weitermachen, da ich eine Liste an weiteren Knoten habe und die kann ich nicht einfach per == vergleichen.

Aber das mit == überladen sieht gut aus, das werde ich dann integrieren.

Du kannst doch den __eq__ Code so ausbauen, dass von den children jeweils auch die __eq__ Klasse aufgerufen wird, die die Gleichheit mit den children von other prüft.

>P.S.: Ein Blick in's PEP8 könnte nicht schade, keine Mahnung oder sowas, nur'n Hinweis!
wegen was denn?

Bspw. wegen den Leerzeilen zwischen der Klassendefintion und der Funktiondefinitionen, obwohl da PEP8 auch 2 Zeilen vorschlägt ... Und bei den Standardwerten von einer Funktion soll man normalerweise kein Leerzeichen zwischen dem = Operator machen.

[Rebecca]

Aber wieso ist es nicht korrekt? Beim Vergleich wird jeweils das __eq__ aufgerufen, oder?

Du willst ja, dass die Objekte gleich sind, wenn ihr foo-Attribut gleich sind. Also wenn a.foo == b.foo ist. Bei a == b wird __eq__(a, b) aufgerufen, (somit self=a, other=b), also musst du self.foo mit other.foo vergleichen (nicht mit other).

Du hast Glueck, dass dein Beispiel trotzdem funktioniert, da er beim Vergleich von self.foo mit other nochmal wieder diese __eq__-Methode aufruft und dann letztendlich doch wieder richtig verglichen wird:

Code: Alles auswählen

>>> class A:
...      def __init__(self, foo): self.foo = foo
...      def __eq__(self, other):
...          print "eq", self, other
...          return (self.foo == other)
...
>>> a = A(1); b = A(1)
>>> a == b
eq <__main__.A instance at 0xb7d494cc> <__main__.A instance at 0xb7d3b72c>
eq <__main__.A instance at 0xb7d3b72c> 1
True

Hab ein Weilchen gebraucht, darauf zu kommen, warum deine Methode doch funktioniert...

[BlackVivi]

Du hast Glueck, dass dein Beispiel trotzdem funktioniert, da er beim Vergleich von self.foo mit other nochmal wieder diese __eq__-Methode aufruft und dann letztendlich doch wieder richtig verglichen wird

Aber dies ist von mir auch gewünscht oO! Somit kann auch das Element mit anderen Klassen verglichen werden, deren Attribute nicht so benannt sind. Vielleicht ist es in diesem Fall nicht so dringend notwendig, aber ansonsten is's für mich so logischer oO! Aber vielleicht ist das Anssichtssache.

[BlackJack]

@Nikolas: Du wirst um eine eigene rekursive Lösung nicht herumkommen. Dass Du das selber machen musst und nicht es standardmässig so gemacht wird, sollte vielleicht klar werden, wenn Du mal überlegst, was einem Objekt alles dran hängt. Alles sind Attribute, auch Methoden, die Verweise auf die Oberklassen und bei den referenzierten Objekten dann das gleiche Spiel. Methoden haben Referenzen auf ihren Namen, auf Code-Objekte usw. und Klassen auf Funktionen und eventuell auf weitere Klassen usw. Da können natürlich auch Kreise von Referenzen entstehen. Also würde so ein "Default"-Vergleich zwei ziemlich grosse Graphen rekursiv vergleichen müssen.

[Rebecca]

BlackVivi: OK, das sehe ich heute zum ersten Mal.

[Nikolas]

Ich hatte nicht gedacht, dass ich mit einer so einfach Frage gleich eine nette Diskussion lostrete

Die rekursive Lösung ist auch nicht allzu schwierig, da ich alle Eigenschaften in einem dict habe, so dass ich auch dei __eq__ nicht verändern muss, wenn ich mal eine zusätzliche Eigenschaft einfüge.

Code: Alles auswählen

    def __eq__(self,other):
        if not isinstance(other, Node):
            return False
        
        for key in self.arg.keys():
            if key == "childs": continue # wird separat betrachtet
            if self.arg[key]!=other.arg[key]:
                return False

        # alle Eigenschaften gleich
        a = self.arg["childs"]
        b = other.arg["childs"]
        if len(a)!=len(b):
            return False
        for i in range(len(a)):
            if not (a[i]==b[i]):
                return False

        return True

Hat noch jemand was zu meckern? bei #(foobar) habe ich noch eine Frage: Nach dem Python Ge-Packt vom MITP wird das __eq__ für den ==-Aufruf benutzt. Was ist aber mit != ?
Das könnte ja eigentlich als

Code: Alles auswählen

def __noteq__(self,other):
return not self == other

implementiert werden, was es aber nicht ist, wie man sieht:

Code: Alles auswählen

class foo():
    def __init__(self,value):
        self.value = value

    def __eq__(self,other):
        print "hallo"
        return self.value == other.value

>>> a=foo(2)
>>> b=foo(3)
>>> a==b
hallo
False
>>> a!=b
True
>>>

Weiss jemand, wie das funktioniert?

@ BlackJack:
Das die Suche möglicherweise groß wird, passiert ja auch, wenn ich es mache. (Ausser dass ich hier die Möglichkeit habe, den längstem Vergleich hinter die anderen zu legen). Die Zyklen kann Python doch aber erkennen, z.B. Beispiel bei einem L.append(L).
Und meine Lösung ist ziemlich einfach. Ich gehe einfach jede Eigenschaft durch und schaue, ob die andere Klasse auch so eine Eigenschaft hat und vergleiche dann mit dem passenden Vergleichsoperator.

[BlackVivi]

implementiert werden, was es aber nicht ist, wie man sieht:

Code: Alles auswählen

class foo():
    def __init__(self,value):
        self.value = value

    def __eq__(self,other):
        print "hallo"
        return self.value == other.value

>>> a=foo(2)
>>> b=foo(3)
>>> a==b
hallo
False
>>> a!=b
True
>>>

Weiss jemand, wie das funktioniert?

Will dir mal nur was zeigen, vllt kommst du selbst drauf :3

Code: Alles auswählen

class Baum(object):

    def __init__(self, foo):
        self.foo = foo

    def __eq__(self, other):
        return self.foo == other

Code: Alles auswählen

In [33]: a = Baum(1)

In [34]: b = Baum(2)

In [35]: a != b
Out[35]: True

In [36]: a == b
Out[36]: False

In [37]: a = Baum(1)

In [38]: b = Baum(1)

In [39]: a != b
Out[39]: True

In [40]: a == b
Out[40]: True

^_^

[Nikolas]

das verwirrt mich jetzt doch etwas. Warum ist denn unten a!=b True?
Was macht denn != sonst, wenn es nicht negiert?

[Leonidas]

Was macht denn != sonst, wenn es nicht negiert?

``__neq__`` aufrufen.

[BlackVivi]

Was macht denn != sonst, wenn es nicht negiert?

``__neq__`` aufrufen.

__ne__ oder oO...

Ich würd's so lösen :3

Code: Alles auswählen

class foo(object):

    def __init__(self, foo):
        self.foo = foo

    def __eq__(self, other):
        return self.foo == other

    def __ne__(self, other): return not self.__eq__(other)
    
if __name__ == "__main__":
    print foo(1) != foo(1)

[BlackJack]

@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]

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

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?

[BlackVivi]

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]

@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]

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.