두 개의 배열 N과 M이 있습니다. N은 일반적으로 M보다 작지만 임의로 크기가 지정됩니다. 가능한 가장 빠른 방법으로 N에있는 요소가 M에도 있는지 알아야합니다.M에 존재하는 N의 원소를 찾기 위해 배열 N과 M을 검색하는 좋은 알고리즘은 무엇입니까?
N은 프로그램의 가능한 인스턴스의 예를 제공하기 위해 N은 크기가 12 단위이고 M은 크기가 1,000 단위 인 배열입니다. 나는 N에있는 어떤 요소가 M에도 존재한다는 것을 알고 싶다. (일치하는 것이 없을 수도있다.) 해결책이 더 병렬적일수록 좋다.
해시 맵을 사용했지만 필자가 원하는만큼 효율적이지 않습니다.
이것을 입력하면 sizeof (N) 개의 독립 스레드에서 M의 이진 검색을 실행하려고 생각했습니다. (CUDA 사용하기) 다른 제안을 환영하지만 어떻게 작동하는지 알 수 있습니다.
1000은 매우 적습니다. 또한 검색을 병렬화하면 증가한 코어 수가 늘어날수록 속도가 빨라집니다. 코어보다 많은 스레드가있는 경우 컨텍스트 전환 및 정보 집계로 인해 응용 프로그램의 속도가 다시 느려집니다.
간단한 해법은 해시 조인을 사용하는 것입니다. M에서 해시 테이블을 만든 다음 N의 요소를 찾습니다 (또는 그 반대로 두 배열이 모두 작기 때문에별로 중요하지 않음).
수정 : 내 의견에 대한 응답으로 내 대답이 너무 많이 변경되지 않습니다. 당신은 당신의 스레드 수가 당신의 프로세서 수와 같을 때까지만 선형 적으로 속도를 올릴 수 있습니다.
병렬 해시 조인을 구현하려는 경우 어렵지 않습니다. X-1 해시 테이블을 작성하여 시작하십시오. 여기서 X는 보유하고있는 스레드/프로세서의 수입니다. 각 요소가 어느 해시 테이블에 있어야 할지를 결정하기 위해 X를 모듈로 한 값을 반환하는 두 번째 해시 함수를 사용하십시오.
검색을 수행 할 때 주 스레드는 각 요소에 보조 해시 함수를 적용하여 그걸로 수색을 위해 넘겨 줘.
그것은 단지 예일뿐입니다. M의 크기는 실행에 따라 다르며 임의로 커질 수 있습니다 (수백만 개의 요소). M의 크기는 한 번에 변경되지 않지만 프로그램은 N과 M을 일종의 작업 단위로 사용하여 일치 항목을 비교 한 후 새 데이터로 채우고 다시 비교합니다. 이상. – jakogut
M의 각 요소에 대해 정렬 된 N에 대해 이진 검색을 수행합니다. 크기가 12 인 정렬되지 않은 N에 대해 선형 검색을 수행하더라도 N에서 M 개의 항목을 찾는 것이 평행합니다.
세트를 사용해야합니다. – FogleBird