2D 점을 효율적으로 해싱 할 수 있습니다.

Question

OK, 작업이 이렇게하면 -10^6에서 10^6까지 (x, y) 두 점 (x, y)이있는 점의 좌표가 주어집니다 . 나는 특정 지점이 있는지 여부를 확인해야한다. (x, y) 튜플이 나에게 주어 졌는지 아닌지. 간단히 말해서 특정 점 (2D)이 설정되었는지 여부에 대한 쿼리에 어떻게 대답합니까? 지금까지 내가 생각할 수있는 가장 좋은 점은 std::map<std::pair<int,int>, bool>을 유지하는 것입니다. 포인트가 주어질 때마다 1로 표시됩니다. 로그 타임으로 실행되어야하고 쿼리에 응답하는 방법이 상당히 최적화되어 있지만 더 좋은 방법이 있는지 궁금합니다. 이.

또한 위의 데이터 구조를 hash.I 사용하는 사람이 실제로 어떤 복잡 할 것이라고 말할 수 있다면 기쁠 것입니다. std::map의 복잡성은 O (로그 N)이 될 것입니다. 열쇠의 구조에 관계없이 요소의 크기?

Answer 1

해시 맵을 사용하려면 std::map 대신 std::unordered_map을 사용해야합니다. 이것을 사용하는 제약은 여러분의 값 타입이 in this answer과 같이 정의 된 해시 함수를 가질 필요가 있다는 것입니다. 어느 쪽이든하거나 이것 boost::hash을 사용

std::unordered_map<std::pair<int, int>, boost::hash<std::pair<int, int> > map_of_pairs;

마음과 같이 64 비트 정수의 32 비트 INT 값 저장되는 스프링의 또 다른 방법에서 설명한 바와 같이

uint64_t i64; 
uint32_t a32, b32; 
i64 = ((uint64_t)a32 << 32) | b32; 

this answer. x 및 y 구성 요소는 정수의 상위 및 하위 바이트에 저장 될 수 있으며 std::unordered_map<uint64_t, bool>을 사용할 수 있습니다. 비록 이것이 이전의 방법보다 더 효율적인 지 또는 다른 코드를 생성하는지에 대해서 알고 싶습니다.

Answer 2

각 점을 bool에 매핑하는 대신 세트에 모든 점을 저장하지 않으시겠습니까? 그런 다음 집합을 검색하여 찾고자하는 점이 포함되어 있는지 확인할 수 있습니다. 연관된 bool에 대한 추가 조회를 수행하지 않고 수행하는 작업과 본질적으로 동일합니다. 예를 들어 :

언급 한 바와 같이

pair<int, int> examplePoint = make_pair(0, 0); 
set<pair<int, int>>::iterator it = points.find(examplePoint); 

if (it == points.end()) { 
    // examplePoint not found 
} else { 
    // examplePoint found 
} 

, std::set 일반적으로 균형 이진 검색 트리로 구현되어 있으므로 각 : 다음

set<pair<int, int>> points; 

, 당신이 좋아하는 세트가 특정 지점 포함되어 있는지 여부를 확인하거나 수 없습니다 조회는 O (logn) 시간이 걸립니다.

대신 해시 테이블을 사용하려는 경우 std::set 대신 std::unordered_set을 사용하면됩니다. 좋은 해시 함수를 사용한다고 가정하면 조회가 O (1) 시간까지 빨라집니다. 그러나 이렇게하려면 pair<int, int>에 대한 해시 함수를 정의해야합니다. 다음은 그 예 this 대답에서 가져온 것입니다 :

namespace std { 
template <> struct hash<std::pair<int, int>> { 
    inline size_t operator()(const std::pair<int, int> &v) const { 
     std::hash<int> int_hasher; 
     return int_hasher(v.first)^int_hasher(v.second); 
    } 
}; 

} 

편집 : 신경 끄시 고, 당신이 이미 작동있어보세요!