큰 단어 목록에서 단어 집합을 찾는 알고리즘

Question

9 백만 레코드 목록에서 다른 단어 집합과 일치하는 단어 집합을 찾을 수있는 가장 빠른 알고리즘을 찾고 있습니다.

문제점 : 거의 10 만 세트의 단어 목록이 있으며 9 백만 단어 세트의 다른 목록에있는 단어 세트 각각을 검색해야합니다.

현재의 솔루션은 이렇게되고 텍스트 파일의 모든 레코드를 읽고 배열 형태로 메모리에 보관합니다 (검색 목록이라고합시다). 이 배열을 만드는 동안 나는 알파벳 순서로 단어 집합을 정렬하고 모든 단어 집합이 추가되면 전체 목록을 정렬합니다. 나는 다른 큰 목록과 동일하게, '데이터 목록'이라고 부르 자.

이제 검색 목록의 각 요소를 반복하여 일치하는 항목을 찾으려고합니다. 일치 항목이 발견되면 일치하는 위치와 동일한 위치에서 수행하는 다음 검색을 기억합니다. 이렇게하면 검색 목록의 각 요소에 대해 반복적으로 전체 데이터 목록을 반복하지 않아도됩니다.

매우 빠르다고 생각했지만 불행히도 그렇지 않았습니다. 검색 목록의 전체 반복을 완료하는 데 거의 15 ~ 20 분이 소요됩니다. 이것은 허용되지 않습니다. 여기

내 코드의 조각이

int lastPointer = 0 
for(int i=0; i<search list.size(); i++){  
    def this_matched_out = [] 
    inmem_json_arr[i][0] 
    for(int j=lastPointer; j<data list.size(); j++){ 
     if(data list[j].containsAll(search list[i])){ 
      this_matched_out.add(data list[j]) 
      lastPointer = j 
     } 
    } 
    if(this_matched_out.size()>0) - println "found a match for search "+list[i] 
    else println "No match found for "+list[i] 
} 

아무도 나에게 더 나은 알고리즘을 제안 할 수

또는 여기 아무 잘못 뭐하는 거지입니까?

Answer 1

해시 테이블을 사용하십시오. 조회는 귀하의 단어가 얼마나 큰지 상관없이 O (1) 시간이 걸립니다.