Fast Input
input 함수가 본질적으로 느린 이유는 다음과 같은 성질에 있는데, input으로 10만 개의 글자를 한 번에 읽는 것보다, 한 개의 글자를 10만 번 읽는 것이 훨씬 느리다. 즉, 읽는 양이 문제라기보다는 읽는 횟수(줄 수)가 문제인 것이다. input이 이렇게 실행 overhead가 큰 이유는 prompt parameter 의 존재 때문이거나, stderr을 매번 flush하기 때문이거나, 또는 syscall을 위해 매번 tty를 확인하기 때문이라고 추측된다(구현).
알고리즘 문제 풀이에서는 prompt나 stderr 같은 것을 쓸 필요가 없으므로, 입력을 읽어오는 그 기능의 핵심만 사용하면 되기 때문에 sys.stdin으로부터 바로 readline하는 것으로 속도를 향상시킬 수 있다.
readline은 input과 달리 끝의 개행문자를 자동으로 없애지 않기 때문에, 문제가 string을 받기를 요구한다면 rstrip으로 처리해 줄 필요성이 있다. 다만 입력이 숫자로만 구성되어 있다면, 어차피 해당 string이int('1\n')과 같이 처리될 때 문제가 없기 때문에 개행문자를 없앨 필요가 없다.
흔히 사용되는 다른 방법으로는 os.read 함수를 사용하여 입력의 모든 내용을 한 번에 메모리에 미리 받아놓고 쓰는 방법이 있는데, 속도면에서 큰 차이를 확인하지 못했고 또 각종 interactive terminal에서 제대로 작동하지 않아 이 방법을 선호하고 있다.
TL; DR
입력의 줄 수가 적다면, 양이 많아도 fast input을 사용할 필요가 없다. 이 때 줄 수가 적음의 기준은 경험적으로 1000줄 이하 정도로 생각하고 있다.
입력이 숫자들로만 이루어져 있다면 input = sys.stdin.readline 으로 충분하며, 더 빠를 수 있다.
Fast Output
print도 마찬가지로, 출력하는 양이 문제가 아니라 출력하는 횟수가 문제가 된다. 그래서 따로 무언가를 import 하지 않더라도 속도 향상을 이루어 낼 수 있는 방법은, 출력할 모든 내용을 일단 하나의 list에 저장한 후, str.join 같은 함수를 이용해 그 모든 내용을 하나로 합쳐 마지막에 단 한 번의 print만 하는 것이다. 이 방법만으로도 output 속도에는 거의 문제가 없고 많은 사람들이 실제로 이렇게 한다. 그러나 굳이 print 함수의 속도를 향상시키려는 것은 불편함이 가장 큰 이유이다.
나는 print의 큰 장점이 print(*lst)와 같이 편하게 list나 generator를 출력하는 기능과, sep, end와 같은 parameter의 존재라고 생각한다. 이 기능들을 적절히 사용하면 코드의 가독성을 명료하게 유지하면서도 원하는 출력 포맷에 맞출 수 있다. 위의 방법은 이러한 점이 많이 부족하고, 흔히 사용되는 방법중 하나인 sys.stdout.write(str(x))도 마찬가지의 이유로 불편하다고 생각한다.
print 함수의 기능을 유지한 상태로 속도를 향상시키려면, 결국 print는 내가 원하는 전처리를 거친 후, 최종적으로 그 결과물을 sys.stdout에 write하는 구조로 되어있다는 점에서 다음과 같은 해결이 가능하다. 원래 존재하는 sys.stdout.write 대신, 같은 interface를 가진 io.BytesIO object를 새로 만들어 그곳에 write 하는 것으로 함수를 덮어씌운다. 이제 print 함수를 사용하면 원래의sys.stdout이 아닌, 이 새로운 곳에 정보를 쓴다. 그리고 코드가 모두 실행 된 후, 이 임시 공간에 저장된 모든 정보를 한 번에 출력하면 끝이다. 첫 문단의 방법과 사실상 같은 원리인데, print 함수의 내부 회로를 이용해서 만든 것이라 겉모습은 똑같은 것이다.
I want Faster IO
이 방법으로도 입출력이 느리다면, 사실 알고리즘 자체의 속도에 문제가 있거나 python 자체가 느린 것일 가능성이 높다. 시간복잡도를 개선하거나, 코드의 상수 효율성을 개선하거나, 아니면 그냥 c++로 다시 짜는 것이 빠를 수도 있다. 지푸라기라도 잡는 심정이라면, 나보다 고수분들이 만드신 template이 있다.
