短いバージョン:順序付けされていないアイテムの辞書として実装されたマルチセットに最適なハッシュアルゴリズムは何ですか?
辞書として実装された不変のマルチセット(バッグまたは他の言語のマルチセット:数学セットのように、各要素を複数保持できることを除いて)をハッシュしようとしています。collections.Counter
ここでのアドバイスと同様に、標準ライブラリクラスのサブクラスを作成しました。Pythonハッシュ可能dictsは、次のようなハッシュ関数を推奨します。
class FrozenCounter(collections.Counter):
# ...
def __hash__(self):
return hash(tuple(sorted(self.items())))
アイテムの完全なタプルを作成すると(たとえば、ジェネレーターを使用する場合に比べて)多くのメモリが消費され、アプリケーションの非常にメモリを大量に消費する部分でハッシュが発生します。さらに重要なことに、私の辞書キー(マルチセット要素)はおそらく注文できません。
私はこのアルゴリズムを使用することを考えています:
def __hash__(self):
return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
ビット単位のXORを使用すると、タプルのハッシュとは異なり、ハッシュ値の順序は重要ではないことを意味しますか?データのタプルの順序付けられていないストリームにPythonタプルハッシュアルゴリズムを半実装できると思います。https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.hを参照してください(ページで「ハッシュ」という単語を検索してください)-しかし、私はそれを読むのに十分なCをほとんど知りません。
考え?提案?ありがとう。
(なぜ私がマルチセットをハッシュしようとしているのか疑問に思っている場合:私の問題の入力データはマルチセットのセットであり、マルチセットの各セット内で、各マルチセットは一意である必要があります。私は締め切りに取り組んでいます私は経験豊富なコーダーではないので、可能な限り新しいアルゴリズムを発明することは避けたかったのです。私がたくさんのものを持っていることを確認するための最もPython的な方法は、それらをに入れることです
set()
が、ハッシュ可能。)
コメントから集めたもの
@marcinと@senderleはどちらも、ほぼ同じ答えを出しました。use hash(frozenset(self.items()))
。items()
「ビュー」はセットのように設定されているため、これは理にかなっています。@marcinが最初でしたが、さまざまなソリューションのbig-O実行時間に関する優れた調査のため、@senderleにチェックマークを付けました。@marcinは、メソッドを含める__eq__
ことも通知しますが、から継承されたメソッドはdict
問題なく機能します。これが私がすべてを実装する方法です-このコードに基づくさらなるコメントや提案は大歓迎です:
class FrozenCounter(collections.Counter):
# Edit: A previous version of this code included a __slots__ definition.
# But, from the Python documentation: "When inheriting from a class without
# __slots__, the __dict__ attribute of that class will always be accessible,
# so a __slots__ definition in the subclass is meaningless."
# http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots
# ...
def __hash__(self):
"Implements hash(self) -> int"
if not hasattr(self, '_hash'):
self._hash = hash(frozenset(self.items()))
return self._hash