파이썬으로 행렬 구현하기 (1)

코딩테스트의 유형은 회사, 지원직무, 경력에 따라 상이합니다. 일반적으로는 특정 사이트에 접속해서 (프로그래머스, 코드업 등) 주어진 문제를 2~3 시간 내에 풀고 제출하는 경우가 대부분이지만 지원하는 직무가 높은 경력을 요구하거나 일반 알고리즘 문제로 직무 적합성을 판단하기 애매한 경우에는 회사에서 직접 문제를 지원자에게 메일로 보내 푼 문제의 소스코드를 압축파일로 보내라는 경우도 많습니다.

이때의 코딩테스트 문제는 완전 운입니다... 지원하는 팀에서 개발하려고 하는 모듈이 될 수도 있고 (개인적으로 최악의 경우로 요구사항이 높습니다) 머신러닝의 경우 직접 알고리즘를 개발하여 주어진 성능을 달성해야 하는 경우도 있습니다. 이번 포스트에서는 그 중에서도 가장 간단한 numpy 등의 외부 라이브러리 없이 순수한 파이썬으로만 행렬을 구현하는 방법을 다뤄보겠습니다.

 

행렬 클래스 생성

먼저 파이썬에서 행렬을 어떻게 "표현"할 수 있을까요? 직관적으로 다음과 같은 중첩 리스트가 될겁니다.

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

그럼 클래스를 이용해 행렬 인스턴스를 생성한다고 할 때, 어떻게 생성할 수 있을까요? 위처럼 바로 중첩리스트를 입력으로 넣을 수도 있고, 행/열의 수를 기입할 수도 있습니다. 이때, 행렬 원소의 값을 어떤 값으로 할지도 입력으로 넣을 수도 있겠죠.

class Matrix(object):
    def __init__(self, rows, cols=1, fill=0.):
        '''Construct zero matrix from list of list
        Examples:
        A = Matrix([[1,2],[3,4]])
        A = Matrix([1,2,3,4])
        A = Matrix(10, 20)
        A = Matrix(10, 20, fill=0.)
        A = Matrix(10, 20, fill=lambda r, c: 1. if r==c else 0.)
        '''
        if isinstance(rows, list):  # in case of rows is list
            if isinstance(rows[0], list):  # in case of rows is list of list
                self.rows = [[e for e in row] for row in rows]
            else:
                self.rows = [[e] for e in rows]
        elif isinstance(rows, int) and isinstance(cols, int):  # in case of the number of rows and cols are defined
            xrows, xcols = range(rows), range(cols)
            if callable(fill):  # if 'fill' is callable object
                self.rows = [[fill(r,c) for c in xcols] for r in xrows]
            else:  # Fill with 'fill' value
                self.rows = [[fill for c in xcols] for r in xrows]
        else:
            raise RuntimeError(f"Unable to build matrix from {rows}")
        
        self.nrows = len(self.rows)
        self.ncols = len(self.rows[0])

• 생성자는 행렬의 행, 열의 개수뿐만 아니라 디폴트로 채울 "fill" 값도 받아들입니다. "fill" 아규먼트는 어떠한 값이 될 수도 있고, 함수가 될 수도 있으며 행렬 원소를 초기화합니다.
• 추후 행렬을 이중리스트로 표현하기 위해 self.rows 라는 인스턴스 변수에 값을 담습니다.

 

행렬 성분 표시

행렬 성분을 얻거나 아니면 특정 행, 열의 값을 지정하거나 등의 행렬 성분과 관련된 함수를 정의합니다.

    def __getitem__(self, coords):
        i, j = coords
        return self.rows[i][j]

    def __setitem__(self, coords, value):
        i, j = coords
        self.rows[i][j] = value

    def tolist(self):
        return self.rows

    def __str__(self):
        return str(self.rows)

• 어떤 행렬 A를 생성했을 때, numpy 에서 하듯 인덱싱을 통해 값을 읽으려면 행렬 클래스가 리스트, 튜플 등과 같은 내장 시퀀스로 동작해야 합니다. 이를 위해 __getitem__과 __setitem__을 정의하여 인덱싱이 가능하도록 합니다.

간단한 예를 통해 확인한 결과 잘 동작합니다.

A = Matrix(3, 4, fill=lambda r, c: 1. if r==c else 0.)
print(A)
>>> [[1.0, 0.0, 0.0, 0.0], [0.0, 1.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0]]

A[0,1] = 2
print(A)
>>> [[1.0, 2, 0.0, 0.0], [0.0, 1.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0]]

A[2,3]
>>> 0.0

 

추가적으로 flatten, reshape, row swap 등의 기능을 구현합니다.

    def flatten(self):
        return [self[r,c] for r in range(self.nrows) for c in range(self.ncols)]    

    def reshape(self, n, m):
        if n*m != self.nrows*self.ncols:
            raise RuntimeError('Impossible reshape')
        flat = self.flatten()
        return Matrix(n, m, fill=lambda r, c, m=m, flat=flat: flat[r*m+c])

    def swap_rows(self, i, j):
        self.rows[i], self.rows[j] = self.rows[j], self.rows[i]
        
 
A = Matrix(3, 4, fill=lambda r, c: 1. if r==c else 0.)
print(A.flatten())
>>> [1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0]

print(A.reshape(4,3))
>>> print(A.reshape(4,3))

A.swap_rows(2,1)
print(A)
>>> [[1.0, 0.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0], [0.0, 1.0, 0.0, 0.0]]

 

단위행렬과 대각행렬 만들기

크기가 주어지면 단위행렬, 대각 성분이 주어지면 대각행렬을 만드는 함수를 정의합니다. 이들 메소드는 기존 행렬에 영향을 주지 않기 때문에 (self 인자를 사용할 필요가 없죠) staticmethod로 구현하겠습니다. (참고로 staticmethod는 의미적으로 클래스의 namespace에는 속해야하나 일반 함수처럼 동작하는 함수를 구현할 때 사용합니다.)

    @staticmethod
    def identity(rows=1, e=1.):
        return Matrix(rows, rows, fill=lambda r, c, e=e: e if r==c else 0.)

    @staticmethod
    def diagonal(d):        
        return Matrix(len(d), len(d), fill=lambda r, c, d=d: d[r] if r==c else 0.)
        
 
A = Matrix.identity(3, 3)
print(A)
>>> [[3, 0.0, 0.0], [0.0, 3, 0.0], [0.0, 0.0, 3]]

A = Matrix.diagonal([3,1,3,4])
print(A)
>>> [[3, 0.0, 0.0, 0.0], [0.0, 1, 0.0, 0.0], [0.0, 0.0, 3, 0.0], [0.0, 0.0, 0.0, 4]]

• 대각행렬 입력 "d" 인자에는 정수가 아닌 튜플이나, 리스트가 와야 합니다. 예를 들어 5의 값을 가지는 1x1의 대각행렬을 만들기 위해서는 d=[5]를 입력으로 넣어주어야 합니다.

 

---

이제 행렬에 사용하는 산술 연산을 정의할 준비를 마쳤습니다. 다음 포스트에서는 이번 포스트에서 정의한 클래스를 이용해서 행렬의 덧셈, 뺄셈, 곱셈 등의 산술 연산을 구현해보도록 하겠습니다.

[알고리즘 & 코딩테스트/코딩테스트] - 파이썬으로 행렬 구현하기 (2)

[알고리즘 & 코딩테스트/코딩테스트] - 파이썬으로 행렬 구현하기 (3) - 가우스 조던 소거법을 이용한 역행렬

[알고리즘 & 코딩테스트/코딩테스트] - 파이썬으로 행렬 구현하기 (4) - 마무리