집합 구성원을 찾는 효율적인 방법

Question

저는 2^n 벡터로 작업하고 있습니다. N = 3 가능한 값은 :

가

000, 001, 010, 011, 100, 101, 110, 111

가 I가 조합 세트 주어진 가장 효율적인 방법 인 것을 발견하고자

가

말할

000, 001, 100000, 110000, 11

주어진 값이 가능한 세트에 있는지 찾는 방법.

한 가지 방법은 전체 목록을 살펴 보는 것입니다 (무차별 대항력). 다른 하나는 고전적인 검색 방법 중 하나를 사용하는 것입니다. log_2에 대한 이진 검색 등 (N) +1

이 내가 거기에 무엇이 있는지 알고 싶어 확률 방법

하지만 또 다른 방법은, 블룸 필터를 사용하는 것, 즉 비트의 목록을 제공 문자열을 사용하여 멤버쉽을 효율적으로 테스트합니다.

Answer 1

모든 데이터 구조가 작동합니다. 나는 당신의 지역 사전 구조가 무엇이든간에 도달하기 쉽다. 왜냐하면 이것은 간단하고 잘 테스트 된 코드이기 때문이다. 대개 해시입니다. 사전, HashMap 또는 std :: unordered_map과 같이 다른 이름으로 불리는 경우가 많습니다. 때로는 이진 트리입니다. 해시 (Perl), 사전 (Python), HashMap.

"이 문제의 완벽한 데이터 구조"를 롤업하려면 트라이 (trie)의 변형이 필요할 것입니다. 그러나 그로부터 얻을 수있는 최대의 승리는 상당히 작은 요소입니다. 그래서 그것이 필요하다는 것을 알지 못하는 이유는 무엇입니까?

Answer 2

해시 기반의 일종의 세트 (예 : Java의 경우 HashSet)는 상환 시간에 상환 및 조회를 수행하며 이는 점근적인 용어로 얻는 것이 가장 좋습니다.

보트를 밀어 내고 싶은 경우 밀도가 높습니다 (즉, 가능한 비트 문자열의 적절한 비율이 있어야합니다). 그런 다음 정수로 변환하고 비트 필드를 사용합니다. 이것은 또한 일정한 시간이지만 더 빠른 상수입니다.