[1주차] Python3의 빠른 입력, sys.stdin.readline

 

 

input()... 시간 초과를 알려주다

 

http://boj.kr/11659

11659번 문제를 풀고 있었다.

정확히는 C++17로는 풀어놓은 문제였지만, 스터디 공식 언어인 Python3로 다시 푸는 중이었다.

구간합 문제인데, 신기하게도 C++17로 풀 때에는 원본 배열 요소의 값 입력과 동시에 구간합 배열을 만들어야 하던 것이

Python3로 풀 때에는 원본 배열을 입력 받아놓고 그것으로 구간합 배열을 따로 만들어야 한다는 것이 아닌가...

 

그래서 구간합의 기본 골자는 C++17이든 Python3든 간에 상관 없이

구간합 배열을 S 라고 했을 때

구간합을 만드려면

S[i] = S[i - 1] + input;

 

이렇고

 

start ~ end 사이의 구간합을 알려면

S[end] - S[start - 1]

 

인 것은 동일한 거 아냐.

 

그래서 그렇게 작성을 했습니다.

그런데... 시간초과의 향연 (사진, 곤란)

 

시간 초과를 받은 가장 마지막 코드를 보자.

 

n, m = map(int, input().split())
numbers = list(map(int, input().split()))
sum = [0]
tmp = 0

for i in numbers:
    tmp = tmp + i
    # numbers의 각 요소와 이전 요소와의 합 -> 구간합 구하기
    sum.append(tmp)

for i in range(m):
    start, end = map(int, input().split())
    print(sum[end] - sum[start - 1])

 

아무리 생각해도, 구간합은 잘 구현을 했다.

그런데 자꾸 시간 초과가 나는거 아닌가...

그래서 설마 C++17에서 cin과 cout이 버퍼와의 tie를 끊어 입출력 속도를 개선했던 것처럼 Python3 에서도 그런 것이 있나 찾아봤다.

 

sys.stdin.readline

 

아, 있었다.

우선 오늘의 TIL에서는 사용자 입력에 대한 이야기만 적어둘 것이다. 출력에 대해서는 나중에 또 부딪힌다면 그제서야 작성해보도록 하겠다.

 

input()이 느린 이유

 

어쨌든, input()도 내부적으로는 sys.stdin.readline()을 호출한다.

그런 다음, 사용자 입력의 끝에 붙은 개행 문자 ('\n')을 제거한다.

마지막으로 입력이 비어 있을 경우의 에러의 예외 처리 따위도 포함되어 있다.

그리고 input()은 prompt를 인자로 받는데, prompt가 있을 경우 이를 먼저 출력하는 데에 시간을 쓴다는 것이다.

결론적으로는 추가적인 처리가 항상 수행되기 때문에 시간 초과가 나기 일수인 것이다.

 

sys.stdin.readline()의 동작 방식

 

sys.stdin은 파일 객체이며, readline()은 바로 버퍼에서 한 줄을 읽어온다.

개행 문자 제거 같은 후처리가 존재하지 않기에 개행 문자를 제거하는 rstrip() 같은 처리는 개발자가 직접 해줘야 하지만,

버퍼에서 바로 한 줄을 읽어온다는 것은 input()보다는 항상 빠른 속도를 보장한다는 이야기이다.

따라서 input() 보다 적게는 5배, 많게는 10배 이상의 빠른 속도를 보여준다.

 

그래서 해결한 코드

import sys

# input = sys.stdin.readline 등으로 초기화가 가능하다.
input = sys.stdin.readline

n, m = map(int, input().split())
numbers = list(map(int, input().split()))
sum = [0]
tmp = 0

for i in numbers:
    tmp = tmp + i
    # numbers의 각 요소와 이전 요소와의 합 -> 구간합 구하기
    sum.append(tmp)

for i in range(m):
    # input()의 경우 sys.stdin.readline() 대비 10배 이상 느리다
        #why - prompt 출력 때문에 시간 지연
    # m이 최대 100,000일 수 있기 때문에 100,000번의 input() 호출은? 느리다~
    start, end = map(int, input().split())
    print(sum[end] - sum[start - 1])

 

input = sys.stdin.readline 처럼 미리 해당 함수를 다른 이름으로 정의해놓을 경우 기존의 input() 처럼 편리하게 사용할 수 있는 듯 하다.

 

마음이 편안하구만....