. 이분 검색

오프셋으로부터 줄번호와 열번호를 찾아주는 GetRCFromOff 함수는 유틸리티 함수들 중에 가장 자주 호출되는 함수이다. 앞으로 더 늘어나겠지만 ApiEdit9 22 곳에서 이 함수를 호출하여 줄번호를 구하고 있다. 이렇게 자주 호출되는 함수인데도 검색 방법이 다소 불합리하게 작성되어 있어 문서가 커지면 검색 속도가 느려진다. 따라서 이 함수를 최적화하여 검색 속도를 개선하면 전반적인 속도 향상을 기대할 수 있다.

이 함수가 줄번호를 찾는 방법은 검색 방법 중 가장 단순한 순차 검색(Sequential Search)이다. 문서의 첫 줄부터 검색을 시작하여 원하는 줄을 찾을 때까지 줄번호를 계속 증가시켜 가며 검색해 나간다. 0번 줄부터 너 이 오프셋 가지고 있어?라는 질문을 던지기 시작해서 1번 줄, 2번 줄, 3번 줄 식으로 계속 질문을 해 나가다가 Yes라는 대답을 들을 때까지 검색을 하는 것이다. 문서가 짧으면 이 방법도 효율적이지만 문서 길이가 커지면 자연히 검색 속도가 느려질 수밖에 없다.

이 함수가 검색하는 대상인 pLine 배열은 오프셋 순서대로 정렬(Sort. Align과는 다름)되어 있다는 특징이 있으며 이 특징을 십분 활용하여 이분 검색(Binary Search)으로 알고리즘을 바꾸면 훨씬 더 빨리 원하는 줄을 찾는다. 이분 검색이란 전체 구간을 반씩 나누어 가며 찾는 값이 있는 구간을 선택해 나가는 검색 방법이며 문서가 커져도 비교 횟수가 그리 많지 않다.

예를 들어 문서가 총 1000줄이라고 할 때 200번째 줄을 검색해야 한다고 해보자. 전체 1000줄을 절반으로 나누면 0~500, 500~1000 두 구간으로 나누어진다. 이 구간의 경계인 500의 값을 보고 이 값보다 찾는 값이 더 크다면 뒤쪽 구간을 선택하고 작다면 앞쪽 구간을 선택한다. 물론 500이 찾는 값이면 더 이상 검색할 필요도 없다. 그러면 0~499가 먼저 선택되고 다시 이 구간을 나누면 0~250이 선택되고 125~250구간이 선택되고 이런 식으로 계속 범위를 좁혀 나가다 보면 원하는 200줄을 금방 검색해 낼 수 있다.

GetRCFromOff 함수를 이 방식대로 검색하도록 바꾸어 보자. 완성된 코드는 다음과 같다. 이분 검색에 대한 자세한 내용은 알고리즘 서적을 보면 어렵지 않게 이해할 수 있으므로 상세한 코드 분석은 생략한다.

 

void GetRCFromOff(int nPos, int &r, int &c)

{

     int Upper,Lower;

 

     Lower=0;

     Upper=TotalLine-1;

     for (;;) {

          r=(Upper+Lower)/2;

 

          if (nPos > pLine[r].Start && nPos < pLine[r].End)

              break;

 

          if (nPos == pLine[r].Start) {

              if (pLine[r].nLine != 0 && bLineEnd==TRUE) {

                   r--;

              }

              break;

          }

 

          if (nPos == pLine[r].End) {

              if (buf[pLine[r].End] == 0 || buf[pLine[r].End] == ‘\r’ || bLineEnd == TRUE) {

                   break;

              }

          }

 

          if (pLine[r].Start > nPos) {

              Upper=r-1;

          } else {

              Lower=r+1;

          }

     }

 

     c=nPos-pLine[r].Start;

}

 

순차 검색을 할 때와 비교해보면 알고리즘 외에도 몇 가지 달라진 것이 있는데 오프셋이 이 줄에 속했는지 범위를 검사할 때 Start위치는 제외된다는 점이 다르다. nPos pLine[r].Start를 비교하는 연산자가 >=에서 >로 바뀌었다. 오프셋이 줄의 처음과 같더라도 이 줄이 자동개행된 줄이고 bLineEnd TRUE이면 이 오프셋은 이전 줄의 끝에 있는 것이므로 별도로 조건 점검을 해야 한다.

순차 검색을 할 때는 Start를 범위에 포함시켜도 상관없는데 왜냐하면 항상 윗줄이 먼저 검사되고 윗줄에서 nPos End와 같고 bLineEnd TRUE이면 이 오프셋을 먼저 자신의 줄에 포함시키기 때문이다. nPos Start와 같아진 조건은 이미 윗줄은 아니라는 가정이 있으므로 nPos Start와 같을 때 무조건 이 줄에 속한 오프셋이라고 볼 수 있었다.

그러나 이분 검색은 줄번호 순으로 테스트를 하는 것이 아니고 구간의 중간중간을 쿡쿡 찔러 보면서 이 오프셋이 니 꺼야? 아니면 너보다 커, 작아?를 질문하기 때문에 어떤 줄이 먼저 테스트될지 알 수가 없는 것이다. 그래서 nPos Start인 경우는 무조건 줄 범위안에 있다고 확신할 수 없으며 별도의 테스트가 더 필요하다. nLine 0이 아니라는 조건은 자동개행된 줄의 선두라는 뜻이며 이 상태에서 bLineEnd TRUE이면 이 줄 바로 앞 줄의 끝 오프셋이라고 판단하게 된다.

알고리즘을 바꾼 후 예제를 실행해보면 효과는 가히 놀랄만하다. 문서의 어느 부분에서나 캐럿이동이나 선택에 지연이 거의 없다는 것을 확인할 수 있다. 96000줄을 찾는데 96000번을 비교했던 것을 17번 정도만 비교하면 찾을 수 있게 되었기 때문이다. 더구나 선택할 때는 이 함수가 한 번 호출되는 것도 아니고 여러 번 반복적으로 호출되기 때문에 속도 향상 효과가 더욱 크다.