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.
class Picker(list, Observable):
def __init__(self, name):
list.__init__(self)
Observable.__init__(self)
self.name = name
def pick(self, item):
if item in self:
self.remove(item)
else:
self.append(item)
self.notify_observers(self)
def __hash__(self):
return id(self)
Die Doku schreibt unter anderem zu '__hash__': "... If a class does not define a __cmp__() or __eq__() method it should not define a __hash__() operation either; ..."
Ich bin mir nicht sicher, wie das zu übersetzen ist:
- Wenn keine '__cmp__' oder '__eq__' definiert ist, sollte auch keine '__hash__' definiert werden
oder
- Wenn keine '__cmp__' oder '__eq__' definiert ist, sollte dafür (also zum Vergleich mit 'is' / '==') nicht '__hash__' verwendet werden
Beides kommt mir merkwürdig vor. Die Frage für mich ist schlichtweg, ob meine Verwendung der '__hash__'-Methode so in Ordnung geht.
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit )
@mutetella: Nein das geht so nicht wirklich in Ordnung. Wenn man eine `__hash__()`-Methode definiert, dann muss es eine dazu passende Vergleichsmethode geben. Kannst Dir ja jetzt überlegen wo die vorhandene Vergleichsmethode von Listen den Vertrag für das Funktionieren von Hash-Tabellen verletzt.
Der Satz lautet übrigens (etwas gekürzt): Wenn eine Methode keine Vergleichsmethode definiert, sollte sie auch keine `__hash__()`-Methode definieren.
mutetella hat geschrieben:"... If a class does not define a __cmp__() or __eq__() method it should not define a __hash__() operation either; ..."
Ich bin mir nicht sicher, wie das zu übersetzen ist:
- Wenn keine '__cmp__' oder '__eq__' definiert ist, sollte auch keine '__hash__' definiert werden
oder
- Wenn keine '__cmp__' oder '__eq__' definiert ist, sollte dafür (also zum Vergleich mit 'is' / '==') nicht '__hash__' verwendet werden
Die erste Variante ist richtig. "not ... either" heißt übersetzt "auch keine".
Das macht ja auch Sinn, wenn man die Erläuterungen komplett liest (und versteht). Da würde man dann auch sehen, dass deine `__hash__()`-Methode überflüssig ist, da sie standardmäßig bereits in dieser Form implementiert ist.
snafu hat geschrieben:Da würde man dann auch sehen, dass deine `__hash__()`-Methode überflüssig ist, da sie standardmäßig bereits in dieser Form implementiert ist.
Aber nicht, wenn von einer Klasse abgeleitet wird, die '__hash__' auf None setzt, wie das z. B. bei 'list' offensichtlich der Fall ist.
snafu hat geschrieben:"hashable" sollten demnach also nur unveränderliche Objekte (z.B. Strings) sein.
Schon klar... Ich suche halt eine vernünftige Lösung, wie ich eine Liste als solche als set-Element verwenden kann und dadurch den set-Vorteil nutze, dass set-Elemente einmalig enthalten sind.
BlackJack hat geschrieben:Kannst Dir ja jetzt überlegen wo die vorhandene Vergleichsmethode von Listen den Vertrag für das Funktionieren von Hash-Tabellen verletzt.
Das wird dann wohl meine Fleißaufgabe werden...
Wobei ich nicht verstehe, weshalb ich '__eq__' oder '__cmp__' denn nochmals implementieren sollte:
In [63]: years = picker.Picker('year')
In [64]: years.pick(2011)
In [65]: years
Out[65]: [2011]
In [66]: years == [2011]
Out[66]: True
In [67]: years is [2011]
Out[67]: False
Und wenn dem so ist, wo könnte eine Kollission stattfinden?
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit )
mutetella hat geschrieben:Schon klar... Ich suche halt eine vernünftige Lösung, wie ich eine Liste als solche als set-Element verwenden kann und dadurch den set-Vorteil nutze, dass set-Elemente einmalig enthalten sind.
Sieht mir nicht nach klar, sondern nach konfus aus
Es gibt ja einen guten Grund, warum listen nicht hashable sind. Nehmen wir mal einen Moment an sie waeren es. Was sagt uns denn dann dieses Beispiel:
>>> a = [1, 2, 3]
>>> b = [1, 2]
>>> c = [1, 2]
>>> set([a, b, c])
set([[1, 2, 3], [1, 2]]) # ein Element faellt weg
>>> b.append(3)
Was soll denn nun genau passieren? Mengen machen ja nur dann Sinn, wenn sie Aequivalenzklassen bilden. Das wird aber schwer, wenn die Klassen selbst bewegliche Ziele sind.
>>> a = HashableList((1,2))
>>> b = HashableList((1,2))
>>> s = set((a,b))
>>> s
set([[1, 2], [1, 2]])
>>> a.append(3)
>>> s.add(a)
>>> s
set([[1, 2], [1, 2, 3]])
>>> b.append(4)
>>> s.add(b)
>>> s
set([[1, 2, 3], [1, 2, 4]])
>>> b[2] = 3
>>> s.add(b)
>>> s
set([[1, 2, 3], [1, 2, 3]])
>>> s.remove(b)
>>> s
set([[1, 2, 3]])
Konkret geht es mir darum, dass ich Listen (Picker) habe, die ich nach jeder Änderung einfach ohne weitere Prüfung, ob schon vorhanden oder nicht, einem set zufügen möchte.
Was ist so verwegen daran?
mutetella
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit )
Es ist halt Unsinn im Kontext einer Liste. Wenn du sowas willst, bau dir halt ein Objekt "Handle", was das macht. Kann ja ne Liste als Attribut haben. Damit hast du hash und == so definiert, wie sie sein sollen - ueber die ID.
Listen haber haben einen Vergleichsoperator, der dann nicht konform geht mit deiner Hash-Funkjtion. Denn fuer hashes muss (im sinne von "sollte, wirklich, ganz in echt") gelten:
a == b => hash(a) == hash(b)
Wenn das verletzt ist, kommst du in Schwulitaeten. Und deine Mengen-OPs sind genau sowas - die Erwartung ist, das
Aber mal von Anfang an: set's sind dazu da ein Menge zu speichern. Was sind also nun Mengen? Mengen sind dazu da um zu unterscheiden, ob etwas dazu gehört, oder nicht. Beispiel: Die Menge der angemeldeten User, oder die gezogenen Lottozahlen (6 aus 49).
Was sind hingegen Listen? Listen enthalten sortiert Elemente. Zum Beispiel die Beiträge zu einem Thema. Oder beim Gewinnspiel Super 6.
Wie sind set's und Listen implementiert.
Zuerst zu den Listen: In CPython wird das über Arrays realisiert. Das heißt ich erzeuge eine Liste und Python legt mir dann ein Array an, das noch Elemente aufnehmen kann. Wird das Arrays zu klein, wird ein größeres Arrays erstellt und die Werte kopiert. Hier liegt der große Vorteil beim Zugriff auf den Index der konstant ist. Klassischerweise sind Listen eine Reihe von Elementen. Das heißt ein Indexzugriff bedeutet eine Iteration über die Elemente. Die Zugriffszeit ist also linear beim Indexzugriff.
Bei den set's sieht das anders aus: Über die hash-Funktion wird ein int-Wert ermittelt. Bei ints sind sie es gleich selbst. Hashtables funktionieren nun so, dass über ein mathematisches Verfahren aus der Zahl sich ein Speicherplatz ergibt. Es kann aber nun aus zwei Gründen zu Kollisionen kommen. Erstens zwei Objekte liefern den gleichen hash. Das geht ganz einfach. Wir bilden den hash von einem Objekt und erhalten z.B. die Zahl `1234`. Nun hat unser Objekt den gleichen hash-Wert wie die selbe Zahl `1234`. Zweitens: Aus zwei verschiedenen Hashwerten ergibt sich der gleiche Speicherbereich.
Es muss also zu jedem Speicherbereich eine Liste zugeordnet werden die dann durchgegangen wird. Deshalb ist die Zugriffszeit nicht ganz konstant.
Beim iterieren der Liste werden dann die Objekte verglichen, ob sie gleich sind. Daher auch der Sinn der __eq__ Methode. Ich meine sonst nimmt sie die id eines Objektes und vergleicht die. Warum das ein Problem ist? Nehmen wir an, wir haben ein Tupel (1,2) im set gespeichert. Nun will ich überprüfen, ob es darin enthalten ist. Es muss also der Hash ermittelt werden. Jetzt wird nachgeschaut, was unter dem Hashwert gespeichert ist und die Liste wird durchgegangen. Nun wird jedes Element verglichen. Und da ist der Punkt. Das Tupel, was im set gespeichert ist hat eine andere id. Ohne __eq__ würde die Gleichheit nicht festgestellt werden.
Warum können nun keine Listen im set gespeichert werden. Würden sich die Listen nicht verändern, dann wäre das kein Problem (dafür gibts ja tupel - quasi frozenlists). Der Hashwert ergibt sich nämlich aus den Elementen des tuples. Das heißt, eine Liste, die sich verändert, würde den hash-Wert verändern. Die Liste wäre dann im set nicht mehr auffindbar. Der Vergleich würde ja noch klappen, aber die Liste wäre im set unter der falschen Adresse gespeichert. Man könnte zwar jetzt einfach bei allen Listen den gleichen hash-Wert zurückgeben, hat dann aber quasi nur eine Liste von Listen und dafür braucht man kein set.
Dann gibt es noch dicts. Die funktionieren genauso wie sets, nur dass sie zu einem Key einen Value mit abspeichern.
Was du machst, ist die sets zu missbrauchen.
[url=http://wiki.python-forum.de/PEP%208%20%28%C3%9Cbersetzung%29]PEP 8[/url] - Quak!
[url=http://tutorial.pocoo.org/index.html]Tutorial in Deutsch[/url]
)
