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.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Gleichheit von Bäumen feststellen

Beitragvon Nikolas » Freitag 11. Januar 2008, 12:32

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. :lol:
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, 12:42

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!
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Beitragvon Rebecca » Freitag 11. Januar 2008, 12:49

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
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Freitag 11. Januar 2008, 12:49

Noch eine kleine Anmerkung: Der Plural von "child" lautet "children". "childs" gibt es nicht.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Beitragvon Nikolas » Freitag 11. Januar 2008, 12:50

>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)
:lol:

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.
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, 12:51

Rebecca hat geschrieben: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?

Nikolas hat geschrieben: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.

Nikolas hat geschrieben:>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.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Beitragvon Rebecca » Freitag 11. Januar 2008, 13:11

BlackVivi hat geschrieben: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...
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

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

Rebecca hat geschrieben: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

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

@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.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Beitragvon Rebecca » Freitag 11. Januar 2008, 13:51

BlackVivi: OK, das sehe ich heute zum ersten Mal. :)
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

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

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

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.
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, 14:29

Nikolas hat geschrieben: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
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

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

das verwirrt mich jetzt doch etwas. Warum ist denn unten a!=b True?
Was macht denn != sonst, wenn es nicht negiert?
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Freitag 11. Januar 2008, 14:54

Nikolas hat geschrieben:Was macht denn != sonst, wenn es nicht negiert?

``__neq__`` aufrufen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Freitag 11. Januar 2008, 14:56

Leonidas hat geschrieben:
Nikolas hat geschrieben: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)

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot], snafu