PyPy3 와 Python3

-

개요

최근 백준 2580번 스도쿠 문제를 풀어보다 느낌점을 정리해 두고자 합니다.

스도쿠 문제풀이 게시물 

이 문제는 이미 C++로 풀었는데 정답판정을 받았습니다. 

하지만 학원에 파이썬을 공부하는 학생도 많으므로 Python3로 풀어보다 난관에 봉착했습니다. 😧

[백준 스도쿠 정답제출 결과]

한 2시간 정도 Python3으로 시도했지만 모두 시간초과!!! 😰 

(나름 열심히 짰는데 많이 당황...)

그런데 동일한 코드로 PyPy3로 제출하니 정답~ 😕 

아래는 제출한 코드입니다.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import sys
 
SIZE = 9
 
def isOk(arr, r, c, n):   
    # for i in range(SIZE):   
    #     if arr[i][c]==n or arr[r][i]==n:
    if n in rows[r] or n in cols[c]:
            return False
     
    # x = (c//3)*3
    # y = (r//3)*3
    # for i in range(3):   
    #     for j in range(3):       
    #         if arr[i+y][j+x]==n:
    #             return False
     
    if n in box[r//3][c//3]:
        return False
 
    return True
 
def sudoku(arr):   
    for i in range(SIZE):  
        for j in range(SIZE):
            if arr[i][j]==0:           
                for k in range(1, SIZE+1):               
                    if isOk(arr, i, j, k):                   
                        arr[i][j] = k
                        rows[i].add(k)
                        cols[j].add(k)
                        box[i//3][j//3].add(k)
 
                        if sudoku(arr)==True:
                            return True
 
                        arr[i][j] = 0
                        rows[i].remove(k)
                        cols[j].remove(k)
                        box[i//3][j//3].remove(k)
 
                return False       
    return True
 
lst = []
# 행열 값을 메모제이션
rows = [set() for _ in range(SIZE)]
cols = [set() for _ in range(SIZE)]
box = [[set() for _ in range(SIZE//3)] for _ in range(SIZE//3)]
 
for i in range(SIZE):
    #arr = list( map(int, input().split(' ')) )
    arr = list( map(int, sys.stdin.readline().rstrip().split(' ')) )
    lst.append(arr)
    for j in range(SIZE):
        if arr[j] != 0:
            rows[i].add(arr[j])
            cols[j].add(arr[j])
 
            box[i//3][j//3].add(arr[j])
 
#print(lst)
 
if sudoku(lst):           
    for i in range(SIZE):       
        for j in range(SIZE):
            #print(lst[i][j], end=' ')
            sys.stdout.write(f'{lst[i][j]} ')
        sys.stdout.write('\n')
        

완전히 같은 코드인데 Python3는 시간초과, PyPy3는 정답이라니...

이 둘이 정확히 무슨관계인지가 궁금해졌습니다.

사실 C++로는 최적화도 하지 않고 풀었는데...

Python3는 행,열,3x3 메모제이션까지 시도했음에도 풀리지 않았습니다.

 

CPython(= Python3)

우리가 흔히 'Python' 또는 'Python3'라고 부르는 것은 사실 CPython이라는 구현체.

CPython은 C로 작성되었으며, 파이썬 코드를 한 줄씩 해석(interpret)하여 실행.

마치 사람이 외국어를 한 줄씩 번역하는 것과 유사.

코드를 실행할 때마다 매번 해석하기 때문에, 실행 속도가 컴파일 방식에 비해 느릴 수 있다.

즉 인터프리터 방식, 준비과정없이 바로 실행되며 코드가 해석되는 구조.

 

PyPy3

PyPy3는 또 다른 파이썬 구현체로, 핵심은 JIT (Just-In-Time) 컴파일러를 사용.

JIT 컴파일러는 프로그램 실행 중에 자주 사용되는 코드 조각(핫스팟)을 찾아 기계어로 미리 번역(컴파일).

이렇게 컴파일된 부분은 다음에 실행될 때 번역 과정 없이 바로 실행되기 때문에 속도가 매우 빨라짐.

마치 자주 쓰는 문장을 미리 번역해두고 필요할 때 꺼내 쓰는 것과 유사.

즉 컴파일 방식, 준비과정을 갖고 코드를 해석하기 구조, 즉 즉시실행 X.

 

속도차이 언제, 왜? 

결국 PyPy는 Python의 느린 실행 속도를 보완하고자 개발된 CPython의 또 다른 구현체입니다.

다만 모든 상황에서 JIT 컴파일러를 사용하는 PyPy가 빠른 것은 아닙니다.

자세한 설명과 탄생 배경은 PyPy 나무위키 를 참조하기 바랍니다.


PyPy3가 더 빠른 경우:

반복문이나 루프가 많은 코드 즉, 수학 계산, 데이터 처리, 시뮬레이션 등 연산 집약적인 작업에서 반복문이나 루프가 많이 사용되는 경우, PyPy3의 JIT 컴파일러가 진가를 발휘. 

왜냐하면 PyPy3는 프로그램 실행 중에 자주 사용되는 코드 부분을 실시간으로 기계어로 번역하고 최적화 (동적 번역).

이 과정에서 PyPy3는 코드의 실행 패턴을 분석하고, 반복되는 부분을 집중적으로 최적화하여 실행 속도를 높임.

 

Python3가 더 빠르거나 비슷한 경우:

코드의 길이 or 실행시간이 매우 짧다면, JIT 컴파일 최적화 효과를 보기 전에 프로그램이 종료되어 오히려 Python3보다 느릴 수 있음. (PyPy3의 시작 시간 오버헤드 때문)

또한, NumPy, SciPy, pandas와 같이 C로 작성된 확장 모듈을 많이 사용하는 경우, Python3(=CPython)은 C로 작성된 부분을 직접 실행하기 때문에 보다 빠른 성능.

PyPy3도 C 확장 모듈을 지원하지만, Python3만큼 최적화되어 있지 않을 수 있고 특히 오래된 C 확장 모듈의 경우 PyPy3와의 호환성 문제가 발생할 가능성 존재.

메모리 사용량이 중요한 경우에도 PyPy3는 JIT 컴파일 과정에서 추가적인 메모리를 사용할 수 있으므로 메모리 제한이 있는 환경에서는 Python3이 더 유리할 수 있음.

 

정리 (Chat GPT 4o)

Python3, PyPy3 차이점

결론

스도쿠 문제는 비워진 칸(0)의 개수가 많을 수록 복잡도가 상승, 재귀호출이 스택에 많이 쌓이게 됩니다.

현재 빈칸에 어떤 값을 넣어보고 다음 빈칸에는 다른 값을 넣어보다 맞지 않으면 다시 처음으로 돌아가는 백트래킹 알고리즘으로 구현되어 있기 때문입니다.

따라서 모든 9x9 행, 열, 그리고 들어갈 수 있는 경우의 수(1~9)를 탐색하는 3중 반복문의 형태로 구현되어 있으며, 이런 패턴은 자주 사용하는 코드를 기계어로 번역하고 최적화하는 PyPy3에 유리한 구조입니다.

 

참고자료

  • Google Gemini 2.0 Flash Thinking Experimental

 

마지막으로 Python3로 스도쿠 문제를 맞춘 Code Guru가 계시면 알려주시면 감사~😉

감사합니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

Qt Designer 설치하기

-
이미지
개요 오늘은 Qt Designer 설치방법에 대해 설명하고자 합니다. Qt Designer는 Qt앱 생성시 GUI ( G raphic U ser I nterface) 를 쉽게 구성하고 배치하는 것을 도와주는 도구 입니다. [Qt Designer 실행화면] C++언어로 Qt를 사용하는 경우는 Qt Creator 설치시 같이 설치되어 바로 사용이 가능하지만 파이썬의 경우 별도 패키지를 설치 후 사용가능합니다. 그럼 파이썬에서 Qt Designer를 설치하는 방법을 살펴보겠습니다.
Read more »

PyQt5 기반 동영상 플레이어앱 만들기

-
이미지
비디오 재생 예전 게시물 중 음악파일 플레이어 를 파이썬으로 만든 예제가 있습니다. Qt 의 QMediaPlayer , QMediaPlaylist class를 이용해 mp3 등 음악 파일을 재생하는 원리입니다. 아래와 같이 사용합니다. from PyQt5.QtWidgets import QApplication from PyQt5.QtMultimedia import QMediaPlaylist, QMediaPlayer, QMediaContent from PyQt5.QtCore import QUrl import sys if __name__ == '__main__': app = QApplication(sys.argv) playlist = QMediaPlaylist() url = QUrl.fromLocalFile('test.mp3') playlist.addMedia(QMediaContent(url)) player = QMediaPlayer() player.setPlaylist(playlist) player.play() sys.exit(app.exec_()) PlayList를 생성해 파일을 추가하고, Player의 play() 함수를 수행하면 음악이 재생됩니다. 이번에는 동영상 플레이어 (Video Player) 를 Python + PyQt5 를 이용해 만들어 보았습니다. 기본 원리는 위와 같지만 비디오을 출력할 위젯 (QVideoWidget)만 설정 하면 동영상이 재생되는 원리입니다. [동영상 재생 프로그램] 주요기능 재생 리스트에 동영상 파일 추가, 삭제 (*.avi. *.mp4, *.mkv, *.mp...
Read more »