파이썬 배열(리스트), 행렬의 전치, zip

1. Python 배열의 메모리 할당

allocation

python의 리스트는 동적 배열로 메모리 할당은 다음과 같은 방식으로 이루어진다.
1. 생성 시 용량 0
2. 첫 append() 시 기본 크기 할당.

기본 크기란?
python의 리스트는 동적 배열이기 때문에 C++의 array처럼 요소 개수에 맞추어 용량을 생성, 할당하지 않음.
대신 추후 삽입을 대비하여 여유 공간을 두고 overallocation(과잉 할당)하는 방식 사용.

3. 삽입하다 용량 초과 시 약 1.125+a(CPython 기준) 크기의 새 배열 생성. 메모리 복사 및 원래 배열 삭제.

자세한 내용은 하단 참고~
동적 배열(Vector)의 메모리 할당

그래서 배열 메모리 사용량은 어떻게 되는데?

파이썬 리스트는 내부적으로는 값을 직접 할당하는 것이 아니라 해당 객체를 가리키는 포인터들을 사용하는 포인터 배열임.

항목	메모리 사용량
리스트 객체 자체	약 64 바이트
각 요소 포인터	약 8 바이트 (64비트 OS 기준)
정수 값 (int)	약 28바이트 (값에 따라 달라짐)

왜 int를 삽입해도 객체당 28바이트나 차지할까?
파이썬은 int도 객체로 관리하기 떄문. 정수값 뿐만 아니라 메타 데이터와 실제 값을 포함하는 객체임.

그렇다면 500 * 500 행렬인 이차원 배열은 메모리를 얼마나 사용할까?

외부 배열
1. 리스트 객체: 64B
2. 500개의 포인터 8B* 500 = 4,000B
➡️ ≈ 4KB

내부 배열
1. 각 행 리스트 객체: 64B
2. 각 행의 500개 정수 포인터: 8B 500 = 4,000B
3. 정수 객체 자체: 28B 500 = 14,000B
➡️ 각 행 별로 18,064B
➡️ 500행 이면? 500 * 18,064 = 9,032,000B ≈ 8.61MB

총 8.6~8.7MB

2. Python 행렬의 전치

이차원 배열의 행과 열을 서로 바꾸는 방법에 가장 많이 쓰는 것은 zip()메서드 일것이다.

zip()

iterable한 객체를 여러개 받아 동일한 인덱스 요소끼리 묶어서 튜플로 반환하는 내장 함수. 가장 짧은 iterable 기준으로 작동함. (각 iterable의 길이 다를 경우 가장 짧은 요소 index까지만 돌고 그 이상은 잘림)

a = [1, 2, 3]
b = ['a', 'b', 'c']
z = zip(a, b)
print(list(z))  # [(1, 'a'), (2, 'b'), (3, 'c')]

c = ['X', 'Y', 'Z']
print(list(zip(a, b, c)))  # [(1, 'a', 'X'), (2, 'b', 'Y'), (3, 'c', 'Z')]

zip의 시간 복잡도

zip(a, b, c)를 수행 시 내부 동작은 다음과 같다.

1. zip 객체(반복자) 생성

2. 각 iterable들을 순차적으로 하나씩 가져와 묶으며 튜플 생성

   1. a[0], b[0], c[0] 묶기
   2. a[1], b[1], c[1] 묶기
      ...(반복)

3. zip 객체(반복자) 반환
   ➡️zip은 Lazy Evaluation 방식으로 동작. 실제 데이터를 zip()하는 순간에 생성하지 않고 iterator를 반환했다가 for문 등을 통해 접근하는 순간 실제 데이터 생성.

   때문에 위의 zip 생성 예시 코드에서 list로 변환하지 않고 print할 경우 zip객체가 나온다.

a = [1, 2, 3]
b = ['a', 'b', 'c']
z = zip(a, b)

print(zip) a = [1, 2, 3]
b = ['a', 'b', 'c']
z = zip(a, b)

➡️ 따라서 가장 짧은 요소의 길이 N에 대해 O(N)의 시간 복잡도 가짐

python에서 행렬의 전치

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

transposed = list(map(list, zip(*matrix)))

참 쉽죠?
시간 복잡도는 행의 크기 r과 열의 크기 c에 대해 O(r * c) 가 된다.
몹시 효율적인 구조라 할 수 있다.

---

3. 행렬에 대해 행과 열에 대해 같은 작업을 해야하는 경우

1. 행에 대한 작업 수행
2. 전치
3. 새 배열의 행 작업 수행(열 작업)

으로 해결할 수 있다.

def compress(matrix):
    changed = True
    while changed:
        changed = False

        # 행 압축
        new_matrix = []
        prev_row = None
        for row in matrix:
            if row != prev_row:
                new_matrix.append(row)
                prev_row = row
            else:
                changed = True
        matrix = new_matrix

        # 열 압축
        matrix_T = list(zip(*matrix))  # 전치
        new_matrix_T = []
        prev_col = None
        for col in matrix_T:
            if col != prev_col:
                new_matrix_T.append(col)
                prev_col = col
            else:
                changed = True
        matrix = [list(row) for row in zip(*new_matrix_T)]  # 다시 전치

    return matrix