제목과 마찬가지로, 나는 큰 상수 배열 N에 존재하는 M의 요소를 찾으려고 노력하고 있습니다. 대부분의 경우 M의 어떤 요소도 N에 존재하지 않으므로 M에서 수행 된 검색의 대다수는 시간 낭비.키 M의 배열과 대상 N의 배열이있는 경우 M을 검색하기 전에 N에 M이 있는지 확인할 수 있습니까?
M의 전체 검색을 수행하기 전에 색인을 만드는 방법을 찾고 있습니다. 광산과 유사한 프로젝트는 M의 모든 요소의 처음 몇 바이트에서 비트 배열을 만들고 비트 수준의 병렬 처리를 활용하여 신속하게 검색 할 수 있습니다. 나는 이것이 어떻게 작동하는지 완전히 이해하지 못합니다.
그래서 M을 불필요하게 검색 할 기회를 줄이기 위해 어떤 트릭을 사용할 수 있습니까?
이것은 주로 언어와 관련이없는 질문이지만 가능하면 완벽해야하며 C++을 사용하고 있습니다.
정확하게이 경우에 사용되는 Bloom filters을 생각해보십시오. 그들은 당신에게 잘못된 반응을 줄 수 있습니다.이 경우 실제 테이블에서 검색해야하지만, 항목이 저장되어 있지 않다면 대부분의 경우 처음부터 알려줄 것입니다.
해시 테이블은 일반적으로 저장소에 가장 적합한 옵션입니다. 그러나 키 공간이 대상의 수보다 훨씬 많으면 해시 충돌이 상당 할 수 있습니다. 여기에 저장된 대상이 실제로보고있는 키인지 확인해야합니다. 키 비교가 비용이 많이 들면 신속하게 요인이 될 수 있습니다.
키 값 N으로 해시 테이블을 만들 수 있습니다. 그 다음이 존재하는 값을 반환하는 경우
는 그런 다음 해시에 액세스하려고 [M은 [I], 즉 (1) (무시 충돌.)
N 당신이를 만드는 고려해 볼 수 있습니다 정적이기 때문에 O입니다 Perfect Hash N의 기능입니다. 은 O (1) 시간을 보장합니다.
알고리즘에 대한 CLR 설명서에는이 장 및 위키 페이지에 대한 장이 나와있어 유용하다고 생각되는 링크가 있습니다.
이지만 너무 복잡하여 유용한 구현을 찾기가 어려울 수 있습니다.
. 구현을 위해 Gperf을보십시오.
예상되는 O (1)과 함께 일반적으로 사용 가능한 해시 테이블을 항상 사용할 수 있습니다.
내가 거기에 있음을 알기 위해 검색하고 싶은 몇 가지 추가 정보를 저장한다고 가정합니다. 어떻게 보관하고 있니?
이 경우에 유용한 B-Tree을 찾을 수 있습니다 (업계 표준 데이터베이스는 일반적으로 그 중 일부 변형을 사용합니다). 색인으로도 사용할 수 있습니다! 그래서, 당신이 검색하고, 당신이 그것을 발견하면, 당신은 그것에 대한 데이터/포인터가 있습니다. 당신은 웹상에서 이것들에 대한 많은 구현을 발견 할 것이다.
좋은 지적; 정적 타겟을 사용하면 완벽한 해시는 충돌을 제거하여 대부분의 해시 문제를 해결할 수 있습니다. – Javier
@Javier : 그들은 "완벽"이라고 부르는 이유가 있다고 생각합니다 :-) –
쿨한데, 들어 본 적이 없습니다. –
아, 완벽합니다. 나는 이것을 받아들이 기 전에 다른 사람들이 생각해 낼 수있는 것을 보 겠지만, 이것은 내가 찾고있는 대답 인 것 같다. 감사! – jakogut
예. 블룸 필터. 그런 다음 N 또는 정렬 M을 정렬하는 방법을 사용하여이를 백업합니다. 둘 중 하나 또는 둘 모두를 정렬하면 중간에 점프하고 끝나기 전에 단락하여 충돌 검사의 복잡성을 줄일 수 있습니다. – Jason