Python으로 직접 Stack 구현하고 튜닝하기

0단계 - 이 Stack은 어디서 시작된걸까?

예전에 하나, 이린, 감자와 면접의 신이라는 기술 면접 스터디를 할 때, 하나가 "Java로 Stack의 주요 기능을 간단하게 직접 구현해주세요"라는 질문을 가져온 적이 있었다.

질문을 듣자마자 당황스러움이 먼저 밀려왔다. 면접 중에 라이브 코딩을 하는 경우도 많고, 자료구조를 직접 구현하는 문제가 자주 나온다는 건 알고 있었지만, 정작 나는 한 번도 스택을 직접 구현해 본 적이 없었다.

그렇지만 마음 한켠에서 "재미있겠는걸?"이라는 생각이 들어, 내가 해보겠다고 손을 들었고, 20분 정도의 시간 안에 스택같아 보이는 얼렁뚱땅 무엇인가를 만들었고 결과적으로는 잘 돌아가지는 않았지만, 꽤나 재미있던 경험이었다. (그 이후로도 가끔씩 하나는 나에게 중요한 포인트에서 기술 질문들을 던져주곤 했었는데 많이 배울수 있는 기회가 되었었다.)

그리고 며칠 전, 백준에서 그때의 기억을 떠올리게 하는 문제를 발견했다.

이번에는 파이썬으로 꼭 성공하겠다 생각하고 문제를 풀기 시작했다.

백준 10828번 - 스택

1단계 - 기본 기능 구현

문제에서 요구하는 것은 Stack의 기본 기능(push, pop, size, empty, top)을 구현하는 것이다. 파이썬에서는 List가 기본적으로 Stack의 대부분 기능을 지원하기 때문에, 사실상 이 문제는 아주 간단하게 해결할 수 있다.

하지만 나는 일부러 파이썬의 내장 리스트 메서드들을 사용하지 않고, 스택을 직접 만들어보는 연습을 해보고 싶었다.

처음에는 List라는 자료구조 자체를 구현해보려고 했다. 하지만 선형 자료구조를 만들기 위해 포인터를 사용해야 하고, 메모리를 직접 다뤄야 하는 구조는 파이썬에서 쉽게 구현하기 어려웠다. Node 클래스도 만들어야 하고, 전체적으로 너무 복잡해졌다.

그래서 타협점으로, 기본 리스트를 내부 배열로 사용하되, append()나 pop()과 같은 기본 메서드는 사용하지 않고 직접 구현해보기로 했다.

class RoyStack():
    def __init__(self):
        self.space = []

    def push(self, value):
        self.space.append(value)
        return

    def pop(self):
        if not self.space:
            print(-1)
            return
        print(self.space[-1])
        self.space = self.space[:-1]
        return

    def size(self):
        print(len(self.space))
        return

    def empty(self):
        if not self.space:
            print(1)
            return
        print(0)
        return

    def top(self):
        if not self.space:
            print(-1)
            return
        print(self.space[-1])
        return


import sys

input = sys.stdin.readline
n = int(input())
roy_stack = RoyStack()

for _ in range(n):
    user_input = list(input().split())
    command = user_input[0]

    if command == 'push':
        roy_stack.push(user_input[1])
    elif command == 'pop':
        roy_stack.pop()
    elif command == 'size':
        roy_stack.size()
    elif command == 'empty':
        roy_stack.empty()
    else:
        roy_stack.top()

정답은 통과되긴 했지만 마음에 들지 않는 부분이 몇 가지 있었다.

가장 먼저 거슬렸던 건 입력을 split했을 때 두 번째 값이 있을지 없을지 확신할 수 없어서 if-else로 분기 처리를 해야 했다는 점이다. 매 줄마다 조건문이 점철된 구조는 확장성도 떨어지고 보기에도 좋지 않았다.

또 하나는 print()를 stack 메서드 내부에서 직접 호출하고 있다는 점이다. pop()이나 top()은 값을 반환만 하고 출력은 호출하는 쪽에서 담당하는 게 더 자연스럽다고 느꼈다. 나는 또 한번 역할과 책임을 명확히 분리하지 못한 구조를 만들었구나 한탄했다...

1.5단계 - 좀 더 클린하게

그래서 이걸 어떻게 개선할 수 있을까 고민하다가, Python에서 지원하는 가변 인자 unpacking(*args)를 활용하면 입력 처리도 훨씬 깔끔하게 할 수 있다는 걸 알게 되었다. 동시에 조건문 대신 dictionary의 value에 함수를 직접 넣는 방식으로 command mapping을 구성하면, 코드 자체도 함수형 스타일에 더 가까워질 수 있었다.

이 과정에서 literal 값으로 쓰이던 magic number들도 함께 정리했고, 전체적으로 읽기 쉬운 구조로 다듬을 수 있었다. 호출하는 쪽에서는 print만 담당하고, 스택 내부는 오직 연산과 상태 관리만 책임지도록 책임을 명확히 나눴다.

class RoyStack():
    def __init__(self):
        self.space = []

    def push(self, value):
        self.space.append(value)
        return

    def pop(self):
        if not self.space:
            return -1
        pop_value = self.space[-1]
        self.space = self.space[:-1]
        return pop_value

    def size(self):
        return len(self.space)

    def empty(self):
        if not self.space:
            return 1
        return 0

    def top(self):
        if not self.space:
            return -1
        return self.space[-1]


import sys

FIRST_VALUE = 0
input = sys.stdin.readline
n = int(input())
roy_stack = RoyStack()

commands = {
    'push': lambda v: roy_stack.push(v[FIRST_VALUE]),
    'pop': lambda _: print(roy_stack.pop()),
    'size': lambda _: print(roy_stack.size()),
    'empty': lambda _: print(roy_stack.empty()),
    'top': lambda _: print(roy_stack.top())
}

for _ in range(n):
    command, *number = input().split()
    if command in commands:
        commands[command](number)

각 기능은 역할과 책임이 좀 더 잘 분리되어 있고, 함수 안에서 side effect 없이 값을 반환만 하기 때문에 테스트하기도 수월하다. 커맨드 매핑도 새로운 명령을 추가하거나 수정할 때 코드 중간을 건드릴 필요 없이 dictionary에 추가만 해주면 된다.

하지만 여기까지 구현하고 나서도 한 가지 성능 문제가 계속 마음에 걸렸다. 바로 pop()이 내부적으로 슬라이싱을 이용해서 리스트를 복사하기 때문에 매번 O(n)의 연산이 발생한다는 점이다. 실제로 Python의 pop() 메서드는 O(1)이 보장되는데, 이 구조는 그에 비해 너무 느렸다.

2단계 - 내부 인덱스 추가

한참을 고민하다 내부 인덱스를 두어 마치 Java에서 배열을 사용할때처럼, 리스트의 크기를 고정해두고 배열의 끝을 가리키는 index 포인터를 따로 두는 구조는 어떨까 생각이 들어 바꿔보았다.

class RoyStack():
    def __init__(self, capacity=1000):
        self.space = [None] * capacity
        self.index = 0

    def push(self, value):
        self.space[self.index] = value
        self.index += 1
        return

    def pop(self):
        if self.index == 0:
            return -1
        self.index -= 1
        return self.space[self.index]

이 구조는 메모리를 미리 할당한 다음 index 포인터를 이동시키는 방식으로 작동한다. push()는 해당 위치에 값을 넣고 index를 증가시키고, pop()은 index를 줄이기만 하면 되기 때문에 두 연산 모두 O(1) 시간으로 동작한다.

그런데, 이 구조로도 완전히 해결되지 않은 문제가 하나 있었다.
바로 초기에 설정한 용량보다 많은 값이 들어오는 경우다.

리스트의 크기보다 인덱스가 커지게 되면 당연히 IndexError가 발생한다. 그렇다면 기본 파이썬 리스트는 이런 상황에서 어떻게 동작할까? 내부적으로 일정 크기를 초과하면 리스트를 복사하고, 그 크기를 두 배로 늘려가며 동적으로 크기를 조절한다.

이와 동일한 방식으로 직접 동적 확장을 구현해보기로 했다.

3단계 - 동적 확장

class RoyStack():
    def __init__(self, capacity=1000):
        self.space = [None] * capacity
        self.index = 0
        self.capacity = capacity

    def resize(self):
        new_capacity = max(1, self.index * 2)
        new_space = [None] * new_capacity
        for v in range(self.index):
            new_space[v] = self.space[v]
        self.space = new_space
        self.capacity = len(new_space)
        return

    def push(self, value):
        if self.index >= self.capacity:
            self.resize()
        self.space[self.index] = value
        self.index += 1
        return

push()가 호출될 때 현재 인덱스가 용량을 초과하면, resize()를 통해 리스트 용량을 두 배로 확장한다.
만약 최초 크기가 0으로 설정되더라도 문제없이 작동하도록, 최소 용량은 1로 설정했다.

리스트를 복사하는 과정은 O(n)이 걸리지만, 자주 일어나는 연산이 아니기 때문에 실제로는 amortized O(1)의 시간으로 동작할 것이다.

4단계 - 동적 축소

여기까지 구현하고 나면 자연스럽게 다음과 같은 의문이 생긴다.
"크기는 늘리는데, 왜 줄이지는 않을까?"

실제로 지금 구조는 resize()만 존재할 뿐, 리스트 크기를 줄이는 기능은 없다.

이 상태에서는 한 번 커진 리스트가 계속 메모리를 점유하게 되고,
특정 상황에서는 실제로 필요하지도 않은 대용량 메모리를 낭비하게 된다.

처음에는 단순히 인덱스가 용량의 절반 이하로 떨어지면 리스트를 줄이면 되겠다고 생각했지만,
그럴 경우 경계 조건에서 resize()와 shrink()가 반복되며 불필요한 메모리 재할당이 반복될 수 있다는 문제가 있다.
예를 들어 크기가 1000에서 2000으로 증가했다가, 다시 1000으로 줄고, 다시 2000으로 늘어나는 식의 비효율적인 반복이 발생할 수 있다.

이를 해결하기 위해, 확장과 축소의 기준을 다르게 설정하기로 했다.

resize는 현재 인덱스의 2배
shrink는 전체 용량의 1/4 이하로 내려갔을 경우에만

이 방식은 인프라에서 scale-out은 즉시 확장하고, scale-in은 웜업 타임을 두고 일정 기준을 충족한 이후에 줄이는 방식과 유사하다는 생각이 들었다.

class RoyStack():
    def __init__(self, capacity=1000):
        self.space = [None] * capacity
        self.index = 0
        self.capacity = capacity

    def resize(self):
        new_capacity = max(1, self.index * 2)
        new_space = [None] * new_capacity
        for v in range(self.index):
            new_space[v] = self.space[v]
        self.space = new_space
        self.capacity = len(new_space)
        return

    def shrink(self):
        new_capacity = max(1, self.index)
        if new_capacity >= self.capacity:
            return
        new_space = [None] * new_capacity
        for v in range(self.index):
            new_space[v] = self.space[v]
        self.space = new_space
        self.capacity = len(new_space)
        return

    def push(self, value):
        if self.index >= self.capacity:
            self.resize()
        self.space[self.index] = value
        self.index += 1
        return

    def pop(self):
        if self.index == 0:
            return -1
        self.index -= 1
        pop_value = self.space[self.index]
        if self.index < self.capacity // 4 and self.capacity > 1:
            self.shrink()
        return pop_value

이렇게 구현하면 현재 인덱스가 전체 용량의 1/4보다 작고, 용량이 1보다 클 경우에만 shrink()를 호출한다.
그 내부에서는 현재 인덱스 크기만큼만 다시 리스트를 생성하고 교체한다.
이를 통해 실제로 필요한 만큼만 메모리를 사용하는 구조를 만들 수 있었다.

5 - 생각보다는 조용한 결말

실제로 resize()와 shrink()를 추가해도 성능 향상은 거의 없었다.
테스트로 10만 건 정도의 데이터를 넣고 빼는 작업을 반복해도 별다른 차이가 나지 않았다.

만약 테스트 데이터 크기를 1000만건, 연속적인 push와 pop을 10만건 이상 만들어서 넣으면 속도 차이가 날수도 있을것 같다.

생각보다 오랜 시간이 걸렸지만, 미뤄왔던 숙제를 끝마친것과 같은 후련함이 있었고 무엇보다 시간 가는 줄 모를 정도로 재미있게 만들 수 있었다.

지금까지 Python으로 알고리즘 문제는 많이 풀어왔지만, 정작 Python의 철학이나 고급 기능들에 대해서는 깊이 고민해본 적이 없었다. 이번 기회에 그런 부분까지 한 번쯤 짚어볼 수 있어서 스스로에게도 꽤 의미 있는 시간이 됐다.

C 계열 언어는 뭐든지 직접 만들 수 있는 언어고, Java는 어느 정도 안전성과 성능의 균형점을 제공한다면,
Python은 굉장히 자유롭고 편리한 언어지만, 반대로 저수준 구현으로 내려가면 오히려 제약이 많은 언어라는 점을 느끼게 되었다.

~~그런데... C보다는 Go가 더 궁금하다..~~

앞으로도 가끔씩 이렇게 기본 자료구조를 직접 구현해보는 시간을 가져보려고 한다!

저작자표시 비영리 변경금지 (새창열림)

'Language' 카테고리의 다른 글

상속과 합성에 대한 이해 (3)	2023.11.30
Java의 final은 불변성을 보장해주지 않는다. (2)	2023.10.26

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Python으로 직접 Stack 구현하고 튜닝하기

0단계 - 이 Stack은 어디서 시작된걸까?

1단계 - 기본 기능 구현

1.5단계 - 좀 더 클린하게

2단계 - 내부 인덱스 추가

3단계 - 동적 확장

4단계 - 동적 축소

5 - 생각보다는 조용한 결말

'Language' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역