17

短いバージョン:順序付けされていないアイテムの辞書として実装されたマルチセットに最適なハッシュアルゴリズムは何ですか?

辞書として実装された不変のマルチセット(バッグまたは他の言語のマルチセット:数学セットのように、各要素を複数保持できることを除いて)をハッシュしようとしています。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
4

2 に答える 2

13

辞書は不変であるため、辞書の作成時にハッシュを作成して直接返すことができます。私の提案は、frozensetfrom items(3+で; iteritems2.7で)を作成し、それをハッシュして、ハッシュを保存することです。

明確な例を提供するには:

>>>> frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems())
frozenset([(3, 2), (1, 3), (4, 1), (2, 1)])
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems()))
-3071743570178645657
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 4]).iteritems()))
-6559486438209652990

frozensetソートされたアイテムのタプルよりもaを好む理由を明確にするために、 aはアイテムfrozensetをソートする必要がないため、初期ハッシュはO(n log n)時間ではなくO(n)時間で完了します。frozenset_hashこれは、とのset_next実装から見ることができます。

ハッシュ関数の実装について説明しているRaymondHettingerからのこのすばらしい回答も参照してください。frozensetそこで彼は、ハッシュ関数が安定した順序に依存しない値を取得するために値をソートする必要を回避する方法を明示的に説明しています。

于 2012-04-06T15:37:47.493 に答える
1

考えたことはありhash(sorted(hash(x) for x in self.items()))ますか?そうすれば、整数をソートするだけで、リストを作成する必要はありません。

要素のハッシュを一緒に排他的論理和することもできますが、率直に言って、それがどれほどうまく機能するかはわかりません(衝突がたくさんありますか?)。衝突といえば、メソッドを実装する必要はありません__eq__か?

または、ここでの私の答えと同様に、hash(frozenset(self.items()))

于 2012-04-06T15:39:14.127 に答える