매우 큰 텍스트 파일에서 이진 검색을 수행하는 C# 코드

Question

매우 큰 텍스트 파일 (10GB 일 수 있음)에서 이진 검색을 수행하는 데 사용할 수있는 라이브러리가 있습니까?

파일은 일종의 로그 파일로, 모든 행은 날짜와 시간으로 시작합니다. 따라서 행이 정렬됩니다.

Answer 1

나는 의사 코드를 작성하는 방법을 쓰기 시작했으나 좋지 않을 수도 있으므로 포기했습니다. 바이너리 검색을 작성하는 방법을 알고있을 것입니다. 실제로는 복잡하지 않습니다.

당신은 두 가지 이유에서, 도서관에서 찾을 수 없습니다 :

1. 그것은이다 정말 "이진 검색"- 당신이 알고리즘을 적용 할 수 있도록 라인 크기, 다른 (예를 들어,파일의 중간을 찾은 다음 다음 "줄 바꿈"을 찾아 "중간"이라고 생각하십시오).
2. 당신의 datetime 로그 형식은 비표준 일 가능성이 높습니다. (좋아, "표준"으로 보일지 모르지만 조금 생각하면 .... 로그 메시지와 날짜를 구분하기 위해 '[] [10/02/2001 10:35:02] 내 메시지).
요약

- 나는 당신의 필요가 누군가가 파일이 정적 인 경우 라이브러리 :

Answer 2

목록 개체에는 이진 검색 방법이 있습니다.

http://msdn.microsoft.com/en-us/library/w4e7fxsh%28VS.80%29.aspx

Answer 3

파일을 스트리밍 할 수 있어야합니다,하지만 당신은 또한 랜덤 액세스가 필요합니다. 파일의 각 줄에 같은 수의 바이트가 들어 있다는 보장이 부족한지 어떻게 확신 할 수 있는지 잘 모르겠습니다. 그렇게했다면 객체의 스트림을 얻을 수 있고 Seek 메서드를 사용하여 파일 내에서 이동할 수 있습니다. 거기에서 선을 구성하는 바이트 수를 읽어서 이진 검색을 수행 할 수 있습니다. 그러나 다시 말하지만, 행 수가 같은 바이트 수인 경우에만 유효합니다. 그렇지 않으면 선의 중간에서 벗어날 것입니다.

뭔가

라인의 길이가 동일한 길이 보장되지 않습니다으로

byte[] buffer = new byte[lineLength]; 
stream.Seek(lineLength * searchPosition, SeekOrigin.Begin); 
stream.Read(buffer, 0, lineLength); 
string line = Encoding.Default.GetString(buffer); 

Answer 4

처럼, 당신은 예를 들어, 인식 라인 경계의 일부 양식을 필요 해요 캐리지 리턴 또는 줄 바꿈.

바이너리 검색 패턴은 기존의 알고리즘과 거의 비슷합니다. 파일의 '가운데'로 (길이로) 탐색하고, 줄 바꿈 시퀀스로 구분 된 착륙선의 시작 부분으로 뒤로 (바이트 단위로) 탐색하고, 해당 레코드를 읽고 비교합니다. 비교에 따라 위아래로 (바이트 단위로) 탐색하여 반복하십시오.

레코드의 시작 인덱스를 식별 할 때 마지막 레코드와 동일한 인덱스인지 확인하십시오. 목표 레코드에서 전화를 걸면 중간으로 이동해도 다른 레코드로 연결되지는 않습니다. 예 : 각각 100 바이트와 50 바이트의 인접 레코드가 있으므로 75 바이트로 점프하면 항상 첫 번째 레코드의 시작으로 돌아갑니다. 그런 일이 발생하면 비교하기 전에 다음 기록을 읽으십시오.

꽤 빨리 목표를 달성 할 수 있습니다.

Answer 5

파일의 모든 줄 바꿈 (line-feed)에 대해 Int64를 메모리에 보유해야한다는 제약 아래서는 안됩니다. 이것은 실제로 텍스트 라인이 얼마나 오래 지속되는지에 달려 있습니다. 라인 당 1000 바이트 (10000000000/1000 * 4) = 40MB가 주어집니다. 매우 크지 만 가능합니다. 오프셋 (offset) 파일을 검색하고 읽는 사용자 정의 비교 자와 함께 목록을 검색

1. 파일을 스캔하고 목록
2. 바이너리의 각 줄 바꿈의 오프셋 (offset) 서수를 저장 :

   그래서 이것을 시도 데이터.

Answer 6

를 작성 귀찮게 (또는 거의 변경)하는 사용자 지정 코드에 구현하기 위해 너무 구체적 너무 간단하게 생각하고, 당신은

1. 이는 (초기 파일을 스캔하고 날짜 파일의 일부를 더한 원래의 자신의 위치를 ​​가지고 : 그것에 대하여 "충분히"쿼리를 실행, 나는 가장 좋은 방법은 "인덱스"파일을 생성 할 것으로 예상 왜 꽤 정적이어야합니다) 어떻게 그들을 인코딩 (예 : 유닉스 시간 (전체 10 자리) + nanosecon ds (제로로 채워진 4 자리수)와 줄 위치 (제로로 된 10 자리수). 이 방법을 사용하면 일관된 "라인"을 가진 파일을 갖게됩니다

2. 해당 파일에 대한 프리폼 이진 검색 (범위 검색을 수행하려면 조금 창의적이어야 함) 원본 파일의 관련 위치 가져 오기 지정된 위치에서 시작하여 원본 파일에서 직접 읽을

3. 는/당신은 O로 (로그 (N)) 실행 시간 : 검색 범위있어 지정된 범위

읽기 (당신은했습니다 생성 된 프리미티브 DB 기능)

파일 데이터 파일 너무 자주 업데이트되거나 쿼리 파일에서 저장하는 것보다 인덱스 파일을 만드는 데 더 많은 시간을 소비하면서 끝낼 색인 파일에 대해 "충분한"쿼리를 실행하지 않습니다.

Btw,이 인덱스 파일로 작업 할 때 데이터 파일을 정렬 할 필요가 없습니다. 로그 파일을 추가하고 정렬하는 경향이 있으므로 데이터 파일에서 EOL 표시 (0으로 채워진 10 자리)의 위치 만 보유하는 색인 ​​파일을 간단하게 작성하여 전체 작업 속도를 향상시킬 수 있습니다. 데이터 파일에 직접 바이너리 검색 (원본 파일에서 찾기 위치를 결정하기 위해 색인 파일 사용) 및 로그 파일에 줄이 추가되면 EOL 위치를 색인 파일에 간단히 추가 (추가) 할 수 있습니다.