array의 0번째 item을 sentinel로 사용한 sequential scan

Tags:

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]

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *