바이너리 검색 하위 문자열을 사용하여 배열 문자열 검색

Question

약 200,000 개의 레코드가 포함 된 file.txt가 있습니다.

각 레코드의 형식은 123456-99-Text입니다. 123456은 고유 계정 번호이고, 99는 필요한 위치 코드이며 (01에서 99로 변경됨) 텍스트는 부적합합니다. 이 계좌 번호는 ac 단위 (111111, 111112, 111113 등)의 파일에서 줄 바꿈 순서로 정렬됩니다.

시각적 인 스튜디오 텍스트 상자와 검색 버튼을 만들어 누군가가 계정 번호를 검색하도록했습니다. 계좌 번호는 실제로는 11 자리이지만 처음 6 개 사항입니다. 이걸 문자열로 썼습니다. actnum = textbox1.text.substring(0,6)

if (x.contains(actnum)) 다음에 string code = x.substring(8,2)) 문을 사용하여 foreach (string x in file.readline('file.txt'))을 작성했습니다.

프로그램은 정상적으로 작동하지만 누군가가 존재하지 않는 계정 번호 나 목록 맨 아래에있는 번호를 검색하면 프로그램이 잘 작동하기 때문에 프로그램은 10 초 동안 잠겨 " 번호를 찾을 수 없습니다 "else 문 또는 영원히 그 마지막 레코드를 찾을 수 있습니다.

내 질문 : 이진 검색에 대해 읽기

이 나는 ​​많은 성공없이 하나를 시도하려고했습니다. 합법적 인 이진 검색처럼 작동하도록 배열이나 파일을 가져올 수 없습니다. textbox1에서 6 자리 actnum을 가져 와서 6 자리 계정 번호의 배열 부분 문자열과 비교 한 다음 해당 특정 줄에서 부분 문자열 99 코드를 가져 오는 방법이 있습니까?

바이너리 검색이 크게 도움이 될 것입니다! 필자는 555-555를 사용하여 레코드 파일의 상단 또는 하단과 비교 한 다음, 필요한 라인을 고칠 때까지 검색을 계속하고 전체 라인을 잡고 99 라인을 부분 출력합니다. 내가 가진 문제는 숫자와 텍스트가 모두 포함되어 있기 때문에 파일의 적절한 정수 변환을 얻는 것처럼 보이므로 적절하게 <,>, = 부호를 사용할 수 없습니다.

이 문제에 대한 도움을 주시면 대단히 감사하겠습니다. 현재 프로그램은 실제로 작동하지만 엄청나게 느립니다.

Answer 1

, 나는 상당히 프로그램을 가속화에 대한 포함 된 리소스를 배울 관리 않았다 이진 검색과 같을 것이다. 전체 파일을 스캔하는 데 5-10 초가 걸리므로 1 초가 걸립니다. 다음 코드 게시 :

string searchfor = textBox1.Text 
    Assembly assm = Assembly.GetExecutingAssembly(); 
    using (Stream datastream = assm.GetManifestResourceStream("WindowsFormsApplication2.Resources.file1.txt")) 
    using (StreamReader reader = new StreamReader(datastream)) 
    { 
     string lines; 
     while ((lines = reader.ReadLine()) != null) 
     { 
      if (lines.StartsWith(searchfor)) 
      { 
       label1.Text = "Found"; 
       break; 
      } 
      else 
      { 
       label1.Text = "Not found"; 
      } 
     } 
    } 

Answer 2

파일이 자주 변경되지 않는다고 가정하면 빠른 시간 내에 검색을 처리하는 구조를 사용하여 전체 파일을 메모리에로드하기 만하면됩니다. 파일이 변경 될 수있는 경우 파일을 다시로드하거나 프로그램을 다시 시작하거나 더 복잡한 프로세스를 다시 시작하기위한 메커니즘을 결정해야합니다.

정확한 일치를 찾는 것처럼 보입니다 (123456을 검색하면 123456이라고 표시된 하나의 레코드 만 생성됨). 이 경우 Dictionary을 사용할 수 있습니다. 사전을 사용하려면 키 및 값 유형을 정의해야합니다. 두 경우 모두 string이 될 것입니다.

Answer 3

하나의 가능한 해결책 (반드시 최고는 아님)으로 Dictionary<string, int> (또는 모든 레코드 ID가 숫자 인 경우 Dictionary<long, int>)에 레코드 ID를 추가 할 수 있습니다. 각 키는 한 줄의 ID이고 각 값은 줄입니다 색인. 특정 레코드를 찾아야 할 때는 사전을보고 (효율적인 검색을 할 것입니다) 줄 번호를 알려줍니다. 항목이 없으면 (존재하지 않는 ID) 사전에서 찾을 수 없습니다.

이 시점에서 파일에 레코드 ID가 있으면 줄 번호가 있습니다. 너무 크지 않은 경우 전체 파일을 메모리에로드하거나 오른쪽 줄을 탐색하여 데이터와 라인.

이 작업을하려면 파일을 한 번 이상 검토하고 모든 행의 모든 ​​레코드 ID를 수집하여 사전에 추가해야합니다. 이진 검색을 구현할 필요가 없습니다. 사전은 내부적으로 조회를 수행합니다.

편집 :

당신은 모든 특정 라인에서 데이터, (당신이 언급 한 위치 코드와 같은) 하나 개의 비트를 필요로하지 않는 경우, 당신도 (줄 번호를 저장 할 필요가 없습니다 이후 파일의 라인으로 돌아갈 필요가 없기 때문에) - 위치 데이터를 사전에 값으로 저장하십시오.

개인적으로는 내 경험에 따르면 이러한 프로젝트가 작지만 기능을 수집하기 시작하고 파일에서 모든 것을 갖춰야하기 때문에 라인 인덱스를 개인적으로 저장합니다. 이것이 시간이 지남에 따라 계속 될 것으로 예상된다면, 각 라인의 데이터를 데이터 구조로 구문 분석하고이를 사전에 저장하면 미래의 삶이 더 단순해질 것입니다. 정보의 1 비트보다 더 많은 데이터를 필요로하지 않을 것이라는 확신이 들면 사전 자체에 데이터 자체를 숨길 수 있습니다. 여기

는 (귀하의 기록 ID를가 long로 해석 될 수 있다는 가정) 간단한 예제 :

LineData lineData; 

if (_dataMap.TryGetValue (recordID, out lineData)) 
{ 
    // record ID was found 
} 

이를 :

public class LineData 
{ 
    public int LineIndex { get; set; } 

    public string LocationCode { get; set; } 

    // other data from the line that you need 
} 

// ... 

// declare your map 
private Dictionary<long, LineData> _dataMap = new Dictionary<long, LineData>(); 

// ... 
// Read file, parse lines into LineData objects and put them in dictionary 
// ... 

는 레코드 ID가있는 경우, 당신은 단지 TryGetValue() 전화를 보려면 접근법은 기본적으로 전체 파일을 메모리에 유지하지만 모든 데이터는 단 한 번만 (처음에는 사전을 만드는 동안) 구문 분석됩니다. 이 접근 방식이 너무 많은 메모리를 사용한다면 사전에 라인 인덱스를 저장 한 다음 레코드를 찾고 해당 라인을 파싱 할 경우 파일로 돌아가십시오.

Answer 4

다른 순서로 줄에 액세스 할 수 있어야하므로 file.ReadLine에 대해 실제로 이진 검색을 수행 할 수 없습니다. 파일을 가정 대신 메모리에 전체 파일을 읽어야합니다 (file.ReadAllLines가 될 것이다 옵션)

이 문자열에 의해 정렬됩니다, 당신은 다음

public class SubstringComparer : IComparer<string> 
    { 
     public int Compare(string x, string y) 
     { 
      return x.Substring(0, 6).CompareTo(y.Substring(0, 6)); 
     } 
    } 

과 IComparer

구현하는 새로운 클래스를 만들 수 있습니다 내가 검색의 더 나은 유형을 할 수있는 방법을 발견하지 않았지만

int returnedValue = foundStrings.BinarySearch(searchValue, new SubstringComparer());