C/C++ 입출력 방법에 따른 속도 정리

때는 백준 1920번 문제를 풀 때 겪은 일이었습니다.

https://www.acmicpc.net/problem/1920

문제를 보자 마자 C++ STL에 있는 unordered_set을 이용하면 풀리겠거니, 하고 풀었더니 시간초과가 났습니다.

그래서 풀이를 찾아보니 바이너리 서치를 이용해서 풀더군요. 그래서 C++ STL Algorithm 헤더에 있는 binary_search를 이용해서 푸니 똑같이 시간초과가 났습니다.

예전에 C++ STL에 있는 upper_bound와 lower_bound가 O(lgN)이 아니라 선형 시간복잡도를 갖는다는 이야기를 들은적이 있습니다.(틀린 이야기라라고 합니다.) (binary_search는 lower_bound를 이용해서 구현된 것으로 알고 있습니다.) 그래서 vector container에 대한 binary_search를 커스텀으로 구현한 뒤 다시 풀어보니 또 시간초과...

그래서 binary_search를 잘못 구현한 것인가 싶어서 vector<int>::iterator를 이용하지 않고, int형 인덱스로 다시 구현해도 시간초과가 났습니다. 그래서 미뤄두고 있다가 최근 코드포스에서 비슷한 현상을 겪었죠.

http://codeforces.com/contest/892/problem/B

C++로 구현하니 시간초과가 나는데 요즘 공부하는 파이썬으로 짜니 오히려 정답처리가 되는... 그래서 대회가 끝나고 C++로 정답판정을 받은 사람들의 코드를 보니 다음과 같은 코드가 눈에 띄었습니다

 
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin, cout이 scanf, printf에 비해서 속도가 많이 느리다고 하더군요. std::endl보다 '\n'가 훨씬 빠르다는 이야기도 많이 들었지만, 실제 프로그래밍 문제를 풀 때 이러한 것 때문에 애로사항을 겪은적이 없었기 때문에 크게 신경쓰지는 않았었는데 이렇게 겪게 되었습니다.

따지고 보면 입출력 속도 때문에 시간초과가 난 문제 둘 다 최대 입력값 개수가 100만개 이상이었습니다.

찾아보니 여러가지가 자료들이 많았는데 결론적으로는 편리함 때문에 cin, cout을 쓰기 보다는 scanf와 printf를 사용하면 해결될 문제입니다. 그리고 좀 더 빠르게 하겠다면 글자 하나씩 입출력하는 함수들이 더 빠릅니다.(getchar, putchar 등등)

cin, cout을 사용하더라도 sync_with_stdio(false)로 속도를 가속할 수는 있지만, 이는 정공법적인게 아니라 일종의 편법같은 방식이고, 이 방식도 통하지 않는 경우가 있습니다.(그래도 scanf, printf속도로만 정답이 나오는 경우) 그리고 sync_with_stdio를 false로 준 경우, scanf, printf와 같은 C 표준 입출력 함수와 cout, cin같은 C++ 입출력 객체를 섞어 사용하는 경우 오답처리가 날 수 있습니다. 입출력이 코드 작성자가 의도하지 않은 순서로 나타난다던가 하는 일이 일어날 수 있다는 것이죠. 특히 멀티 쓰레드 환경일 경우 sync 값이 true일 때는 Thread safe라서 예상치 못한 값이 나오지 않지만, false를 시킬 경우 Thread unsafe해지기 때문에 예상치 못한 값이 나타날 수 있습니다.

그러므로 굳이 sync_with_stdio(false); 를 이용해서  C++ 입출력 객채를 가속시켜서 사용할 것이라면, scanf와 printf와 섞어서 사용하지 말 것이며, 싱글 쓰레드 환경에서만 사용(알고리즘 문제만 풀 때는 무조건 싱글스레드이므로 상관없지만 실무에선 쓰지말것)하고, 그래도 시간초과가 난다면 C 표준입출력 함수들을 사용하는 것을 추천하는 바입니다.

더 참고할 수 있는 자료들

알고스팟 - 언어별 input method 비교

https://algospot.com/forum/read/2496/

백준저지 -  1920번 문제 질문

https://www.acmicpc.net/board/view/9022

cpp reference - sync_with_stdio

http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

stackoverflow - sync_with_stdio, cout.tie등에 대한 질문에 대한 답변

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull