[Python] list의 append 메서드와 메모리

백준 10989번 문제를 풀다가 메모리 초과 오류와 마주했다.

 

 

 

# 기존 코드

import sys
input = sys.stdin.readline

n = int(input())
l = []

for _ in range(n):
    new = int(input())
    l.append(new)
    
l = sorted(l)

for i in l:
    print(i)

 

 

append 메서드가 동작하는 방식이 메모리 초과 오류와 관련이 있다고 해서 살펴봤는데, "메모리 재할당", "공간 확장 및 이사"와 같은 내용들을 확인할 수 있었다:

 

 

- append라는 함수 자체가 기존에 할당된 공간을 확장해야 하기 때문에, 만약에 연속된 메모리의 자리가 없을 경우 새롭게 큰 공간을 만들어 모든 값들을 이사시켜야 하는 단점이 있습니다. 여기서 바로 꽤나 큰 overhead가 발생하게 되서 상대적으로 느립니다.

 

- 반복문 안에 append를 썼기 때문에 메모리 재할당이 일어나 속도 저하와 비효율적인 메모리 사용이 발생

 

 

 

 

또한, 

N 입력값이 최대인 10,000,000 으로 들어왔다고 가정했을 때, 
int 배열로 만들면 4 * 10,000,000 = 40.000.000 byte = 약 38MB을 차지하여 메모리 제한(8MB)를 단숨에 초과한다고 한다.

 

 

 

---

 

 

그래서 계수 정렬이라는 방법을 사용해서 코드를 수정했더니 오류가 해결되었다.

 

계수 정렬(Counting Sort):

- 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
- 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정

- 데이터가 등장한 횟수를 셈

 

# 수정 코드

import sys
input = sys.stdin.readline

l = [0]*10001

n = int(input())

for _ in range(n):
    new = int(input())
    l[new] += 1
    
for i in range(len(l)):
    for _ in range(l[i]):
        print(i)

 

 

 

 

[참고]

1. https://smlee729.github.io/python/data%20structure/2015/03/02/1-list-allocation.html

2. https://leunco.tistory.com/67

3. https://kill-xxx.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0-3-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC-%EC%98%A4%EB%A5%98-%ED%95%B4%EA%B2%B0