티끌 모아 최적화

0. 본 글은 for 루프와 최적화에 대한 이야기입니다.

 

1. 코드 워즈라는 문제 풀이 서비스가 있습니다. 우리에게 흔히 알려진 문제 풀이 서비스인 백준등과 비슷한 서비스이나, 약간은 결이 다른 문제들이 많은 느낌입니다.

 

2. 최근에 이런 문제를 풀어보았습니다.

https://www.codewars.com/kata/58924f2ca8c628f21a0001a1/train/cpp

Codewars - Achieve mastery through coding practice and developer mentorship

이름은 좀 그렇지만, 난해한 프로그래밍 언어중 하나인 BrainFXXX의 번역기를 작성하는 문제입니다.

 

3. 하나의 명령어들을 토큰화해서 프로그램을 동작시키는데 성공했습니다. 버그들도 있었지만 고쳐냈고, 제법 큰 입력값에 대한 처리들도 통과했습니다.

 

4. 하지만 아뿔싸, 6개의 테스트군 중 마지막 테스트인 super input은 통과하지 못합니다. C++의 replace를 스택을 이용한 기법으로 바꾸기도 하고, 온갖곳을 쥐어 짜내 최적화를 시도하지만 아무리해도 되지 않습니다.

 

5. 구조적인 문제인가 고민하던 찰나, 우연히 한 곳에 눈이 갑니다. 바로 for 루프의 조건식입니다.

평소의 습관대로라면, 조건식에서 매번 length를 계산하는 것을 방지하기 위해 따로 const 변수로 빼놓는데, 어찌된 일인지 한군데 처리 되지 않았습니다.

for (unsigned long i = 1; i < source_code.length(); ++i)

const unsigned long len = static_cast<unsigned long>(source_code.length());
for (unsigned long i = 1; i < len; ++i)

그래서 코드를 위에서 아래로 재빠르게 수정하고 혹시나 하는 마음으로, 동시에 큰 기대 없이 문제를 제출합니다.

 

6. 그런데 문제가 성공적으로 통과됩니다. 코드상의 동적할당을 건드려야 하나, 아니면 구조를 새로 짜야하는 고민을 하고 있었는데, 정작 문제의 핵심은 사소해 보이는 곳에 있었습니다.

 

7. for문의 조건식은 매번 루프를 돌 때마다 조건식을 확인합니다. 다시 말해서, 조건식을 따로 변수로 캐싱해두지 않고 매번 length()나 size()를 불러 확인하게 되면 이 역시도 함수 호출이기 때문에 쌓이다보면 무시할 수 없는 양이 됩니다.

입력되는 데이터의 양이 적다면 크게 문제되진 않겠지만, 이번 경우처럼 입력량이 무수히 늘어나게 되면 결국은 속도에도 영향을 미치게 된다는 것이겠지요.

평소에 알고 있었던 개념이고, 늘 for 루프의 조건은 루프 바깥에서 처리하고 있었는데 실수로 놓친 덕분에 그 중요성을 다시 한번 확인할 수 있었습니다. 

티끌 모아 태산이라는 말이 새삼 떠오르게 되는 순간이었습니다.