짧은 버전 : 정렬되지 않은 항목의 사전으로 구현 된 멀티 세트에 가장 적합한 해싱 알고리즘은 무엇입니까?불변의 사전을 파이썬으로 해싱
저는 불변 멀티 세트 (다른 언어로 된 백 또는 멀티 세트입니다 : 수학적 세트와 같이 각 요소를 둘 이상 가질 수 있다는 점을 제외하고)을 사전으로 구현했습니다. 상대
class FrozenCounter(collections.Counter):
# ...
def __hash__(self):
return hash(tuple(sorted(self.items())))
항목의 전체 튜플을 생성 메모리를 많이 차지 (: Python hashable dicts, 해시 함수과 같이 권고한다 : 나는 여기에 조언 유사한 표준 라이브러리 클래스 collections.Counter의 서브 클래스를 만들었습니다 생성기를 사용하여), 해시는 응용 프로그램의 메모리 사용량이 많은 부분에서 발생합니다. 더 중요한 것은, 내 사전 키 (multiset 요소) 아마 주문할 수 없습니다.
나는이 알고리즘을 사용하여 생각 해요 : 내가 사용 피겨
def __hash__(self):
return functools.reduce(lambda a, b: a^b, self.items(), 0)
비트 XOR은 튜플의 해시 달리 해시 값에 대한 문제가되지 않습니다 순서를 의미? 필자는 데이터의 튜플 (tuples)의 순서가없는 스트림에 Python 튜플 해싱 알고리즘을 세미 구현할 수 있다고 가정합니다. https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h ('hash'라는 단어를 찾으려면 페이지에서 검색)을 참조하십시오. - 그러나 나는 그것을 읽는데 충분한 C를 간신히 알고 있습니다.
생각하십니까? 제안? 감사.
( 왜 멀티 세트를 해시하는 데 어지러운지 궁금한 분 : 내 문제의 입력 데이터는 멀티 세트 세트이며 각 멀티 세트는 고유해야합니다. 마감 기한에 근무하고 있고 경험 많은 코더가 아니기 때문에, 가능하면 새로운 알고리즘을 발명하는 것을 피하고 싶었습니다. 내가 생각하기에 가장 복잡한 방법은
set()하지만, 일이 해쉬해야합니다.) 내가 코멘트에서 수집 한 어떤
@marcin과 @senderle 모두 거의 같은 대답을했습니다 : hash(frozenset(self.items()))을 사용하십시오. 이것은 items() "views" are set-like이기 때문에 의미가 있습니다. @marcin이 처음 이었지만 다른 솔루션에 대한 큰 실행 시간에 대한 좋은 연구 때문에 @senderle에 체크 표시를했습니다. @marcin은 또한 include an __eq__ method을 생각 나게합니다. 그러나 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
해시 가능 객체는 모두 주문 가능합니다. 해시 가능하다면 항상 동일한 해시를 생성하므로 해시를 정렬하십시오. – senderle
'튜플 (tuple) '에 많은 메모리가 필요합니까? 그것은 dict의 각 항목에 대한 "포인터"일 뿐이며, 사본은 생성되지 않습니다. – agf
http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html – wkschwartz