Hashing niezmiennego słownika w Pythonie

Krótka wersja: Jaki jest najlepszy algorytm mieszania dla multisetu zaimplementowanego jako słownik elementów nieuporządkowanych?

Próbuję zmieścić niezmienny multiset (który jest torbą lub multisetem w innych językach: jak zestaw matematyczny, z wyjątkiem tego, że może pomieścić więcej niż jeden element) zaimplementowany jako słownik. Stworzyłem podklasę standardowej klasy bibliotekicollections.Counter, podobnie jak tutaj:Wymowne dyktaty Pythona, który zaleca taką funkcję skrótu:

<code>class FrozenCounter(collections.Counter):
    # ...
    def __hash__(self):
        return hash(tuple(sorted(self.items())))
</code>

Tworzenie pełnej krotki elementów zajmuje dużo pamięci (w stosunku do, powiedzmy, użycia generatora), a mieszanie wystąpi w niezwykle intensywnej pamięci części mojej aplikacji. Co ważniejsze, moje klucze słownikowe (elementy wielosegmentowe) prawdopodobnie nie będą możliwe do zamówienia.

Myślę o użyciu tego algorytmu:

<code>def __hash__(self):
    return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
</code>

Obliczam użycie bitowych środków XORkolejność nie ma znaczenia dla wartości mieszania w przeciwieństwie do mieszania w krotce? Przypuszczam, że mógłbym na półimplementować algorytm mieszający krotki Pythona w nieuporządkowanym strumieniu krotek moich danych. Widziećhttps://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (szukaj na stronie słowa „hash”) - ale ledwo znam C, aby go przeczytać.

Myśli? Propozycje? Dzięki.

(Jeśli zastanawiasz się, dlaczego bawię się próbami skrócenia multisetu: Dane wejściowe dla mojego problemu to zestawy multisetów, a w każdym zestawie multisetów każdy multiset musi być unikalny. Pracuję nad terminem i nie jestem doświadczonym koderem, więc chciałem uniknąć wymyślania nowych algorytmów tam, gdzie to możliwe. Wydaje się, że najbardziej Pythonicznym sposobem na upewnienie się, że mam unikatowy zestaw rzeczy, jest umieszczenie ich wset(), ale rzeczy muszą być dostępne.)

Co zebrałem z komentarzy

Zarówno @marcin, jak i @senderle dali prawie taką samą odpowiedź: użyjhash(frozenset(self.items())). To ma sens, ponieważitems() „widoki” są podobne do zestawu. @marcin był pierwszy, ale dałem znak zaznaczenia @senderle z powodu dobrych badań nad czasem pracy big-O dla różnych rozwiązań. @marcin także mi przypominazawierać__eq__ metoda - ale ten odziedziczony podict będzie działać dobrze. W ten sposób wdrażam wszystko - mile widziane są dalsze komentarze i sugestie oparte na tym kodzie:

<code>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
</code>

questionAnswers(2)

yourAnswerToTheQuestion