빠른 검색

김동웅·2021년 10월 19일

File_structrue In C,C++

목록 보기

11/11

보조기억장치에 대한 접근비용이 매우 크기 때문에, 이를 최소화할 수 있는 정렬 및 검색 방법이 필요하다.

1. 단순 필드와 레코드 파일에서의 조회

RRN이나 Byte offset을 알지 못할때, 현재까지 키를 사용한 접근은 순차 탐색을 의미

2. 추측에 의한 검색 : 이진 탐색

1000개의 고정길이 레코드를 가지고 있고 키를 사용하여 오름차순으로 정렬된 파일
Jane Kelly라는 레코드를 이진탐색으로 찾는 방법: 최대 10번 비교


int BinarySearch(FixedRecordFile &file, RecType &obj, KeyType &key)
// 키에 대한 이진 탐색
// 키가 발견되어 진다면, obj는 해당하는 레코드를 포함하고 1을 되돌려 준다.
{
	int low = 0; int high = file.NumRecs() – 1;
	while(low <= high)
	{
	int guess = (high+low)/2;
	file.ReadByRRN(obj.guess);
	if(obj.Key() == key) return 1; // 레코드를 찾은 경우
	if(obj.Key() > key) high = guess –1; // guess 앞부분을 검색
	else low = guess + 1; // guess 뒷부분을 검색
	}
return 0; // 키를 발견하지 못하고 루프를 끝나는 경우
}

이진탐색 vs 순차탐색

이진탐색 : 최대 └log2^n┘+1 번 비교, O(log2^n)의 복잡도
순차탐색 : 최대 n번 비교, 평균 n/2번 비교
: O(n)의 복잡도

키정렬

메모레엇는 파일로부터 키만을 읽어 이를 정렬하고, 이 키에 대한 새로운 순서에 따라 파일 내 레코드를 재정리(tag sort라고도 함)

키정렬 방법 설명

가정 : 고정길이 레코드파일, 헤더 레코드에 전체 레코드 유지
알고리즘 :
① 디스크에서 키 RRN 쌍을 읽어 keyRRN 객체의 배열(KEYNODES[])에 저장
② 메모리상에서 KEYNODES[] 를 정렬한다.
③ KEYNODES[] 의 배열 순서대로 입력화일의 레코드를 읽어서 새로운 화일에 기록한다.

void KeySort(FixedRecordFile & inFile, char * outFileName)
{
RecType obj;
KeyRRN * KEYNODEs = new KeyRRN[inFile.NumRecs()];
// 화일을 읽어서 키를 적재
  for(int i=0; i<inFile.NumRecs(); i++)
  {
  inFile.ReadByRRN(obj, i); // 레코드 I를 읽는다 // fread
  KEYNODES[i] = KeyRRN(obj.Key(), i); // 키와 RRN을 키 배열에 넣는다
  }
Sort(KEYNODES, inFile.NumRecs()); // 키 배열을 정렬한다
FixedRecordFile outFile; // 정렬된 키순서로 레코드를 지니게 될 화일
outFile.Create(outFileName); // 새로운 화일을 생성한다
// 정렬된 키 순서로 새로운 화일에 기록한다
  for(int j=0; j<inFile.NumRecs(); j++)
  {
  inFile.ReadByRRN(obj, KEYNODES[j].RRN); // 키 순서로 읽기 / fseek
  outFile.Append(obj); // 키순서로 기록 // fwrite
  }
  
}