Als Übung und hauptsächlich zu meiner eigenen Unterhaltung implementiere ich einen Backtracking-Packrat-Parser. Die Inspiration dafür ist, dass ich eine bessere Vorstellung davon haben möchte, wie hygienische Makros in einer algolähnlichen Sprache funktionieren würden (im Gegensatz zu den syntaxfreien Lisp-Dialekten, in denen sie normalerweise vorkommen). Aus diesem Grund werden bei unterschiedlichen Durchläufen durch die Eingabe möglicherweise unterschiedliche Grammatiken angezeigt, sodass zwischengespeicherte Analyseergebnisse ungültig sind, es sei denn, ich speichere auch die aktuelle Version der Grammatik zusammen mit den zwischengespeicherten Analyseergebnissen. ( BEARBEITEN : Eine Konsequenz dieser Verwendung von Schlüsselwertsammlungen ist, dass sie unveränderlich sein sollten, aber ich beabsichtige nicht, die Schnittstelle verfügbar zu machen, damit sie geändert werden können, sodass entweder veränderbare oder unveränderliche Sammlungen in Ordnung sind.)
Das Problem ist, dass Python-Dikte nicht als Schlüssel für andere Dikte angezeigt werden können. Selbst die Verwendung eines Tupels (wie ich es sowieso tun würde) hilft nicht.
>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
Ich denke, es müssen ganz unten Tupel sein. Jetzt bietet die Python-Standardbibliothek ungefähr das, was ich brauche, collections.namedtuple
hat eine ganz andere Syntax, kann aber als Schlüssel verwendet werden. Fortsetzung der obigen Sitzung:
>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}
OK. Aber ich muss eine Klasse für jede mögliche Kombination von Schlüsseln in der Regel erstellen, die ich verwenden möchte, was nicht so schlimm ist, da jede Analyseregel genau weiß, welche Parameter sie verwendet, damit die Klasse gleichzeitig definiert werden kann als die Funktion, die die Regel analysiert.
Bearbeiten: Ein zusätzliches Problem mit namedtuple
s ist, dass sie streng positionell sind. Zwei Tupel, die so aussehen, als ob sie unterschiedlich sein sollten, können tatsächlich gleich sein:
>>> you = namedtuple("foo",["bar","baz"])
>>> me = namedtuple("foo",["bar","quux"])
>>> you(bar=1,baz=2) == me(bar=1,quux=2)
True
>>> bob = namedtuple("foo",["baz","bar"])
>>> you(bar=1,baz=2) == bob(bar=1,baz=2)
False
tl'dr: Wie bekomme ich dict
s, die als Schlüssel für andere verwendet werden können ?dict
s verwendet werden können?
Nachdem ich die Antworten ein wenig gehackt habe, ist hier die vollständigere Lösung, die ich verwende. Beachten Sie, dass dies ein wenig zusätzliche Arbeit leistet, um die resultierenden Diktate für praktische Zwecke vage unveränderlich zu machen. Natürlich ist es immer noch recht einfach, sich durch einen Anruf darum zu kümmern, dict.__setitem__(instance, key, value)
aber wir sind alle Erwachsene hier.
class hashdict(dict):
"""
hashable dict implementation, suitable for use as a key into
other dicts.
>>> h1 = hashdict({"apples": 1, "bananas":2})
>>> h2 = hashdict({"bananas": 3, "mangoes": 5})
>>> h1+h2
hashdict(apples=1, bananas=3, mangoes=5)
>>> d1 = {}
>>> d1[h1] = "salad"
>>> d1[h1]
'salad'
>>> d1[h2]
Traceback (most recent call last):
...
KeyError: hashdict(bananas=3, mangoes=5)
based on answers from
http://stackoverflow.com/questions/1151658/python-hashable-dicts
"""
def __key(self):
return tuple(sorted(self.items()))
def __repr__(self):
return "{0}({1})".format(self.__class__.__name__,
", ".join("{0}={1}".format(
str(i[0]),repr(i[1])) for i in self.__key()))
def __hash__(self):
return hash(self.__key())
def __setitem__(self, key, value):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def __delitem__(self, key):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def clear(self):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def pop(self, *args, **kwargs):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def popitem(self, *args, **kwargs):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def setdefault(self, *args, **kwargs):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
def update(self, *args, **kwargs):
raise TypeError("{0} does not support item assignment"
.format(self.__class__.__name__))
# update is not ok because it mutates the object
# __add__ is ok because it creates a new object
# while the new object is under construction, it's ok to mutate it
def __add__(self, right):
result = hashdict(self)
dict.update(result, right)
return result
if __name__ == "__main__":
import doctest
doctest.testmod()
hashdict
muss unveränderlich sein, zumindest nachdem Sie mit dem Hashing begonnen haben. Warum also nicht die Wertekey
undhash
als Attribute deshashdict
Objekts zwischenspeichern? Ich habe__key()
und modifiziert und__hash__()
getestet, um zu bestätigen, dass es viel schneller ist. SO erlaubt keinen formatierten Code in Kommentaren, also werde ich ihn hier verlinkenAntworten:
Hier ist der einfache Weg, um ein Hash-Wörterbuch zu erstellen. Denken Sie daran, sie nach dem Einbetten in ein anderes Wörterbuch aus offensichtlichen Gründen nicht zu mutieren.
quelle
O(n*log(n))
bei dern
die Anzahl derdict
Einträge angegeben ist. Weiß jemand, ob Pythonsfrozenset
Hash-Funktion in linearer Zeit ausgeführt wird?dict(key1=value1, key2=value2,...)
oder so erstellt werdendict([(key1, value1), (key2, value2),...)])
. Gleiches gilt für diesen. Die Kreation, die Sie gepostet haben, heißt wörtlichhashabledict({key_a: val_a, key_b: val_b, ...})
.Hashables sollten unveränderlich sein - dies nicht erzwingen, sondern darauf vertrauen, dass Sie ein Diktat nach seiner ersten Verwendung als Schlüssel nicht mutieren. Der folgende Ansatz würde funktionieren:
Wenn Sie Ihre Diktate mutieren müssen und sie NOCH als Schlüssel verwenden möchten, explodiert die Komplexität hundertfach - um nicht zu sagen, dass dies nicht möglich ist, aber ich werde bis zu einem SEHR spezifischen Hinweis warten, bevor ich in DIESEN unglaublichen Morast gerate! -)
quelle
sorted
Schlüssel in __ ;-).Alles, was benötigt wird, um Wörterbücher für Ihren Zweck nutzbar zu machen, ist das Hinzufügen einer __hash__ -Methode:
Beachten Sie, dass die Frozenset- Konvertierung für alle Wörterbücher funktioniert (dh die Schlüssel müssen nicht sortierbar sein). Ebenso gibt es keine Einschränkung für die Wörterbuchwerte.
Wenn es viele Wörterbücher mit identischen Schlüsseln, aber unterschiedlichen Werten gibt, muss der Hash die Werte berücksichtigen. Der schnellste Weg dazu ist:
Dies ist schneller als
frozenset(self.iteritems())
aus zwei Gründen. Zunächst verwendet derfrozenset(self)
Schritt die im Wörterbuch gespeicherten Hash-Werte erneut und speichert unnötige Aufrufe vonhash(key)
. Zweitens greift die Verwendung von itervalues direkt auf die Werte zu und vermeidet die vielen Speicherzuweisungsaufrufe, die von Elementen verwendet werden , um bei jeder Suche viele neue Schlüssel- / Wertetupel im Speicher zu bilden.quelle
dict
, dass die Hash-Werte der Schlüssel nicht zwischengespeichert werden - obwohl einzelne Klassen (wiestr
) ihre Hashes zwischenspeichern können und dies auch tun. Zumindest beim Erstellen einerdict
mit meinen benutzerdefinierten Klasseninstanzen als Schlüssel verwendeten Instanz wurden deren__hash__
Methoden bei jeder Zugriffsoperation aufgerufen (Python 3.4). Unabhängig davon, ob ich richtig bin oder nicht, bin ich mir nicht sicher, wiehash(frozenset(self))
die vorberechneten Hashwerte wiederverwendet werden können, es sei denn, sie werden in den Schlüsseln selbst zwischengespeichert (in diesem Fall werdenhash(frozenset(self.items())
sie auch wiederverwendet).{'one': 1, 'two': 2}
und{'one': 2, 'two': 1}
__missing__
abzuleiten. Was denken Sie?Die gegebenen Antworten sind in Ordnung, aber sie könnten verbessert werden, indem der Hash
frozenset(...)
anstelle vontuple(sorted(...))
generiert wird:Der Leistungsvorteil hängt vom Inhalt des Wörterbuchs ab, aber in den meisten Fällen, die ich getestet habe, ist das Hashing mit
frozenset
mindestens zweimal schneller (hauptsächlich, weil es nicht sortiert werden muss).quelle
hash(frozenset(d))
.hash(frozenset(d))
führt zu identischen Hashes für 2 Diktate mit ähnlichen Schlüsseln, aber unterschiedlichen Werten!frozenset(d.itervalues())
. In Fällen, in denen Diktate unterschiedliche Schlüssel haben,frozenset(d)
ist dies viel schneller und schränkt die Hashfähigkeit von Schlüsseln nicht ein. Denken Sie zum Schluss daran, dass die Methode dict .__ eq__ viel schneller nach gleichen Schlüssel / Wert-Paaren sucht, als der Hash für alle Schlüssel / Wert-Paar-Tupel berechnet werden kann. Die Verwendung von Schlüssel- / Wertetupeln ist ebenfalls problematisch, da die gespeicherten Hashes für alle Schlüssel weggeworfen werden (deshalbfrozenset(d)
ist dies so schnell).Eine einigermaßen saubere, unkomplizierte Implementierung ist
quelle
__iter__
und__len__
.__iter__
und__len__
weil ich muss, da ich ableitecollections.Mapping
; Wie man es benutzt,collections.Mapping
wird in der Dokumentation des Sammlungsmoduls ziemlich gut behandelt. Andere Menschen haben kein Bedürfnis danach, da sie ableitendict
. Ausdict
einem anderen Grund abzuleiten als zu definieren,__missing__
ist eine schlechte Idee. Die Diktatspezifikation sagt nicht aus, wie Diktat in einem solchen Fall funktioniert, und in Wirklichkeit wird dies Tonnen von nicht virtuellen Methoden enthalten, die im Allgemeinen weniger nützlich sind und in diesem speziellen Fall Restmethoden mit irrelevantem Verhalten haben.Ich komme immer wieder auf dieses Thema zurück ... Hier ist eine weitere Variante. Es ist mir unangenehm, eine Unterklasse
dict
hinzuzufügen, um eine__hash__
Methode hinzuzufügen . Es gibt praktisch kein Entrinnen vor dem Problem, dass Diktate veränderlich sind, und das Vertrauen, dass sie sich nicht ändern, scheint eine schwache Idee zu sein. Also habe ich stattdessen versucht, ein Mapping basierend auf einem eingebauten Typ zu erstellen, der selbst unveränderlich ist. obwohltuple
eine naheliegende Wahl ist, impliziert der Zugriff auf Werte eine Sortierung und eine Halbierung. Kein Problem, aber es scheint nicht viel von der Kraft des Typs zu nutzen, auf dem es aufgebaut ist.Was ist, wenn Sie einen Schlüssel blockieren und Wertepaare in a
frozenset
? Was würde das erfordern, wie würde es funktionieren?Teil 1, Sie benötigen eine Möglichkeit, die Elemente so zu codieren, dass ein Frozenset sie hauptsächlich anhand ihrer Schlüssel behandelt. Ich werde eine kleine Unterklasse dafür machen.
Das allein bringt Sie in die Nähe einer unveränderlichen Zuordnung:
D'oh! Wenn Sie die Set-Operatoren verwenden, sind die Elemente leider gleich, aber nicht dasselbe Objekt. Was im Rückgabewert endet, ist undefiniert . Wir müssen noch einige Drehungen durchlaufen.
Das Nachschlagen von Werten auf diese Weise ist jedoch umständlich und führt schlimmer noch zu vielen Zwischensätzen. das geht nicht! Wir werden ein 'falsches' Schlüssel-Wert-Paar erstellen, um es zu umgehen:
Was zu weniger problematischen Ergebnissen führt:
Das ist die ganze tiefe Magie; Der Rest packt alles in etwas ein, das eine Schnittstelle wie ein Diktat hat. Da wir eine Unterklasse von haben
frozenset
, die eine ganz andere Oberfläche hat, gibt es ziemlich viele Methoden; Wir bekommen ein wenig Hilfe voncollections.Mapping
, aber der größte Teil der Arbeit überschreibtfrozenset
stattdessen die Methoden für Versionen, die wie Diktate funktionieren:was letztendlich meine eigene Frage beantwortet:
quelle
Die akzeptierte Antwort von @Unknown sowie die Antwort von @AlexMartelli funktionieren einwandfrei, jedoch nur unter den folgenden Einschränkungen:
hash(hashabledict({'a':[1,2]}))
wird erhöhenTypeError
.hash(hashabledict({'a':'a', 1:1}))
wird erhöhenTypeError
.frozenset((1,2,3))
und sindfrozenset((4,5,6))
, werden sie in beide Richtungen ungleich verglichen. Das Sortieren der Elemente eines Wörterbuchs mit solchen Schlüsseln kann daher zu einer beliebigen Reihenfolge führen und verstößt daher gegen die Regel, dass gleiche Objekte denselben Hashwert haben müssen.Die viel schnellere Antwort von @ObenSonne hebt die Einschränkungen 2 und 3 auf, ist jedoch weiterhin an die Einschränkung 1 gebunden (Werte müssen hashbar sein).
Die schnellere und dennoch antwortende Antwort von @RaymondHettinger hebt alle drei Einschränkungen auf, da sie nicht
.values()
in die Hash-Berechnung einbezogen wird. Die Leistung ist jedoch nur dann gut, wenn:.keys()
.Wenn diese Bedingung nicht erfüllt ist, ist die Hash-Funktion weiterhin gültig, kann jedoch zu viele Kollisionen verursachen. Im Extremfall, in dem alle Wörterbücher aus einer Website-Vorlage generiert werden (Feldnamen als Schlüssel, Benutzereingabe als Werte), sind die Schlüssel immer gleich und die Hash-Funktion gibt für alle Eingaben den gleichen Wert zurück . Infolgedessen wird eine Hashtabelle, die auf einer solchen Hash-Funktion basiert, beim Abrufen eines Elements (
O(N)
anstelle vonO(1)
) so langsam wie eine Liste .Ich denke, die folgende Lösung wird einigermaßen gut funktionieren, selbst wenn alle 4 oben aufgeführten Einschränkungen verletzt werden. Es hat den zusätzlichen Vorteil, dass es nicht nur Wörterbücher, sondern auch alle Container hashen kann, selbst wenn sie veränderbare veränderbare Container haben.
Ich würde mich über jedes Feedback sehr freuen, da ich dies bisher nur leicht getestet habe.
quelle
Möglicherweise möchten Sie auch diese beiden Methoden hinzufügen, damit das v2-Beizprotokoll mit Hashdict-Instanzen funktioniert. Andernfalls versucht cPickle, hashdict .____ setitem____ zu verwenden, was zu einem TypeError führt. Interessanterweise funktioniert Ihr Code mit den beiden anderen Versionen des Protokolls einwandfrei.
quelle
Wenn Sie keine Zahlen in das Wörterbuch aufnehmen und die Variablen mit Ihren Wörterbüchern nie verlieren, können Sie Folgendes tun:
cache[id(rule)] = "whatever"
da id () für jedes Wörterbuch eindeutig ist
BEARBEITEN:
Oh sorry, ja in diesem Fall wäre das, was die anderen sagten, besser. Ich denke, Sie könnten Ihre Wörterbücher auch als Zeichenfolge serialisieren
cache[ 'foo:bar' ] = 'baz'
Wenn Sie Ihre Wörterbücher jedoch von den Schlüsseln wiederherstellen müssen, müssen Sie etwas Hässlicheres tun
cache[ 'foo:bar' ] = ( {'foo':'bar'}, 'baz' )
Ich denke, der Vorteil davon ist, dass Sie nicht so viel Code schreiben müssten.
quelle
cache[id({'foo':'bar'})] = 'baz'; id({'foo':'bar'}) not in cache
Fähigkeit, Schlüssel dynamisch zu erstellen, ist wichtig, wenn ich überhaupt Diktate als Schlüssel verwenden möchte.