.txt 파일에서 문자열을 검색하는 C에서 이진 검색 알고리즘을 만드는 중입니다. 각 행은 주식 시세 표시를 나타내는 문자열입니다. C에 익숙하지 않아서, 이것은 너무 오래 걸리고 있습니다.영문자 순으로 정렬 된 .txt 파일 C의 이진 검색 만들기
1) 일단 fopen을 사용하여 파일을 열었 으면 파일 검색을 위해 C 라이브러리에서 제공되는 일부 기능을 사용하여 알고리즘을 능률적으로 처리 할 수 있습니까? 파일에서 직접 비교를 수행하거나 각 행을 배열에 복사하고 알고리즘에서 배열을 검색해야합니까?
2.) 파일에서 직접 비교해야하는 경우이를 단계별로 처리하는 가장 좋은 방법은 무엇입니까? 파일에 줄수가 있다고 가정하고 중간 줄로 직접 이동하여 문자열을 스캔하여 비교하는 방법이 있습니까?
너무 애매한 경우 죄송합니다. 너무 잘 설명 할 방법이 없습니다. 시간을내어 주셔서 감사합니다.
파일 크기가 너무 큽니다 (2GB 이상) 다음에 파일을 메모리에로드하지 않으면 검색하는 것이 좋습니다. 메모리에 파일을로드 할 수없는 경우 각 행의 오프셋을 int[] 또는 (파일에 너무 많은 행이 포함 된 경우 ...) 보유하여 다른 이진 파일을 만들고 각 행의 오프셋을 정수로 쓸 수 있습니다.
메모리에 모든 것이 있으면 훨씬 좋습니다.
미리 각 줄의 길이를 모른 채 텍스트 파일의 줄을 이진 검색 할 수 없기 때문에 처음에는 각 줄을 메모리로 읽어 들이기를 원할 것입니다.
그러나 가능한 한 빨리 한 줄만 검색하는 것이 목적이라면 파일에서 직접 선형 검색을 수행 할 수도 있습니다. O (n) 설정 비용이 들지 않으면 O (log n)을 얻는 데 아무런 의미가 없습니다. 검색이 한 번만 수행되는 경우입니다.
이것은 또한 좋은 지적입니다. OP는 자신의 필요에 대해 모호했습니다. – chrisaycock
그래, 나는 그 논리를 본다. 그러나 그것은 학교 과제 다. 그것은 저에 관하여 저를 혼동시키는 것이 었습니다. 나는 그것이 선형 적으로 파일을 스캐닝함으로써 셋업되고 배열 될 것이라면 그것의 효율성을위한 알고리즘을 구현하는데 요점을 보지 못한다. – meburbo
meburbo : 좋습니다. 그러나 숙제 문제에 숙제 태그를 포함시키는 것이 좋은 스타일이라고 생각합니다. 나는 당신을 위해 이번에 덧붙였다. – kusma
일괄 읽기로 전체를 읽고 포인터 (메모리로 이동)로 걷는 것은 매우 빠릅니다. 가능한 경우 다중 I/O 호출을 수행하지 마십시오.
또한 메모리 매핑 된 파일은 이와 같은 상황에 매우 적합 할 수 있음을 언급해야합니다. Unix의 경우 mmap()을 참조하십시오. 정말 큰 파일에 대한 최선의 방법입니다.
+1 mmap, 정확히 내가 쓴 글 : –
나는 mmap()에 대해서도 생각해 봤지만 숙제에 따라 이진 검색을 요청했다. 문자열의 길이는 다양하므로 임의 액세스 권한이 없습니다. – chrisaycock
@chrisaycock : 당신의 요점을 알았다면 확실하지 않습니다. 무작위 접근은'mmap()'과 무슨 상관이 있습니까? – Oystein
파일에서 직접 비교할 수있는 방법이 없습니다. 디스크에서 읽은 데이터를 저장하고 해당 버퍼를 사용하려면 버퍼가 있어야합니다. 따라서 이해가되지 않습니다. 단지 불가능합니다.
파일의 특정 줄로 건너 뛸 수 없습니다. 파일의 시작 부분을 기준으로 해당 행의 시작 부분에 바이트 단위의 오프셋을 알지 못하는 경우.
mmap을 사용하여이 파일을 메모리에 직접 매핑하고 문자 배열과 함께 사용하는 것이 좋습니다. 운영체제는 탐색, 읽기, 쓰기와 같은 파일 작업을 사용자에게 투명하게 만들어 주며 메모리의 버퍼처럼 작업하게됩니다. mmap은 32 비트 시스템에서 4GB로 제한됩니다. 그러나 그 파일이 더 크다면 아마도이 질문을해야 할 것입니다 - 왜 지구상에 누군가가이 큰 파일을 색인 데이터베이스에 가지고 있지 않은지를 묻는 것입니다.
위대한 질문입니다.
이진 검색의 문제점은 O (1)의 각 단계에서 요소의 절반을 건너 뛸 수 있다는 것에서 비롯됩니다. 이렇게하면 O (lg n) 개의 프로브 만 수행하므로 런타임은 O (lg n)가됩니다.이것은 예를 들어 배열에 대해 빠른 이진 검색을 수행 할 수 있지만 링크 된 목록에는 포함되지 않습니다. 링크 된 목록에서 요소의 중 간 지점을 찾는 데 선형 시간이 걸리므로 검색 시간이 지배적입니다.
파일에서 이진 검색을 할 때 비슷한 위치에 있습니다. 파일의 모든 행이 같은 길이가 아니기 때문에, 파일 번호 n이 주어진 경우 파일의 n 번째 행으로 쉽게 건너 뛸 수 없습니다. 결과적으로 파일에 대해 좋은, 빠른 이진 검색을 구현하는 것은 약간 까다 롭습니다. 어떻게 든 파일 내에서 효율적으로 이동할 수 있도록 각 행의 시작 및 중단 위치를 알아야합니다.
이렇게하는 방법에는 여러 가지가 있습니다. 먼저, 제안한 것처럼 파일의 모든 문자열을 배열로로드 할 수 있습니다. 이것은 선형 시간이 걸리지 만 메모리에 문자열 배열이 있으면 이후의 모든 바이너리 검색이 매우 빨라집니다. 캐치 (catch)는 파일 크기가 매우 큰 경우 많은 메모리를 차지할 수 있으며 엄청나게 커질 수 있다는 점입니다. 결과적으로, 또 다른 대안은 실제 문자열을 배열에 저장하는 것이 아니라 각 문자열이 나타나는 파일에 오프셋을 저장하는 것입니다. 이렇게하면 바이너리 검색을 신속하게 수행 할 수 있습니다. 비교를 수행 할 때 파일을 적절한 오프셋으로 찾을 수 있습니다. 큰 스팅은 위의 공간보다 훨씬 공간 효율적 일 수 있습니다. 그리고 모든 문자열이 대략 같은 길이라면, 각 라인의 시작 위치를 직접 계산할 수 있도록 모든 라인을 고정 된 크기로 채울 수 있습니다.
좀 더 복잡한 솔루션을 구현하는 데 시간을 많이 소비하려는 경우 파일 전처리를 고려하여 줄 당 하나의 문자열 대신 파일 상단에 고정 소수점 목록 파일 내의 각 캐릭터 라인의 오프셋 (offset)를 포함한 폭의 정수. 이것은 기본적으로 위의 작업을 수행하지만 결과를 파일에 저장하여 이후의 이진 검색을 훨씬 빠르게 만듭니다. 나는 이런 종류의 파일 구조에 대해 약간의 경험이 있으며, 꽤 빠를 수있다.
정말로 도전적인 사람이라면 B- 트리를 사용하여 파일에 문자열을 저장할 수 있습니다. 그러면 원하는 디스크 읽기 횟수를 최소화하여 각 문자열을 엄청나게 빨리 검색 할 수 있습니다 할 것.
희망이 도움이됩니다.
+1 노력에 대해, 비록 당신이 여기서 언급 한 것의 대부분이 현재 OP의 이해를 초월 할 것입니다. 길 너머. – chrisaycock
차가움. 고마워요 – meburbo
. 메모리로 읽어 들여'bsearch()'를 사용하십시오. – chrisaycock
선의 오프셋을 저장할 필요는 없습니다. 'O'(m log n)'시간에' '\ n' '에 동기화하는 바이트에 바이너리 검색을 간단하게 수행 할 수 있습니다. 여기서'n'은 줄의 수이고'm'은 줄의 최대 길이입니다. 이것은 메모리에 파일을로드 할 수없고'fseek' /'fseeko'를 사용해야 만하더라도 작동합니다. –