속도 최대 문자열 검색 알고리즘

Question

하는 페이지에서 내가 700 페이지 문서에서 검색 할 때 나는 그것으로 아무 문제가 없지만, 그것을

for (int i = 1; i <= a.PageCount; i++) 
{ 
    Buf.Append(a.Pages[i].Text); 
    String contain = Buf.ToString(); 
    if (contain != "") 
    { 
     // Inside is dictionary of keys and value contain page where I found it 
     foreach (KeyValuePair<string, List<string>> pair in inside) 
     { 
       if (contain.Contains(pair.Key)) 
        inside[pair.Key].Add((i).ToString()); 
     } 
    } 

    Buf.Clear(); 
} 

을 발견 나는 문서에서 텍스트를 검색하고 taging이 간단한 알고리즘을 사용하고 있습니다 그리고 나는 매우 천천히, 약 1-2 분이 걸리는 500 개 이상의 열쇠를 찾고 있는데, 속도를 높이는 방법이 있습니까? 나는 C를 사용하고있다 #

고마워!

Answer 1

몇 가지 포인트 :

• 이 Buf 제거하십시오; a.Pages[i].Text을 contain에 직접 할당하십시오 :
• inside[pair.Key]는 해당 키와 관련된 값을 검색하는 데 낭비합니다. 당신은 그 객체에 대한 더 싼 참조가 pair.Value에 있기 때문에 시간이 낭비됩니다.
• 정수 값 목록이 있다면 문자열로 저장하는 이유는 무엇입니까?

샘플 코드 :

for (int i = 1; i <= a.PageCount; i++) 
{ 
    String contain = a.Pages[i].Text 
    if (contain != "") 
    { 
     // Inside is dictionary of keys and value contain page where I found it 
     foreach (KeyValuePair<string, List<int>> pair in inside) 
     { 
      if (contain.Contains(pair.Key)) 
       pair.Value.Add(i); 
     } 
    } 
} 

마지막으로, Pages 사실 한 인덱스를 사용합니까 있는지 확인하십시오. 컬렉션은 일반적으로 인덱스가 제로입니다. Pages 이후

편집는 사전입니다 : 당신이 시간 첫 번째 코드 샘플을했던 몇 번

foreach (KeyValuePair<int, Page> kvp in a.Pages) 
{ 
    string contain = kvp.Value.Text; 
    if (contain == "") 
     continue; 
    foreach (KeyValuePair<string, List<int>> pair in inside) 
     if (contain.Contains(pair.Key)) 
      pair.Value.Add(kvp.Key); 
} 

? 시간은 많은 외부 요소에 따라 다를 수 있습니다. 사실 하나의 접근 방식으로 하나의 접근 방식이 다른 하나의 실행 방식보다 빠르거나 느리다는 사실은별로 알려주지 않습니다. 특히 내가 제안한 제안이 문제의 대부분을 다루지 않았을 때 그렇습니다.

다른 사람이 지적했듯이 주된 문제는 contain.Contains(pair.Key)을 350,000 번 호출하는 것입니다. 아마도 병목 일 것입니다. 메소드를 프로파일 링하여 사실인지 알아낼 수 있습니다. 이이면 true, Miserable Variable에서 제안한 Rabin Karp 알고리즘과 같은 것이 가장 좋은 방법 일 것입니다.

Answer 2

[[

편집 : 다음은 루프의 끝에서를 버퍼를 클리어하고 있기 때문에 (당신이 정말로 BUF가 필요하지 않습니다 노트, string pageText = a.Pages[i].Text 모든 비록 당신이 필요),

관계가 무엇 Buf? 당신은

Buf.Append(a.Pages[i].Text); 

은 점점 더 큰 크기의 문자열을 찾기 위해 Contains을 강제하지 않습니다 것을? 나는 당신이 700 페이지의 메모리가 부족한 것이 아닌지 놀랍다.

]

는 any of a set of strings 다른 string 나타나는 경우 볼 수있는보다 효율적인 방법이 있습니다. 예를 들어 여러 번 비교할 필요가 없도록 키의 트리 구조를 준비 할 수 있습니다.

타사 라이브러리를 기존 고려해야 할

Rabin-Karp Algorithm를 참조, 일부가 있어야합니다.

Answer 3

내가 함께 테스트하기 위해 700 페이지가없는,하지만 당신은 정규식을 사용하여 시도 할 수 :

var s = Stopwatch.StartNew(); 
var r = new Regex(string.Join("|", from x in inside select Regex.Escape(x.Key))); 

for (int i = 1; i <= a.PageCount; i++) 
{ 
    foreach (Match match in r.Matches(a.Pages[i].Text)) 
    { 
     inside[match.Value].Add(i.ToString()); 
    } 
} 

Console.WriteLine(s.Elapsed); 

Answer 4

표준 성능/디버깅 절차를 - 코드 및 측정의 조각을 주석 처리합니다. 그것이 나쁠 때까지 한 번에 하나씩 다시 추가하십시오. 그럴 가능성이 귀하의 문제 영역입니다.

예를 들어 전체 foreach를 주석 처리하여 시작할 수 있습니다.

아마도 내부, Buf 등과 같이 복잡하고 값 비싼 일부 오브젝트가있는 것처럼 보입니다. 사용법을 주석으로 처리하고 한 번에 하나씩 되돌려 놓습니다.