[Python] 연산 속도 올리기 - 개요 및 알고리즘과 자료구조

🐍 본 게시글은 Python 3.11.0 환경에서 작성되었습니다!

 

파이썬은 인터프리터 언어로 알려져 있지만 사실은 하이브리드 언어로 볼 수 있다.

그 이유는 동작 방식을 보면 알 수 있다.

 

 

파이썬 코드가 동작하는 방식을 보면 프로그래머가 Python Source Code를 Python Interpreter에 전달하면 내부에서 다음과 같은 과정이 진행된다.

• Python Complier가 파이썬 소스 코드를 읽고 문법 검사 후 오류가 없으면 바이트 코드로 변환 한다.
• PVM(Python Virtual Machine)이 바이트 코드를 기계어로 한줄씩 번역한다.

 

이런 과정이 끝난 후 컴퓨터는 번역된 기계어를 실행한다.

 

Python Compiler가 변환한 바이트 코드를 프로젝트에서 볼 수 있는데 바로 __pycache__라는 폴더의 .pyc이 컴파일된 바이트 코드 이다.

 

 

파이썬은 이렇듯 소스코드를 기계어로 만드는 과정을 거치기 때문에 C,C++, 어셈플리어 같은 저급 프로그래밍 언어보다는 느릴 수 밖에 없다.

 

하지만 파이썬을 코딩을 하다보면 성능 향상이 필요할 때가 있다. 이때는 다음과 같은 방법들을 통해 성능 향상을 시도해 볼 수 있다.

• 알고리즘과 자료구조: 효율적인 알고리즘과 적절한 자료구조를 선택하여 성능을 개선할 수 있다. 예를 들어, 리스트 대신 세트를 사용하여 중복 제거할 때 성능이 향상된다.
• 내장 함수와 라이브러리 활용: Python의 내장 함수나 외부 라이브러리(예: NumPy, Pandas)를 활용하면 성능이 크게 향상될 수 있다.
• 코드 프로파일링: cProfile과 같은 도구를 사용하여 코드의 성능 병목 지점을 찾아 최적화할 수 있다.
• 병렬 처리: 멀티스레딩이나 멀티프로세싱을 통해 CPU의 여러 코어를 활용하여 성능을 개선할 수 있다.
• JIT 컴파일러 사용: PyPy와 같은 JIT(JIT Compilation) 컴파일러를 사용하면 실행 속도를 높일 수 있다.

 

알고리즘과 자료구조를 적절히 사용하여 성능 개선

적절한 알고리즘과 자료구조를 사용하면 Python 코드의 실행 속도를 높힐 수 있다.

대표적으로 리스트를 추가할 때, 반복문을 통해 append 하는 방법보다 리스트 컴프리헨션(List Comprehension) 방법으로 하면 더 빠르다.

import time
if __name__ == "__main__":
    start = time.time()
    a = []
    for i in range(100000000):
        a.append(i)
    end = time.time()
    print(f"Default : {end-start:.4f}sec")

    start = time.time()
    a = [i for i in range(100000000)]
    end = time.time()
    print(f"List Comprehension : {end-start:.4f}sec")

 

 

이렇게 속도차이가 나는 이유는 리스트 컴프리헨션이 내부적으로 최적화되어 있기 때문이다. 

이렇게 리스트를 생성해야 할 때는 리스트(튜플, 집합, 사전) 컴프리헨션을 사용하는 것을 권장한다.

 

추가로 연산을 반복할 때도 마찬가지 이다.

import time
if __name__ == "__main__":
    start = time.time()
    a = 0
    for i in range(1000000):
        a+=i
    print(a)
    end = time.time()
    print(f"Default : {end-start:.4f}sec")

    start = time.time()
    a = list(range(1000000))
    a = sum(a)
    print(a)
    end = time.time()
    print(f"SUM : {end-start:.4f}sec")

 

sum이 더 빠른 이유도 C로 최적화된 내부 구현이 되어 있기 때문이다.

 

특정 문제에 대해서는 알고리즘을 어떤 것을 선택하느냐에 따라 성능이 달라진다.

다음은 그래프에 대해 A -> N로 가는 최단 경로를 구하는 문제이다.

둘다 동일한 결과를 반환하지만 목표 노드가 깊은 곳에 위치하므로 DFS 좀 더 빠르다. (비교를 위해 인위적으로 동일한 대기시간 부여)

import time
from collections import deque

# BFS 구현
def bfs(graph, start, goal):
    visited = set()
    queue = deque([(start, [start])])  # (현재 노드, 경로)
    
    while queue:
        current_node, path = queue.popleft()
        time.sleep(0.1)
        if current_node == goal:
            return path
        
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # 경로를 찾지 못한 경우

# DFS 구현
def dfs(graph, start, goal, path=None):
    if path is None:
        path = []
    path.append(start)
    time.sleep(0.1)
    if start == goal:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in path:
            result = dfs(graph, neighbor, goal, path)
            if result is not None:
                return result
    
    path.pop()
    return None

if __name__ =="__main__":
    graph = {
        'A': ['B', 'C', 'D'],
        'B': ['A', 'E', 'F'],
        'C': ['A', 'G', 'H'],
        'D': ['A', 'I', 'J'],
        'E': ['B', 'K', 'L'],
        'F': ['B'],
        'G': ['C'],
        'H': ['C', 'M', 'N'],
        'I': ['D'],
        'J': ['D'],
        'K': ['E'],
        'L': ['E'],
        'M': ['H'],
        'N': ['H'],
    }

    # 더 많은 노드를 추가하여 그래프를 복잡하게 만듭니다.
    for i in range(15, 30):
        graph[chr(65 + i)] = [chr(65 + i - 1), chr(65 + i - 2)]  # A-Z까지 노드 추가

    # 경로 찾기와 시간 측정
    start_node = 'A'
    goal_node = 'N'

    # BFS 시간 측정
    start_time_bfs = time.time()
    bfs_path = bfs(graph, start_node, goal_node)
    end_time_bfs = time.time()
    bfs_time = end_time_bfs - start_time_bfs

    # DFS 시간 측정
    start_time_dfs = time.time()
    dfs_path = dfs(graph, start_node, goal_node)
    end_time_dfs = time.time()
    dfs_time = end_time_dfs - start_time_dfs

    # 결과 출력
    print("BFS로 찾은 A에서 N로 가는 경로:", bfs_path)
    print(f"BFS 실행 시간:{bfs_time:.7f}")

    print("DFS로 찾은 A에서 N로 가는 경로:", dfs_path)
    print(f"DFS 실행 시간:{dfs_time:.7f}")