練習として、そして主に私自身の楽しみのために、バックトラッキング パックラット パーサーを実装しています。このアイデアのきっかけは、Algol のような言語 (通常、構文フリーの Lisp 方言で使用されているものとは異なります) で hygenic マクロがどのように機能するかについて、もっとよく理解したいと思ったことです。このため、入力をパスするたびに異なる文法が使用される可能性があるため、キャッシュされた解析結果は、キャッシュされた解析結果とともに現在のバージョンの文法も保存しない限り無効になります。(編集: キー値コレクションのこの使用法の結果として、それらは不変である必要がありますが、変更できるようにインターフェイスを公開するつもりはないので、可変コレクションでも不変コレクションでもどちらでも問題ありません)
問題は、Python 辞書が他の辞書のキーとして表示できないことです。タプルを使用しても (いずれにしてもそうするでしょうが) 役に立ちません。
>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
全部タプルでなければならないと思います。Pythonの標準ライブラリは、私が必要とするものをほぼ提供しており、collections.namedtuple
構文は非常に異なりますが、できるキーとして使用されます。上記のセッションから続行します。
>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}
わかりました。しかし、使用したいルール内のキーの可能な組み合わせごとにクラスを作成する必要があります。これはそれほど悪いことではありません。各解析ルールは使用するパラメータを正確に認識しているため、そのクラスはルールを解析する関数と同時に定義できます。
編集: s のもう 1 つの問題は、namedtuple
厳密に位置指定であることです。異なるように見える 2 つのタプルが、実際には同じである可能性があります。
>>> 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
dict
要約:他の のキーとして使用できる を取得するにはどうすればよいですかdict
?
回答を少しハックした後、私が使用しているより完全なソリューションを次に示します。これは、実用的な目的で結果の辞書を漠然と不変にするために、少し余分な作業を行うことに注意してください。もちろん、 を呼び出してハックするのはまだ非常に簡単ですdict.__setitem__(instance, key, value)
が、ここでは私たちは全員大人です。
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()
ベストアンサー1
ハッシュ可能な辞書を作成する簡単な方法は次のとおりです。明らかな理由から、別の辞書に埋め込んだ後は変更しないように注意してください。
class hashabledict(dict):
def __hash__(self):
return hash(tuple(sorted(self.items())))