개요

이 시리즈는 프로그래밍 문제를 CPython으로 풀 때 실행 시간을 최적화하는 방법에 대해 다룹니다.^[1]

파이썬 코드를 실행할 때, 인터프리터 방식의 CPython보다 JIT 컴파일을 지원하는 PyPy를 사용하는 것이 훨씬 더 빠릅니다. 그렇기에 PS를 하는 대다수의 사람은 PyPy를 구현체로 이용합니다. 하지만 이 시리즈에서는 CPython만을 다루겠습니다. 제가 거의 CPython만 쓰기 때문입니다.^[2]

CPython으로 실행 시간을 줄이기 위해 노력하다 보면, 더 빠른 CPython 코드를 작성하는 방법은 생각보다 훨씬 까다롭다는 사실을 깨닫게 됩니다. 그 양은 블로그 글 하나로는 다 담을 수 없을 정도로 방대하죠.

이 글에서는 파이썬 코드를 프로파일링 하는 방법에 대해 다루고, 다음 글에선 기초적인 팁과 빠른 입출력에 대해 이야기 해 보려고 합니다.

프로파일링 하기

실행 시간을 줄이기 위해 최적화를 할 때에는, 감으로 찍거나 원인/결과를 막연히 예상해서는 안 됩니다. 프로그램의 성능에 영향을 줄 수 있는 요소가 매우 많기 때문입니다.

이 시리즈에서 다룰 팁조차, 사실 "일반적으로는 이렇다~" 정도의 내용이여서, 실제로 적용했을 때 실행 시간이 줄어들 거라고 보장할 수 없습니다.

또한, 실제로 실행 시간이 줄어들더라도, 애초에 최적화를 진행한 부분의 원래 실행 시간이 짧았다면, 총 실행 시간이 들인 노력에 비해 그다지 줄어들지 않게 됩니다. (암달의 법칙으로 알려져 있죠.)

따라서, 실제로 프로파일링을 해서 어느 부분을 개선해야 실행 시간을 제일 효율적으로 줄일 수 있는지, 그리고 최적화를 진행한 이후 정말로 실행 시간이 개선되었는지 검증하는 것이 매우 중요합니다.

time

time 모듈을 이용하면, 파이썬 코드의 실행 시간을 간단하게 측정할 수 있습니다.

# 벤치마크 할 함수
arr = list(range(1_000_000))

def add_1():
    total = 0
    for x in arr: total += x
    return total

def add_2():
    return sum(arr)

# 실행 시간 측정
from time import time

for func in [add_1, add_2]:
    t_start = time()
    for _ in range(100): func()
    t_end = time()

    print(f"{func.__name__}:", t_end - t_start)

이 방법의 장점은, 무엇보다 세팅이 간단하다는 점입니다. 실행 시간을 측정하고 싶은 코드 앞에 t_start = time(), 뒤에 t_end = time(); print(t_end - t_start)만 적으면 되니까요.

하지만 이 간단한 방식에는 많은 함정들이 도사리고 있습니다.

• 가비지 컬렉션이 시간에 불규칙적인 영향을 줄 수 있습니다.
  • import gc; gc.disable()로 끄면 됩니다.
• 실행 시간을 측정할 때, 여러 가지 외부 요인으로 인해 편차가 발생할 수 있습니다.
  • 다른 프로세스가 CPU를 잡아먹고 있다던가, 예상치 못한 디스크 I/O 병목이 생긴다던가, ...
  • 같은 코드를 같은 조건에서 실행해도, 이러한 이유들로 인해 5% 정도의 오차가 발생할 수 있습니다.
• 실행 시간이 짧은 코드를 여러 번 돌릴 때, 여러 번 돌리기 위한 루프의 오버헤드가 클 수 있습니다.
• time.time()은 사실 실행 시간을 측정할 때 부적절합니다.
  • 윤초 등의 영향을 받을 수 있습니다.
  • 시스템 시간이 변경되면, 그 영향을 받을 수 있습니다.
  • 초 단위 미만의 정밀도로 제공되지 않을 수 있습니다.^[3]

이 중, 마지막 문제는 time.time() 대신 다른 함수를 사용해서 회피할 수 있습니다.

• time.monotonic()은 시스템 시간 영향 없이, 단조 증가하는 시각을 반환합니다.
• time.perf_counter()는 제일 정확도가 높은 시각을 반환하는데, CPython에서는 time.monotonic()과 같은 값을 반환합니다.
• time.process_time()는 CPython 프로세스가 CPU를 점유 중인 시간만을 반환합니다.

time.monotonic(), time.perf_counter(), time.process_time() 모두 기준이 되는 점이 명시되어 있지 않음에 주의해 주세요. 두 값의 차이만 의미를 가지며, 단일 값 그 자체로는 아무런 의미를 지니지 않습니다.

겉보기에는 time.process_time()가 더 좋아 보일 수도 있지만, 실행 시간 측정에는 time.perf_counter()를 쓰는 것이 더 적절합니다. time.process_time()은 프로세스 실행이 컨텍스트 스위칭 등으로 멈춰 있을 때에는 동작하지 않는데, 그런 것들이 우리가 측정하고 싶은 코드의 성능의 일부로서 고려되어야 하기 때문입니다.

즉, time을 사용하여 정확하게 시간을 재려면, 다음과 같이 해야 합니다.

• time.perf_counter(), 혹은 time.perf_counter_ns()를 이용하여 시각을 측정한다.
• 테스트 할 코드가 실행 중일 때에는, 가비지 컬렉터를 끈다.^[4]
• 실행 시간 편차를 줄이기 위해, 여러 번 코드를 실행하고 평균, 표준편차 등을 활용한 통계적 분석을 한다.
• 실행 시간이 짧은 코드를 여러 번 돌릴 때, 오버헤드를 최소화해야 한다.

다행히도, 파이썬에서는 코드 실행 시간 측정을 위한 모듈을 제공해주고 있습니다.

timeit

timeit 모듈은 파이썬 코드의 실행 시간을 측정할 때 도움이 되는 도구들을 모아 놓은, 파이썬에서 기본으로 제공해 주는 모듈들 중 하나입니다.

파이썬 문서에 다음과 같이 설명되어 있습니다.

It avoids a number of common traps for measuring execution times.

이 모듈은 실행 시간을 측정할 때 빠지기 쉬운 함정을 피합니다.

timeit 사용하기

제일 심플하게는, 터미널에서 직접 모듈을 호출할 수 있습니다.

python -m timeit "for _ in range(10**6): pass"

20 loops, best of 5: 10.3 msec per loop

코드에서 timeit을 임포트해서 직접 호출할 수도 있습니다.

import timeit

# 0.010...
print(timeit.timeit("for _ in range(10**6): pass", number=1))

문자열 뿐만 아니라, 함수를 이용할 수도 있습니다.

import timeit

def bench():
    for _ in range(10**6): pass

print(timeit.timeit(bench, number=1))

timeit.Timer를 사용해 더 유연한 벤치마킹 코드를 작성할 수도 있는데, 자세한 사항는 관련 문서를 참고해 주세요.

timeit 작동 방식

timeit은 파이썬으로 구현되어 있으며, 내부적으로는 time을 사용합니다만, 위에서 언급한 함정들을 회피하고 있습니다.

• 시간 측정 직전 gc.disable()를 호출합니다.
  • 물론, 기존에 GC를 사용하고 있었다면 시간 측정 이후 다시 활성화 해 주죠.
• 반복 측정을 위해, 한 번 시간 측정시 주어진 함수를 여러 번 돌리는 기능을 제공해 주고 있습니다.
  • timeit.timeit: number로 함수를 몇 번 돌릴지 정할 수 있습니다.
  • timeit.repeat: repeat로 측정 횟수를 정할 수 있습니다.^[5]
  • timeit.Timer 클래스에서 반복 횟수를 자동으로 정해 주는 autorange() 함수를 제공하고 있습니다.
• 반복 측정을 위해 루프를 돌릴 때, for 루프 직전에 측정을 시작하고, for 루프 직후에 측정을 끝냅니다.
  • for 루프 오버헤드도 range 대신 itertools.repeat를 통해 최소화하고 있습니다. 이 점에 대해서는 나중 글에서 다룰 예정입니다.
• 기본 타이머로 time.perf_counter를 사용합니다.

더 장확한 시간 측정을 위한 여러 팁들이 존재하지만, 이 글에서는 생략하겠습니다.^[6]

파이썬 코드의 실행 시간을 측정하는 데에는 timeit으로 충분합니다만, 실제로 최적화를 진행할 때 timeit만으로 부족할 때가 있습니다. timeit은 코드의 전체 실행 시간만 측정할 수 있고, 노가다로 코드를 분해해 각각의 실행 시간을 측정하지 않는 이상, 구체적으로 코드의 어느 부분이 시간을 많이 잡아먹는지 알려주지는 않기 때문입니다.

다행히도, 파이썬에서는 코드 실행 시간 분석을 위한 모듈을 제공해주고 있습니다.

cProfile

아떤 함수를 최적화해야 큰 효과를 볼 수 있는지 알려면, 어떤 함수의 실행 시간이 오래 걸리는지를 파악해야 합니다. 파이썬에서는 이를 위해 cProfile 모듈을 제공합니다.^[7]

def func_1():
    return sum(range(10_000_000))

def func_2():
    return "".join(map(str, range(10_000_000)))

def func_3():
    return min(range(10_000_000))

def test():
    func_1()
    func_2()
    func_3()

test()

위와 같은 코드를 test.py로 저장한 뒤, 터미널에서 아래와 같이 cProfile을 실행하면...

python -m cProfile test.py

... 혹은, 다음과 같은 코드를 test.py 밑에 덧붙인 다음, test.py를 실행하면...^[8]

import cProfile
cProfile.run("test()")

... 이렇게 결과가 출력됩니다.

         10 function calls in 1.493 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.493    1.493 {built-in method builtins.exec}
        1    0.000    0.000    1.493    1.493 test.py:1()
        1    0.005    0.005    1.493    1.493 test.py:10(test)
        1    0.000    0.000    1.098    1.098 test.py:4(func_2)
        1    1.098    1.098    1.098    1.098 {method 'join' of 'str' objects}
        1    0.000    0.000    0.246    0.246 test.py:1(func_1)
        1    0.246    0.246    0.246    0.246 {built-in method builtins.sum}
        1    0.000    0.000    0.144    0.144 test.py:7(func_3)
        1    0.144    0.144    0.144    0.144 {built-in method builtins.min}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

각 열 별 설명은 다음과 같습니다.

• ncalls: 함수가 실행된 총 횟수입니다.
• tottime: 함수를 실행하는 데 걸린 시간에서, 함수에서 호출 된 함수들을 실행하는 시간을 뺀 시간입니다.
• cumtime: 함수를 실행하는 데 걸린 총 시간입니다. 함수에서 호출된 다른 함수들의 실행 시간을 포함합니다.
• percall: tottime 또는 cumtime을 호출 횟수 ncalls로 나눈 값입니다.

즉, 위의 예시 출력은 다음과 같이 해석할 수 있습니다.

• func_1, func_2, func_3 중, 제일 실행 시간이 오래 걸린 함수는 func_2입니다.
• func_2 자체적으로 소모한 시간은 없지만, "".join을 실행하는 데 모든 시간을 보내고 있습니다.

출력에도 적혀 있듯이, 기본적으로 cProfile은 cumtime이 감소하는 순으로 정렬해서 출력해 줍니다.

아쉽게도, cProfile이 최적화 할 함수의 후보를 좁혀줄 수는 있지만, 함수 내부에서 구체적으로 어느 부분을 실행하는 데 오랜 시간이 걸리는지 파악하기는 어렵습니다. 특히, 실행 시간이 오래 걸리면서 긴 함수의 cumtime과 tottime이 비슷할 때에는 (= 이 함수 내부에 시간이 오래 걸리는 원인이 있고, 하위 함수는 원인이 아닐 가능성이 클 때), 어느 부분을 최적화해야 하는 지 파악하기는 어렵습니다.

다행히도, 파이썬에서는 이 문제를 해결할 수 있는 모듈... 이 없네요?! 아 이런. 서드 파티 라이브러리를 사용 할 수밖에 없네요.

line_profiler

파이썬 코드의 각 줄의 실행시간을 측정해 주는 라이브러리는 몇몇이 있습니다만, 그 중 제일 간단하게 사용할 수 있는 모듈은 line_profiler인 듯 합니다.

https://github.com/pyutils/line_profiler (사용 설명서)

사용 방법은 간단합니다. 우선, 실행 시간을 자세히 파악하고 싶은 함수에 @line_profiler.profile 데코레이션을 추가 해 줍니다.

from line_profiler import profile

def func_1():
    return sum(range(10_000_000))

def func_2():
    return "".join(map(str, range(10_000_000)))

def func_3():
    return min(range(10_000_000))

@profile
def test():
    func_1()
    func_2()
    func_3()

test()

이 상태에서 코드를 실행하면 아무 일도 일어나지 않습니다.

프로파일을 생성하려면, LINE_PROFILE 환경 변수를 1로 설정 해 주어야 합니다.

• 리눅스에서는 LINE_PROFILE=1 python test.py와 같이 파이썬을 실행하거나, export LINE_PROFILE=1을 해 주면 됩니다.
• 윈도우 파워셸에서는 $env:LINE_PROFILE=1을 실행한 다음 python test.py를 실행 해 주면 됩니다.

LINE_PROFILE 환경 변수를 설정한 상태에서 프로그램을 실행하면, 다음과 같이 profile_output.txt 텍스트 파일이 생성됩니다.

Timer unit: 1e-07 s

Total time: 1.38873 s
File: test.py
Function: test at line 12

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    12                                           @profile
    13                                           def test():
    14         1    2383045.0    2e+06     17.2      func_1()
    15         1   10242448.0    1e+07     73.8      func_2()
    16         1    1261769.0    1e+06      9.1      func_3()

  1.39 seconds - test.py:12 - test

각 줄을 실행하는 데 걸린 시간과, 함수 전체 대비 몇 퍼센트의 비중을 차지하는지 한 눈에 볼 수 있습니다.

line_profiler를 사용할 때 한 가지 주의해야 할 점이 있습니다. cProfile과는 다르게, 이 도구를 사용할 때의 오버헤드는 상당히 큽니다. 벤치마크 용도로는 당연히 부적합할 뿐만이 아니라, 실행 시간이 오래 걸리기 때문에 프로파일을 얻을 때 까지 오랜 시간 프로그램을 실행해야 한다는 점을 주의해야 하죠.

워크플로우

위 도구들을 잘 섞어 쓰면, 아래와 같이 파이썬 코드를 최적화할 수 있습니다.

1. print 디버깅을 하면서 가볍게 코드 실행 시간을 측정하고자 할 때에는, time.perf_counter()를 사용합니다.
2. 코드 실행 시간을 최적화하고 싶을 때에는, 우선 cProfile로 실행 시간이 오래 걸리는 함수를 찿아냅니다.
3. 그 다음, 더 필요하다면 line_profiler를 이용해 문제가 되는 로직을 찾아냅니다.
4. 코드를 "잘" 최적화합니다.
   • 필요하다면 timeit을 이용해 갈피를 잡습니다.
   • "잘"을 어떻게 하면 되는지는 나중에....
5. 최적화 이전 코드와 이후 코드를 timeit을 이용해 벤치마크해서, 최적화가 잘 이루어졌는지 확인합니다.

벤치마크 유틸리티 코드

timeit을 직접 활용하는 것은 번거롭습니다. 특히, 두 코드의 실행 시간을 비교할 때에는, 큰 편차 때문에 정말로 실행 시간이 개선되었는지 판단하기 난감하죠.

그 문제를 해결하기 위해, 유틸 코드를 작성했습니다.

아래에는 통계 분석^[9]을 위한 StatList가 빠진, 간략화 된 코드입니다.

from typing import Callable, TypeAlias, List, Any, Dict
import timeit, statistics

def stdev_range(times: List[float]) -> str:
    if not times: return "(empty)"
    if len(times) == 1: return f"{times[0]:.3f} s"
    
    mean, stdev = statistics.mean(times), statistics.stdev(times)
    
    return f"{mean:.3f} \xB1 {stdev:.3f} ({min(times):.3f} to {max(times):.3f}) s"

BenchTarget: TypeAlias = Callable | str

def bench(
    stmts: List[BenchTarget] | BenchTarget,
    repeats_per_trial: int = 1,
    num_trials: int = 5,
    *,
    timer = timeit.default_timer,
    global_vars: Dict[str, Any] | None = None,
    log: bool = True,
) -> List[List[float]] | List[float]:
    stmts_list = [stmts] if (single := not isinstance(stmts, list)) else stmts
    if not stmts_list: return []

    names_list = [getattr(s, "__name__", f"Code #{i}") for i, s in enumerate(stmts_list, 1)]

    stats = [[] for _ in stmts_list]
    timers = [timeit.Timer(stmt, timer=timer, globals=(global_vars or globals())) for stmt in stmts_list]
    
    for _ in range(num_trials):
        for s, t in zip(stats, timers): s.append(t.timeit(number=repeats_per_trial))
    
    if log:
        name_w = max(map(len, names_list))
        for name, times in zip(names_list, stats):
            print("{}: {}".format(name + " "*(name_w - len(name)), stdev_range(times)))

    return stats[0] if single else stats

위 코드는 퍼블릭 도메인으로 공개하며, 자유롭게 퍼 가셔도 됩니다.

• stmts: 벤치마크를 실행할 함수, 코드 문자열, 또는 그 목록입니다.
• repeats_per_trial: 한 번 실행 시간을 측정할 때, 주어진 함수를 몇 번 반복할지 정합니다.
• num_trials: 실행 시간 측정을 각 함수 종류별로 총 몇 번 할지를 정합니다.
• timer: 시간을 측정할 타이머의 종류입니다. (기본값: timeit.default_timer)
• global_vars: 전역 변수 네임스페이스입니다. (기본값: globals())
• log: 함수를 실행할 때, 로그를 출력할 지 여부를 정합니다. (기본값: True)

stmts의 각 함수를 한 번씩 실행하는 과정을 반복하게 하여, 파이썬 외부적 요인으로 인한 오차를 최대한 골고루 분산시키려 노력했습니다.

예시

A = list(range(10_000_000))

def test_a():
    L = []
    for x in A: L.append(x)

def test_b():
    La = (L := []).append
    for x in A: La(x)

def test_c():
    L = []
    L.extend(A)

bench([test_a, test_b, test_c], num_trials=10)

test_a, test_b, test_c 중 제일 빠른 코드가 test_c일 것임은 쉽게 예측할 수 있습니다. 그렇다면, test_a와 test_b 중 어느 쪽이 더 빠를까요?

간단히 생각해 보면, 둘 사이 눈에 띄는 성능의 차이가 없거나, .append 속성을 매번 찾지 않는 test_b가 조금이나마 더 빠를 것 같습니다.

하지만 실제로 실행해 보면, 의외의 결과를 얻게 됩니다.

test_a: 0.451 ± 0.036 (0.401 to 0.504) s
test_b: 0.484 ± 0.040 (0.437 to 0.537) s
test_c: 0.133 ± 0.014 (0.117 to 0.153) s

통계 분석을 포함한 결과는 다음과 같습니다. 통계적으로도 유의미하게 test_a가 test_b보다 빠른 것을 확인할 수 있습니다.

test_a : 0.448 ± 0.033 (0.404 to 0.515) sec
test_b : 0.496 ± 0.036 (0.453 to 0.563) sec # slowest (p=0.001)
test_c : 0.131 ± 0.013 (0.111 to 0.151) sec # fastest (p=0.000)

#1 | test_c : 0.131 ± 0.013 (0.111 to 0.151) sec |                           faster than #2 (p=0.000)
#2 | test_a : 0.448 ± 0.033 (0.404 to 0.515) sec | slower than #1 (p=0.000), faster than #3 (p=0.001)
#3 | test_b : 0.496 ± 0.036 (0.453 to 0.563) sec | slower than #2 (p=0.001)

L.append(x)가 La(x)보다 빠른 원인을 알기 위헤선, 조금 깊게 파고 들어가야 합니다.

test_a의 for 루프의 바이트코드는 이렇습니다.

      L1:     FOR_ITER                19 (to L2)
              STORE_FAST_LOAD_FAST    16 (x, L)
              LOAD_ATTR                3 (append + NULL|self)
              LOAD_FAST                1 (x)
              CALL                     1
              POP_TOP
              JUMP_BACKWARD           21 (to L1)
      L2:     END_FOR

(TODO: 파이썬 바이트코드 문법 강조 블로그에 추가하기....)

1. STORE_FAST_LOAD_FAST: for 루프로 뽑은 변수를 x에 저장하고, 동시에 L을 스택에 넣습니다.^[10]
2. 최하위 비트가 설정된 LOAD_ATTR는 L에서 append를 찾아, 스택의 맨 위를 L과 바운드되지 않은 L.append로 바꿉니다.
3. x를 불러옵니다.
4. CALL로 L.append를 호출하는데, self를 L로, 인자를 x로 둔 상태로 호출합니다.

그리고 이건 test_b의 for 루프입니다.

      L1:     FOR_ITER                10 (to L2)
              STORE_FAST_LOAD_FAST    33 (x, La)
              PUSH_NULL
              LOAD_FAST                2 (x)
              CALL                     1
              POP_TOP
              JUMP_BACKWARD           12 (to L1)
      L2:     END_FOR

1. STORE_FAST_LOAD_FAST: test_a때와 동일하나, 스택의 맨 위에는 La가 들어갑니다.
2. NULL을 스택에 넣습니다.
3. x를 불러옵니다.
4. CALL로 La를 호출하는데, self를 NULL로, 인자를 x로 둔 상태로 호출합니다.

즉, L.append 대신 La를 호출하게 되면, LOAD_ATTR를 안 해도 되는 대신 PUSH_NULL를 호출해야 하기 때문에^[11], 실행 시간에 별 다른 이득을 얻지 못하게 됩니다.

그런데 아무리 생각해도 PUSH_NULL의 구현이 LOAD_ATTR보다 더 간단할 것 같은데^[12], 왜 실행 시간은 PUSH_NULL을 사용한 쪽이 오히려 더 길까요? 이 질문에 대한 답을 찾는 것은 어려워 보입니다....

이렇듯, 파이썬 최적화의 세계는 심오하면서도 불합리합니다.

다음 글에서는 파이썬에서 코드를 최적화 할 때 알아두면 좋은 일반적인 팁과, 빠른 입출력을 위한 다양한 팁에 대해 알아보겠습니다. 미리 힌트를 주자면, sys.stdin.readline이 전부가 아닙니다....

---

1. 실행 시간을 줄이는 것에 집중합니다. 메모리 사용량 등의 다른 요소는 다루지 않습니다. ↩︎

2. 여러 가지 이유가 있습니다. "이왕이면 최신 버전의 파이썬을 쓰고 싶다", "짧은 코드는 CPython에서 실행 시간이 더 빠르다", "CPython으로 통과시키는 게 재밌잖아", "PyPy 세팅이 귀찮아서", 기타 등등... ↩︎

3. 뭐, 보통은 ms 단위까지는 충분히 제공해 주는데다, time.time_ns()를 쓰면 해결 가능한 문제이기 때문에 그다지 큰 문제는 아닙니다. ↩︎

4. 다음 글에서 다시 언급하겠지만, 가비지 컬렉터는 항상 꺼 놓아도 됩니다. 즉, 가비지 컬렉션이 코드 실행 시간에 영향을 주지 못한다고 가정해야 합니다. ↩︎

5. timeit 모듈 문서에서는 이렇게 반복해서 측정할 시, 최솟값을 제외한 값은 파이썬에 의한 시간 변동이 아닌, 외부 요인으로 인한 시간 변동에 더 큰 영향을 받기 때문에, 별 의미가 없다고 합니다. 평균이나 표준편차 같은 통계값을 보지 말고, 측정한 시간 값들을 직접 보고 "상식적"으로 판단하라고 하고 있죠. 근거 없는 말은 아닙니다만, 제가 보기에는 최솟값을 보기 보다는 컴퓨터가 안정화 된 상태에서 여러번 돌리고 통계값을 내는 것이 더 나아 보입니다. (참고) ↩︎

6. 리눅스에서 taskset을 (윈도우에서는 cmd에서 start /affinity를) 사용하면 더 안정적으로 시간 측정이 가능하다던가.... ↩︎

7. cProfile을 사용함으로써 생기는 부하가 작기는 하지만, 그래도 부하가 없지는 않기 때문에 cProfile을 벤치마크 용도로 사용하는 건 부적절한 점에 주의해 주세요. ↩︎

8. 파이썬 IDLE 셸에선 부정확한 결과가 나올 수 있으니 조심해 주세요. ↩︎

9. 앞 각주에서 설명했듯이, timeit 모듈 문서에서는 이러지 말라고 하긴 합니다만.... ↩︎

10. STORE_FAST_LOAD_FAST는 "superinstruction" 중 하나이며, 파이썬 3.11에 추가된 기능들 중 하나입니다. ↩︎

11. 파이썬 3.10까지는 PUSH_NULL이 필요 없는 CALL_FUNCTION opcode가 있었는데, 왜 삭제된 것인지 의문이네요. ↩︎

12. 실제로도 그렇습니다. (Python/bytecodes.c, Python/generated_cases.c.h 참고) ↩︎

개요

저는 개발할 때 주로 자바스크립트를 사용합니다만, 취미로 프로그래밍 문제를 풀 때에는 자바스크립트가 아닌 파이썬을 정말 많이 즐겨씁니다. 파이썬이 프로그래밍 문제를 풀 때 여러모로 이점이 많기 때문이죠.

우선, 파이썬의 문법은 간결합니다. 예를 들어, BOJ 8073번을 C++로 푼다면 이렇게 됩니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    size_t N;
    cin >> N;
    
    vector<vector<int>> A{N, vector<int>(N)};
    for(auto& row : A) for(auto& v : row) cin >> v;

    auto isNeighbouring = [&](int i, int j) {
        for(int k=0; k<N; ++k) {
            if(k==i||k==j) continue;
            if(A[i][k] + A[k][j] == A[i][j]) return false;
        }

        return true;
    };
    
    for(int i=0; i<N-1; ++i) {
        for(int j=i+1; j<N; ++j) {
            if(isNeighbouring(i, j))
                cout << i+1 << ' ' << j+1 << '\n';
        }
    }
    
    return 0;
}

(C++에서 using namespace std;는 별로 권장되지 않는 습관임을 주의해 주세요.)

같은 로직^[1]을 파이썬으로 적으면 다음과 같습니다.

N, *A = open(0)
N = int(N)
A = [list(map(int, row.split())) for row in A]

is_neighbouring = lambda i, j: \
    not any(A[i][k] + A[k][j] == A[i][j] for k in range(N) if k not in (i, j))

for i in range(N-1):
    for j in range(i+1, N):
        is_neighbouring(i, j) and print(i+1, j+1)

(함수 is_neighbouring에서 문제의 지문을 최대한 그대로 옮기기 위해 all 대신 일부러 not any를 썼습니다.)

파이썬 쪽이 자연어스러워서 조금 더 읽기 편하고 간결하죠. 개인적으로 파이썬의 제너레이터 문법이 정말 마음에 듭니다.^[2]

파이썬의 또 다른 강점은 "배터리 포함" 철학입니다. 제가 제일 좋아하는 언어는 앞서 언급한 자바스크립트입니다만, 불행하게도 자바스크립트에는 "표준 라이브러리"로서 제공되는 것 중, 프로그래밍 문제 풀이에 유용한 것은 거의 없습니다. 반면에, 파이썬 표준 라이브러리에는 프로그래밍 문제를 풀 때 유용한 것이 매우 많습니다.^[3]

하지만 이런 이점에도 불구하고, 입문 수준을 상회하는 프로그래밍 문제를 풀 때에는 파이썬은 C++보다 인기가 덜합니다. 이유는 뻔합니다. 느리거든요.

C++이나 Rust로 코드를 짜면, 컴파일러가 최적화를 해 주고, 보통은 코드나 구조체에 "불필요한 정보"가 생기지 않기 때문에, 문제에서 의도하는 시간 복잡도로 코드를 작성하기만 하면 웬만해서는 시간 제한을 넘지 않게 됩니다.

반면 파이썬에서는 여러 종류의 오버헤드(PyPy3으로 JIT 컴파일하더라도, 동적 타입이나 언어 스펙에 따른 오버헤드를 피할 수 없음)로 인해 백준 온라인 저지와 같이 시간 보정을 걸어주지 않으면 시간 제한을 넘기기 일쑤입니다. 특히, CPython을 이용하는 경우 시간 보정이 걸리더라도 최적화에 신경 쓰지 않으면 풀리지 않는 문제들이 많죠.

그래도 파이썬은 특유의 매력이 있습니다. 대체적으로, 읽기 편한 파이썬 코드는 짧을 뿐만 아니라 성능도 더 좋은 경향이 있습니다. 즉, 파이썬 표준 라이브러리에 있는 함수들을 잘 이용해 사용하고 싶은 알고리즘을 최대한 자연스럽게 코드에 녹아내면, 그게 곧 파이썬 최적화가 됩니다.^[4]

이 시리즈에서는 제가 파이썬으로 프로그래밍 문제를 풀 때, 자주 사용하는 코딩 기법(?)에 대해 다루어 보려 합니다. 이 글에서는 첫 번째로 파이썬에서 입출력을 하는 방법에 대해 알아보면서, 입출력 뿐만 아니라 메인 로직을 짜는 데에도 유용한 파이썬의 문법을 알아 봅시다.

입력

입력이 상대적으로 작으면 (한 10000바이트 이내?), input으로도 충분히 입력을 받을 수 있습니다.

BOJ 1000번을 "기본적인 문법"만으로 풀면 이렇게 풀 수 있겠네요.

arr = input().split()
print(int(arr[0]) + int(arr[1]))

Iterable unpacking은 유용하게 쓰일 수 있지만, 초보자들은 잘 모를 수 있는 문법입니다. 입력을 받을 때 이를 활용하면 코드를 훨씬 간결하게 만들 수 있습니다.

A, B = input().split()
print(int(A) + int(B))

한 줄에 있는 여러 정수를 입력 받을 때에는, map을 활용해 각 데이터를 int로 바꿔 주면 됩니다. 이 경우에는 입력받는 수의 개수가 두 개이므로 사실 필요한 건 아니지만, 입력받는 수의 개수가 많거나 미지수일 때 유용하죠.

A, B = map(int, input().split())
print(A + B)

입력이 상대적으로 크면 sys.stdin.readline을 써야 한다는 사실은 잘 알려져 있죠.

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    A, B = map(int, input().split())
    print(A + B)

한 가지 주의해야 할 점은 sys.stdin.readline의 반환값은 항상 개행 문자 \n이 맨 뒤에 있다는 것입니다. 보통은 그냥 무시해도 되지만, 문자열 입력을 받는 경우에는 .rstrip()으로 제거할 수 있습니다.

한편, 입력 패턴이 간단한 경우에는 앞서 나온 BOJ 8073번을 해결하는 코드와 비슷하게 아래과 같이 적을 수도 있습니다.

N, *Ls = open(0)

for L in Ls:
    A, B = map(int, L.split())
    print(A + B)

구체적으로 첫 번째 줄은 다음과 같이 실행됩니다.

1. 빌트인 함수 open을 통해, file descriptor가 0인 파일(=stdin)의 파일 오브젝트(io.TextIOBase)가 만들어집니다.
2. 타겟에서 iterable unpacking을 하고 있으므로, 1의 파일 오브젝트가 이터레이터로 변환됩니다.
   • io.IOBase의 이터레이터는 스트림의 각 줄을 yield합니다.
3. 따라서 N에는 입력의 첫째 줄이, Ls에는 나머지 줄이 들어가게 됩니다.

정수 목록 입력받기

input, 또는 sys.stdin.readline을 이용해 간단하게^[5] 정수 목록을 입력받는 코드입니다.

# 첫 번째 줄에 목록의 길이가, 다음 줄에 정수 N개가 주어지는 경우.
N = int(input())
A = list(map(int, input().split()))

# 첫 번째 줄에 목록의 길이가, 다음 N개의 줄 각각에 정수가 주어지는 경우.
A = [int(input()) for _ in range(N := int(input()))]

# 한 줄에 목록의 길이 N과 정수 N개가 주어지는 경우.
N, *A = map(int, input().split())

참고로 _, 혹은 _foo와 같이 _로 시작하는 변수명은, 파이썬에서 (match문을 제외하고) 특별한 의미는 없지만, 언어를 가리지 않고 많은 사람들이 "쓰지 않고 버리는 값"을 나타내는데 사용됩니다.

위 코드들에서 N == len(A)이기도 하고, 파이썬스러운 코드를 짜면 N을 직접 쓰지 않는 경우가 많아서, 사실 N을 별도로 읽을 필요는 낮지만, 나중에 쓸모가 있을지도 모르니 웬만해서는 읽어두는 것이 좋습니다.

한편, A가 규칙 없이 여러 줄에 나뉘어진 경우에는... 코드가 C++에 비해 더 복잡해 질 것 같네요....

A가 주어지는 마지막 줄이, A만으로 이루어져 있다면 아래와 같이 적을 수 있습니다.

N, *A = map(int, input().split())
while len(A) < N: A.extend(map(int, input().split()))

list.extend, dict.update, set.update와 같이, 컬렉션에 iterable의 원소를 추가하는 함수들 또한 코드를 간결하게 만드는 데 요긴하게 사용할 수 있습니다.

정수 행렬 입력받기

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

그래프 입력받기

첫 줄에 그래프의 노드와 간선 수, 두 번째 줄부터 그래프의 간선이 1-based 인덱스로 주어지고, 이를 인접 리스트로 저장하는 코드입니다.

N, E = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(E):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    G[u].append(v); G[v].append(v)

저는 문제 지문이 1-based 인덱스를 사용하는 경우에도, 코드 내부적으로는 0-based 인덱스를 사용합니다. 이러는 편이 더 일관성이 있어서 덜 헷갈리기 때문입니다. 다만 이 경우, 입력할 때 -1, 출력할 때 +1을 해 주는 것을 잊지 말아야 합니다.

문제를 풀 때 문제가 생기지 않는다면, 그냥 그래프의 노드 개수를 N+1개로 잡고 풀어도 무방합니다. 다만 이 경우에는 오히려 문제 지문을 읽을 때 1-based와 0-based 인덱스의 혼동이 생길 수 있으니 주의해야 합니다.

한편, u와 v를 입력 받을 때 다음과 같이 받을 수도 있지만...

u, v = map(lambda v: int(v)-1, input().split())

... 코드가 조금 짧아질 수는 있어도 가독성이 떨어져서 별로 권장하지는 않는 방법입니다.

solve 함수

프로그래밍 문제를 풀 때에는 테스트 케이스 하나를 독립적으로 처리하는 solve 함수를 만들어 두는 것이 좋습니다. 당연하지만, solve라는 이름을 쓰는 특별한 이유가 있는 것은 아니고, 다른 이름을 사용해도 무방합니다.

조금 거추장스러울 수는 있지만, 이렇게 하는 게 좋은 데에는 크게 세 가지 이유가 있습니다.

• 작성한 코드를 테스트할 때, solve 함수가 있으면 훨씬 더 편하게 테스트할 수 있습니다.
• 글로벌 변수에 접근하는 것보다 로컬 변수에 접근하는 것이 조금 더 빠릅니다.^[6]
• 가끔 적용되는 경우이긴 한데, solve 함수를 이용해 입출력 코드가 간단해질 수 있습니다.

잠깐 코드 테스트에 대해 이야기 하겠습니다. 예를 들어, BOJ 2042번을 다음과 같이 풀었다고 해 봅시다. 전형적인 세그트리 입문 문제입니다.

import sys; input = sys.stdin.readline

N, M, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

T = [0]*N + A
for i in range(N-1, 0, -1): T[i] = T[2*i] + T[2*i+1]

for _ in range(M+K):
    a, b, c = map(int, input().split())
    b -= 1
    if a == 1:
        b += N
        d = c - T[b]
        while b: T[b] += d; b //= 2
    else:
        s = 0
        b += N; c += N
        while b < c:
            if b&1: s += T[b]; b += 1
            if c&1: s += T[c-1]
            b //= 2; c //= 2
        print(s)

이 코드는 정답입니다만, 만약 모든 예제 입력에 대한 출력이 올바름에도 불구하고 오답 처리되었다면 (일명 "맞왜틀"), 눈 앞이 캄캄해질 수 밖에 없습니다.

하지만 만약 아래와 같이 solve 함수를 만들었다면, ...

import sys; input = sys.stdin.readline

# `solve` 함수, 전역변수 `N`을 사용하지 않는 것 참고.
def solve(A, Q):
    N = len(A)
    T = [0]*N + A
    for i in range(N-1, 0, -1): T[i] = T[2*i] + T[2*i+1]

    for (a, b, c) in Q:
        b -= 1
        if a == 1:
            b += N
            d = c - T[b]
            while b: T[b] += d; b //= 2
        else:
            s = 0
            b += N; c += N
            while b < c:
                if b&1: s += T[b]; b += 1
                if c&1: s += T[c-1]
                b //= 2; c //= 2
            yield s

# 입출력
N, M, K = map(int, input().split())

A = [int(input()) for _ in range(N)]
Q = [tuple(map(int, input().split())) for _ in range(M+K)]

for v in solve(A, Q): print(v)

... 다음과 같이, 시간 복잡도를 희생하는 대신 간단하고 검증이 쉬운 코드를 작성하고...

def solve_naive(A, Q):
    A = A.copy()
    for (a, b, c) in Q:
        b -= 1
        if a == 1: A[b] = c
        else: yield sum(A[b:c])

... 랜덤 테스트 케이스를 생성하는 함수를 만들어서...

from random import randint, shuffle
def make_input():
    N = randint(1, 10)
    M = randint(1, 10)
    K = randint(1, 10)
    vl, vh = -10, 10
    A = [randint(vl, vh) for _ in range(N)]
    QM = [(1, randint(1, N), randint(vl, vh)) for _ in range(M)]
    QK = [(2, (b := randint(1, N)), randint(b, N)) for _ in range(K)]
    Q = QM + QK; shuffle(Q)

    return A, Q

... 검증 코드를 쉽게 짤 수 있게 됩니다.

while True:
    A, Q = make_input()
    
    ans_naive = list(solve_naive(A, Q))
    ans = list(solve(A, Q))

    assert(len(ans_naive) == len(ans))
    if all(x == y for (x, y) in zip(ans_naive, ans)): continue

    print("INCORRECT OUTPUT:")
    print(A, Q)
    print(ans_naive)
    print(ans)
    break 

다행히도(?) 위의 solve는 올바른 코드이기 때문에 어떤 것도 출력되지 않지만, 잘못된 solve를 짰을 때에는 매우 유용하게 쓰일 수 있습니다.

이렇게 랜덤 입력 테스트를 쉽게 할 수 있으려면, 특별한 이유가 없는 한 처음부터 전역 변수를 함수 내에서 참조하지 않게 코드를 짜는 것이 매우 중요합니다.

마찬가지로, solve 함수 안에서 print를 하지 말고, return이나 yield로 값을 반환하게 하는 것이 좋습니다.

solve로 값 넘기기

일반적인 경우에는 별 것 없지만, 종종 다음과 같이 테스트 케이스가 구성되어 있는 경우가 있습니다.

• 첫째 줄에는 테스트 케이스의 개수 N이 주어짐.
• 투 번째 줄부터 N개 줄에는 각각의 테스트 케이스에 대한 입력이 한 줄에 하나씩 주어짐.

이 경우에는 다음과 같이 *를 사용하여 간편하게 solve 함수에 값을 넘겨줄 수 있습니다.

for _ in range(int(input())):
    print(solve(*map(int, input().split())))

solve에서 값 받기

특별한 팁은 없습니다. 굳이 따지자면, 다음 두 가지 팁이 있겠네요.

• return으로 여러 개의 값을 반환할 수 있다는 점을 기억하세요.
• solve 안에서 yield를 써서 값의 목록을 반환할 수도 있습니다.
  • 다만, solve 안에서 리스트를 만들어 반환하는 게 거추장스럽지 않다면, 그렇게 해 주세요.

def solve():
    yield 12
    yield 34

ans = list(solve())

# 또는

for x in solve(): pass

출력

입력값을 받을 때 그냥 input을 사용하면 시간이 오래 걸릴 때가 많지만, 사실 print는 sys.stdout.writeline 대신 그냥 써도 대부분의 경우 큰 상관은 없습니다.

또한, print의 flush 인자의 기본값은 False이기 때문에, 출력 버퍼를 비우는 오버헤드를 걱정할 필요도 없습니다. 오히려 인터랙티브 문제를 풀 때, print(..., flush=True)를 해 주어야 하는 점을 명심해야 합니다.

한편, 값의 목록을 출력할 때에는 두 가지 소소한 팁이 있습니다.

• print(*arr)처럼 *를 사용하면, arr의 모든 원소를 공백으로 구분하여 출력할 수 있습니다.
  • " ".join을 쓰는 경우 arr의 모든 원소가 문자열이어야 하므로, " ".join(map(str, arr))등과 같이 거추장스러워 지는 것보다 편합니다.
  • print의 sep 인자를 적절히 사용해서, 구분자를 다른 문자로 바꿀 수도 있습니다.
• 정수를 여러 줄에 걸쳐 출력하는 문제 중 상당수의 채점기는, 실제로 개행 문자가 제 때 들어갔는지 확인하지 않습니다. 즉, 한 줄에 모든 정수를 print(*arr)와 같은 방식으로 출력해도 정답처리 될 때가 많습니다.

---

1. 사실 C++를 약간 봐 줬습니다. FastIO도 안 쓰고, 몇몇 컴파일러 경고도 무시했습니다. ↩︎

2. C++의 ranges와 비교하면 더욱 그렇습니다. ↩︎

3. 이 점에서 파이썬의 단 한 가지 아쉬운 점이라면 C++의 std::set처럼 "정렬 집합"이 존재하지 않는다는 것입니다. ↩︎

4. 불행하게도, 이건 어느 정도 수준을 넘어서는 최적화를 할 때에는 아닐 수도 있습니다. 파이썬, 특히 CPython에서의 최적화는 골치 아픈 점들이 많이 있는데, 이 점에 대해서는 이 글이 아닌, 나중 글에서 다룰 생각입니다. ↩︎

5. 이 글의 코드는 대부분의 문제를 충분히 빠르게 풀 수 있는 "간결함"에 중점을 두며, "제일 빠른" 코드에 대해 다루지는 않습니다. ↩︎

6. 글로벌 변수에 접근할 때에는 LOAD_NAME, 로컬 변수에 접근할 때에는 LOAD_FAST를 사용하기 때문인데... 자세한 건 이 글에서 다루지 않겠습니다. 큰 차이는 아닙니다. ↩︎

원래 0xF.kr 서버는 AWS에 살고 있었는데, GCP와 비교하여 여러 가지 불편한 점들이 있었습니다. 그래도 뭐, 여태껏 잘 돌아가고 있었으니 그냥 놔 두었죠.

그런데, 서버 리눅스 (정확히는 Debian) 버전을 올리려다, 큰 실수를 해 버리는 바람에 서버가 죽어버렸습니다. 중요한 자료는 GitHub이나 기타 다른 곳에 백업이 되어 있지만, 그래도 뼈아픈 일이었습니다.

거기에다가, 최근에 바쁜 일들이 많이 있어서, 홈페이지를 다시 세우는 데 소홀해졌었습니다. 그래서 지금까지도 0xF.kr는 반 죽어있는 상황입니다. (몇 가지 업그레이드되어 돌아온 게 있기는 합니다. s.0xF.kr이라던가...)

그런데 이것 저것 뻘글을 적어 올릴 곳이 없어서 답답하더라고요. 그래서 블로그를 다시 구축하기로 마음을 먹었습니다.

사용한 기술 스택

Static Site Generator

바닥부터 만드는 게 제일 마음 편하긴 해도, 너무 시간이 오래 걸리고 귀찮기도 하죠. 그래서 기존에 있던 솔루션 중 제 입맛에 맞는 걸 골라 쓰기로 마음 먹었습니다.

참고로 이전에 썼던 건 Hexo였습니다.

제가 원하는 것은 다음과 같았습니다.

• 높은 보안성
• 단순한 테마 커스터마이징 이상의, 이왕이면 HTML을 직접 조작할 수 있는 정도의 높은 유연성
• 이왕이면 JavaScript 기반 (다른 언어 인터프리터/컴파일러를 안 깔고 쓸 수 있었으면...)
• Markdown을 이용한 게시글 작성 (핫 리로딩이 되면 좋음)
• Syntax highlight 지원
• LaTeX 수식 지원

예를 들어, Wordpress는 보안적으로 도저히 믿을 수도 없고, PHP를 필요로 하기 때문에 완전히 아웃입니다.

"높은 보안성"을 제일 쉽게 달성할 수 있는 방법은 그냥 블로그를 통째로 정적 웹 사이트로 만드는 것입니다. 즉, 제가 원하는 것은 "JavaScript 기반의, 마크다운으로 작성한 글을 입력으로 받을 수 있는, 확장성 높고 유연한 정적 웹 사이트 생성기"가 됩니다.

궁리 끝에 11ty를 골랐습니다. 유연성이 너무나도... 뛰어나서... 템플릿을 만들고 설정하는 데 한 세월이 걸리는 것이 단점이지만... 제 니즈를 어느 정도 충족시킵니다.

문법 강조도 지원하고...

function main() {
    const message: unknown = "Hello, world!";
    console.log(message as string);
}

// ?!
if(__name__ === '__main__') {
    main();
}

KaTeX를 이용하면 LaTeX도 사용 가능하죠.

$$\begin{aligned} [x^k] (1+x)^n &= \binom{n}{k} \\ \sum_{k=0}^{n} \binom{n}{k} &= \sum_{k=0}^{n} \binom{n}{k} 1^k \\ &= (1+1)^n = 2^n \end{aligned}$$

CD

기존에 블로그가 방치되었던 가장 큰 이유가 매번 글을 적을 때 마다 사이트를 직접 생성해 줘야 해서였는데, 이 귀차니즘을 해결하기 위해 다음과 같은 해법을 생각했습니다.

1. 블로그를 GitHub에 올림.
2. 워크플로우를 통해, 블로그 글이 업데이트 될 때 마다 사이트 내용을 artifact로 생성.
3. 생성된 사이트를 전달받아 자동으로 deploy.

그런데, 3번 과정은 어떻게 해야 하죠...?

뭐, 해법이야 여러 가지가 있을 수 있지만, 해법들은 뭔가 다 마음에 안 들거나 너무 복잡하고, 제 서버에 직접 띄우는 선에서 최대한 심플하게 가고 싶단 말이죠...

그래서 워크플로우 완료 웹훅을 받으면 아티팩트를 받아 지정된 경로에 푸는 프로그램을 만들어 보았습니다.

(출처, CC BY-NC 2.5)

뭐, 최소한의 기능을 하긴 합니다만... 잘 돌아가니까 당분간은 몇몇 프로젝트에 이걸 쓰려고 합니다.

(참고로 s.0xF.kr는 GitHub Pages로 띄워놓고 있는 중입니다.)

스타일

블로그에 쓰인 스타일은 간단한 HTML 웹 페이지에 쓰려고 제가 만든 NalCSS를 사용합니다만, 이 CSS 파일은 아직 부족한 점이 많으니 참고만 해 주세요.

TO-DO

아직 블로그에 넣지 않은 기능들은 다음과 같습니다.

• "맨 위로 가기" 버튼 넣기
• 댓글 기능 (utterances가 유력한 후보)
• 더 삐까뻔쩍한 블로그 헤더
• About 페이지에 내용 채워넣기
• 404 페이지

그래도 뭐, 게시글를 적으면서 천천히 작압해 나가면 되겠죠...?