파이썬 3에서 일치하는 요소를 얻는 방법은 무엇입니까?

Question

필자는 불변 객체로 표현 된 여러 상태에 대해 그래프가 포함 된 Python 프로그램을 작성 중이다. 그래프를 생성하는 프로세스는 각 상태의 여러 복사본을 만듭니다. 다수의 상태가 있으므로, 메모리를 절약하기 위해 최종 그래프 객체에 각 상태의 복사본 하나만 보관하고 싶습니다. 따라서,이 같은 기능을 표준 상태의 집합을 구축하고, 쓰고 싶습니다

def canonicalize(state, canonical_states): 
    if state in canonical_states: 
     state, = (cstate for cstate in canonical_states if cstate == state) 
    else: 
     canonical_states.add(state) 
    return state 

이 함수는 상태를 취하고 그 상태의 "표준"버전을 반환합니다. 이전에 상태가 표시되지 않으면 표준 버전이됩니다.

대략 일정한 시간에 세트 요소를 검색 할 수 있어야하지만이 구현에는 각 조회마다 O (n) 시간이 필요합니다. 더 좋은 방법이 있습니까?

하나의 해결책은 자신에 대한 사전 매핑 요소로 canonical_states을 나타내는 것입니다 (내 대답 참조). 나는 canonical_states의 유형을 바꾸지 않고이 성능을 달성 한 솔루션을 선호합니다. 간단히 말해서

:는 일부 x in S이 S 설정 점을 감안, 요소 S 등이 x == y의 y을 얻을 수있는 방법이 있나요?

Answer 1

각 상태를 자체에 매핑하는 dict에 의해 표준 상태 집합을 나타냅니다. 그러면 코드는 다음과 같이됩니다.

def canonicalize(state, canonical_states): 
    return canonical_states.setdefault(state, state)