Knuth는 그의 책 Selected Papers on Computer Science에서 array[0]을 sentinel로 사용하는 sequential scan의 개선안에 대해 이야기했습니다. (그리고 제 기억이 맞다면 TAOCP 1권에도 이 내용이 나옵니다.) sequential scan은 다음과 같이 이루어집니다.
INPUT: 검색할 값 TARGET, 검색할 대상인 array, array내 원소의 수 n
1. i = n
2. If i = 0, report “NOT FOUND” and terminate
3. If array[i] = TARGET, report i and terminate
4. Decrement i by 1 and goto 2.
문제는 2번단계가 불필요해보인단 것이죠. Knuth가 보인 해결책은 다음과 같습니다.
INPUT: 검색할 값 TARGET, 검색할 대상인 array, array내 원소의 수 n
1. array[0] = TARGET
2. i = n
3. If array[i] = TARGET, report i and terminate
4. Decrement i by 1 and goto 3.
두번째 방법에서는 array[0]에 TARGET을 저장해두었으므로, 배열의 끝을 지나쳐나가지 않게됩니다. 결국 i = 0 인가의 비교가 제외되므로 속도가 20% 향상된다고 그는 지적하였습니다. 그래서 한번 테스트를 해봤습니다. 특히 && 를 사용한 shortcut evaluation 의 영향도 고려하기 위해 standard sequential scan에서 조건의 순서를 바꿔가며 테스트해봤습니다.
#include
#include
using namespace std;
int main()
{
const int NUM_LOOPS = 1000000;
const int ARRAY_SIZE = 100000;
int array[ARRAY_SIZE];
for (int i = 1; i < ARRAY_SIZE; ++i)
array[i] = rand();
int target_index = rand() % ARRAY_SIZE;
int target = array[target_index];
int answer_idx;
// Use array[0] as sentinel
array[0] = target;
time_t start_time = time(NULL);
for (int i = 0; i < NUM_LOOPS; ++i)
for (answer_idx = ARRAY_SIZE - 1; array[answer_idx] != target; --answer_idx);
time_t end_time = time(NULL);
cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;
// Standard sequential scan
start_time = time(NULL);
for (int i = 0; i < NUM_LOOPS; ++i)
for (answer_idx = ARRAY_SIZE - 1; i >= 1 && array[answer_idx] != target; –answer_idx);
end_time = time(NULL);
cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;
// Standard sequential scan #2
start_time = time(NULL);
for (int i = 0; i < NUM_LOOPS; ++i)
for (answer_idx = ARRAY_SIZE - 1; array[answer_idx] != target && i >= 1; –answer_idx);
end_time = time(NULL);
cout << "elapsed=" << (end_time - start_time) <<" target_index="<< target_index << " answer=" << answer_idx << endl;
return EXIT_SUCCESS;
}
[/code]
결과 입니다.
[code lang="cpp"]
[mkseo@mkseo-desktop ~/tmp]$ g++ scan.cpp
[mkseo@mkseo-desktop ~/tmp]$ ./a.out
elapsed=176 target_index=58275 answer=58275
elapsed=195 target_index=58275 answer=58275
elapsed=194 target_index=58275 answer=58275
[/code]
분명 19초 정도가 향상되지만 루프가 1,000,000회 수행되었음에 주목할 필요가 있습니다. (즉 거의 성능향상이 없다.) 물론 이와 같은 코딩 테크닉상의 성능향상은 중요한 최종 튜닝 포인트가 될 수 있습니다. 하지만, 다음에 보인 바와 같이 그러한 튜닝작업을 잘 짜여진 컴파일러보다 더 잘할 수 있을지는 의문입니다.
[code lang="cpp"]
[mkseo@mkseo-desktop ~/tmp]$ g++ -O3 scan.cpp
[mkseo@mkseo-desktop ~/tmp]$ ./a.out
elapsed=65 target_index=58275 answer=58275
elapsed=68 target_index=58275 answer=58275
elapsed=57 target_index=58275 answer=58275
[/code]