Wstrzymywanie niezmiennego słownika w języku Python

Question

Skrócona wersja: Jaki jest najlepszy algorytm mieszający dla multiset zaimplementowany jako słownik nieuporządkowanych elementów?

Próbuję zaimplementować niezmienny multiset (który jest workiem lub multiset 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. Utworzyłem podklasę klasy standardowej biblioteki collections.Counter, podobną do rad tutaj: Python hashable dicts, zalecający funkcja hash tak:

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

Tworzenie pełnej krotka pozycje zajmuje dużo pamięci (względne na przykład przy użyciu generatora), a haszowanie wystąpi w bardzo intensywnej pamięci mojej aplikacji. Co ważniejsze, moje klucze słownikowe (elementy multiset) prawdopodobnie nie będą mogły być zamawiane.

mam na myśli używając tego algorytmu:

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

I postać używając bitowe XOR oznacza kolejność nie ma znaczenia dla wartości hash w przeciwieństwie wycieniowanie krotki? Przypuszczam, że mógłbym częściowo implementować algorytm mieszający Pythona na nieuporządkowanym strumieniu krotek moich danych. Zobacz https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (szukaj na stronie dla słowa "hash") - ale ledwie znam wystarczającą literę C, aby ją przeczytać.

Myśli? Propozycje? Dzięki.

---

( Jeśli zastanawiasz się, dlaczego jestem aprowizacji z próby mieszania się MultiSet: Dane wejściowe do mojego problemu to zestawy multisets, a wewnątrz każdego zestawu multisets każdy multiset musi być unikalny ja. Pracuję nad terminem i nie jestem doświadczonym programistą, więc chciałem uniknąć wymyślania nowych algorytmów, gdzie to możliwe. Wydaje mi się, że najbardziej Pythonicznym sposobem na upewnienie się, że mam unikatowy zestaw rzeczy jest umieszczenie ich w set(), ale te rzeczy muszą być hashable.)

---

Co mam zebrane z uwagami

Zarówno @marcin, jak i @senderle dały podobną odpowiedź: użyj hash(frozenset(self.items())). Ma to sens, ponieważ items() "views" are set-like. @marcin był pierwszy, ale dałem znak kontrolny @senderle z powodu dobrych badań na temat dużych czasów pracy dla różnych rozwiązań. @marcin również przypomina mi include an __eq__ method - ale ten odziedziczony po dict będzie działał dobrze. W ten sposób mam wdrażaniu wszystko - dalsze komentarze i sugestie na podstawie niniejszego kodeksu są mile widziane:

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 

Answer 1

Ponieważ słownik jest niezmienne, można utworzyć skrót gdy słownik tworzony jest i przesłać go bezpośrednio. Moja sugestia byłaby stworzenie frozenset z items (w 3 +; iteritems w 2.7), hash to i przechowywać hasz.

Aby zapewnić wyraźny przykład:

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

celu wyjaśnienia dlaczego wolę frozenset do krotki brakowanych elementów: a frozenset nie trzeba sortować elementy (ponieważ są one trwale uporządkowane według ich hash w pamięci), a więc początkowy skrót powinien kończyć się w czasie O (n), a nie w czasie O (n log n).Widać to z implementacji frozenset_hash i set_next.

Answer 2

Czy brałeś pod uwagę hash(sorted(hash(x) for x in self.items()))? W ten sposób sortujesz tylko liczby całkowite i nie musisz tworzyć listy.

Moglibyśmy także zhaczyć żywioły elementów razem, ale szczerze mówiąc, nie wiem, jak dobrze by to działało (czy miałbyś dużo kolizji?). Mówiąc o kolizjach, nie musisz implementować metody __eq__?

Alternatywnie, podobna do mojej odpowiedzi here, hash(frozenset(self.items())).