중복 배열을 찾기 위해 너무 오래 걸립니다

Question

당신이 나를 도울 수 있기를 바랍니다.

다음과 같은 행을 포함하는 135,000 개의 긴 txt 파일이 있습니다 : 111706469;1972WE;26;Wel.

프로그램에서 수행해야하는 작업은 이전에 온 모든 줄마다 모든 줄을 비교하여 80 % 이상 유사한 지 확인한 다음 원래 줄의 줄 번호를 지정합니다.

나는 이런 식으로 스스로 할 수 있었던 것들.

  if (rows.Length > 1) { 
       for (int rowIndex = 1; rowIndex < rows.Length; rowIndex++) 
       { 
        string cols = rows[rowIndex]; 
        bool Dubbel = false; 

        for (int DupIndex = 0; DupIndex < rowIndex; DupIndex++) 
        { 
         string SearchDup = rows[DupIndex]; 
         decimal ComparisonResult = Compare(cols, SearchDup); 

         if (ComparisonResult > 80) 
         { 
          cols += ";" + DupIndex; 
          Dubbel = true; 
          break; 
         } 
        } 

        Console.WriteLine(rowIndex + ";" + cols); 
       } 
      } 

이것은 프로그램이 모든 배열 항목에 대해 계속해서 배열을 통과해야 함을 의미합니다. 내 질문은, 거기에 빠른/더 나은 방법이 일을 무엇입니까?

도움을 주시면 감사하겠습니다.

Answer 1

부동 소수점 숫자를 반환하는 퍼지 매칭 문제가 있습니다 - 퍼지 함수 자체에 대한 세부 정보없이 O (N * N)보다 최적화 할 방법이 없습니다 (틀렸을 경우 - 제발 누군가 정확함)

일치하는 항목이 있으면 먼저 제거하여 N^2 복잡도를 (NK)^2 (으)로 줄일 수 있습니다.이 작업은 최소한 정확한 성냥. 그런 다음 알고리즘으로 진행 Dictionary

List<string> rows = new List<string>(new[] {"AAA","BBB","AAA","CCC"}); 

HashSet<string> foundLines = new HashSet<string>(); 

foreach (string row in rows){ 
if (!foundLines.Contains(row)) 
    foundLines.Add(row); 
} 
rows = foundLines.ToList(); 

같은 두 번째 객체를 필요로하지 않는다

사용 HashSet<>는

Answer 2

당신은 중요한 정밀 검사없이 많은 최적화를 얻을 수있을 않을거야. 정확한 일치 또는 대상과 거의 일치하는 것을 검색하는 것은 사소한 일이지만, 객체 간의 차이는 이어야합니다.은 각 항목을 이전 항목과 비교해야합니다. 당신이 N 문자열의 집합을 제공하는 경우

기본적으로, 당신은 비교해야 N 등 N-1, N-2, N-3에 그럼 당신은 N 이외에, N+1 다시 그들에게 모든 을 비교해야하기 때문에 N+1과 N 사이에는 아무 관계도 없습니다.

Answer 3

나는 더 많은 노력을 기울여서 내 자신의 질문에 대한 답변을 얻었으며 다른 사람이 같은 문제를 겪는다면 게시해야한다고 생각했습니다.

나는 txt 파일을 mysql 데이터베이스로 변환 한 다음 모든 레코드를 한 번 DataTable에 SELECTED했습니다. 그런 다음 코드는 레코드를 반복하고 원본 DataTable의 SELECT는 동일한 우편 번호와 집 번호가있는 레코드 만 두 번째 DataTable에 반환합니다. 원본을 비교합니다.

이렇게하면 9 시간에서 2 ~ 3 분이 걸립니다. 사실 후에 그것은 아주 명백했습니다. 그러나 그런 일은 뒤늦은 지경이었습니다. ...

누군가가 도움이되기를 바랍니다.