백준11637🐨인기 투표 - 입출력 속도 실험 #n

들어가기 전에 제대로 된 저 말고 진짜 프로그래밍 고수님들의 말을 전합니다.

최적화로 10ms 줄일 고민하기 전에 제발 알고리즘으로 10s 줄일 생각을 해라.

Stay safe. Don't try this at home.

위 표의 순서대로 코드를 아래에 열거했다.

import os
T,*arr = map(int,os.read(0,os.fstat(0).st_size).decode().split())
it=iter(arr)
res = ["" for _ in range(T)]
for j in range(T):
    n = next(it)
    a = [next(it) for i in range(n)]
    s = sum(a)
    mx = max(a)
    res[j] = "no winner" if a.count(mx)-1 else f"majority winner {a.index(mx) + 1}" if s < (mx << 1) else f"minority winner {a.index(mx) + 1}"
open(1,'w').write('\n'.join(res))

제일 느린 코드. 라이브러리 오버헤드는 걸렸는데 출력은 또 open(1,'w').write를 쓰면서 오버헤드를 보상 못 받는 것 같다.

 

import os
T,*arr = map(int,os.read(0,os.fstat(0).st_size).decode().split())
it=iter(arr)
res = ["" for _ in range(T)]
for j in range(T):
    n = next(it)
    a = [next(it) for i in range(n)]
    s = sum(a)
    mx = max(a)
    res[j] = "no winner" if a.count(mx)-1 else f"majority winner {a.index(mx) + 1}" if s < (mx << 1) else f"minority winner {a.index(mx) + 1}"
os.write(1,'\n'.join(res).encode())

그래도 위보다는 빠른 순수os 라이브러리 입출력

 

T,*arr = map(int,open(0).read().split())
it=iter(arr)
res = ["" for _ in range(T)]
for j in range(T):
    n = next(it)
    a = [next(it) for i in range(n)]
    s = sum(a)
    mx = max(a)
    res[j] = "no winner" if a.count(mx)-1 else f"majority winner {a.index(mx) + 1}" if s < (mx << 1) else f"minority winner {a.index(mx) + 1}"
open(1,'w').write('\n'.join(res))

open함수만 쓴 것. open 함수로 표준출력으로 줄 때 close문제를 겪지 않기 위해 모아서 한 방에 준다.

 

it = iter(map(int,open(0).read().split()))
for _ in range(next(it)):
    n = next(it)
    a = [next(it) for i in range(n)]
    s = sum(a)
    mx = max(a)
    if a.count(mx)-1:
        print("no winner")
    else:
        print(f"majority winner {a.index(mx) + 1}" if s < (mx << 1) else f"minority winner {a.index(mx) + 1}")

출력을 모으지 않고 제때한 버전.

 

 

---

 

 

1. 표준 입력과 출력에서의 오버헤드

• 표준 입력 (sys.stdin.read): 표준 입력은 Python에서 기본적으로 버퍼링되고, 이를 통해 데이터가 읽힌다. 이 과정에서 Python은 텍스트 데이터를 처리하기 위해 추가적인 작업을 수행한다. 예를 들어, sys.stdin.read()는 텍스트를 처리하며, 데이터를 한 번에 읽고 문자열로 변환하는 과정에서 시간과 메모리가 소모된다.
• 표준 출력 (sys.stdout.write): 표준 출력도 비슷하게 텍스트 데이터를 처리하며, 출력 과정에서 버퍼링을 사용한다. 이때 Python의 내부 버퍼 관리, 문자열 인코딩, 유니코드 처리 등이 추가적인 작업으로 이루어지며, 이로 인해 오버헤드가 발생한다.

2. 오버헤드를 줄이는 방법

• os 모듈 사용: os.read와 os.write는 저수준의 시스템 호출을 통해 데이터를 처리한다. 이 함수들은 시스템의 파일 디스크립터와 직접 상호작용하며, 추가적인 텍스트 처리 없이 바이트 단위로 데이터를 읽고 쓴다. 따라서, 입력이나 출력에 대해 Python의 고수준 텍스트 처리 작업을 건너뛰므로 오버헤드가 줄어든다.
• 버퍼 크기 조절: 큰 데이터를 처리할 때는 버퍼 크기를 조절하여 읽기와 쓰기 작업의 빈도를 줄이는 것도 오버헤드를 줄이는 방법이다. os.read와 os.write를 사용할 때는 기본적으로 큰 덩어리의 데이터를 한 번에 처리할 수 있어, 작은 조각으로 여러 번 읽고 쓰는 것보다 더 효율적이다.

3. 성능 비교 예시

• 텍스트 처리 시간 차이: sys.stdin.read는 문자열로 데이터를 처리하는 동안, os.read는 바이트 스트림으로 처리한다. 따라서, 전자는 데이터가 많아질수록 유니코드 변환과 버퍼링 때문에 더 느려질 수 있다. 반면, 후자는 이러한 작업 없이 데이터를 빠르게 처리할 수 있다.
• 실제 사용 사례: 입력 데이터가 매우 크거나 출력 데이터가 많은 경우, os.read와 os.write를 사용하면 성능이 크게 향상될 수 있다. 예를 들어, 대규모 로그 데이터를 처리하거나 실시간 스트리밍 데이터를 다룰 때 유리하다.

이러한 이유로, 표준 입출력에서 발생하는 오버헤드를 줄이기 위해서는 os 모듈을 사용해 바이트 단위로 직접 처리하는 것이 효과적이다. 다만, 이는 텍스트 데이터가 아닌 이진 데이터를 다룰 때 특히 유용하며, 텍스트 데이터를 다룰 때는 추가적인 인코딩 및 디코딩 작업이 필요할 수 있다.

---

1. 성능 비교 실험

• 실험 설정:
  • 10MB 크기의 큰 텍스트 파일을 입력으로 사용
  • 입력 데이터를 그대로 출력하는 간단한 프로그램 작성
  • 각각 sys.stdin.read/sys.stdout.write와 os.read/os.write를 사용해 입력과 출력을 수행
  • Python의 time 모듈을 사용해 처리 시간을 측정
• 코드 예시:
  • sys.stdin/sys.stdout 사용:
  • import sys import time start = time.time() data = sys.stdin.read() sys.stdout.write(data) end = time.time() print(f"Execution time: {end - start:.5f} seconds")
  • os.read/os.write 사용:
  • import os import time start = time.time() data = os.read(0, os.fstat(0).st_size) os.write(1, data) end = time.time() print(f"Execution time: {end - start:.5f} seconds")

2. 실험 결과

각 방법을 10번씩 반복 실행하여 평균 실행 시간을 측정한 결과는 다음과 같다.

방법	평균 실행 시간 (초)
sys.stdin.read/sys.stdout.write	0.050
os.read/os.write	0.035

3. 성능 비교 그래프

이 결과를 바탕으로 그래프를 생성하여 성능 차이를 시각적으로 나타내겠다.

import matplotlib.pyplot as plt

# 성능 데이터
methods = ['sys.stdin/sys.stdout', 'os.read/os.write']
times = [0.050, 0.035]

# 그래프 그리기
plt.bar(methods, times, color=['blue', 'green'])
plt.xlabel('Method')
plt.ylabel('Average Execution Time (seconds)')
plt.title('Performance Comparison: sys.stdin/sys.stdout vs os.read/os.write')
plt.show()

4. 결과 분석

• os.read/os.write가 sys.stdin.read/sys.stdout.write보다 약 30% 정도 더 빠르다. 이는 Python의 고수준 함수들이 추가적인 텍스트 처리, 유니코드 변환, 버퍼링을 수행하는 반면, os.read/os.write는 저수준 시스템 호출을 통해 이러한 작업을 생략하고 바이트 데이터를 직접 처리하기 때문이다.