파이썬으로 행렬 구현하기 (4) - 마무리

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

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

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

---

지난 포스트들에서 numpy 라이브러리 없이 순수히 파이썬 문법으로만 행렬을 구현해보았습니다. 먼저, 행과 열이 주어지거나 이중 리스트가 들어왔을 때 행렬을 표현할 수 있도록 클래스를 정의했고 이후에 덧셉, 곱셈, 뺄셈, 역행렬 등의 다양한 행렬 연산을 추가하였습니다. 

보통 이런 류의 문제를 내는 코딩테스트에서는 여기서 끝나지 않습니다. 구현한 행렬 클래스를 기반으로 행렬을 이용한 다양한 알고리즘 문제를 서브 문제로 출제하는 경우가 보통입니다. 따라서 기간은 보통 짧으면 3일에서 1주일 정도 주게 되죠. 특히 머신러닝과 관련하여 취업하려는 분들이라면 행렬로부터 시작하는 선형 대수학이 머신러닝의 기본임을 누구보다도 잘 아실 거라고 생각합니다. 또한 이번 시리즈에서 다룬 2차원 행렬은 추후 딥러닝 프레임워크의 기본 단위인 텐서의 기본형이기도 합니다. 

세상에 존재하는 수많은 수학적 개념과 알고리즘의 대부분은 이제 더 이상 "직접" 구현할 필요는 없습니다. 파이썬의 다양한 라이브러리가 많은 사람들의 협업으로 완성되었고 심지어 연산 상의 최적화도 훌륭하게 지원하는 상황입니다. 하지만 단순히 가져다 쓰는 것보다 어떻게 동작하는 지에 대한 원리를 아는 것은 추후 연구, 개발에 필수적이겠죠? 행렬은 비록 단순하나 다른 개념 및 알고리즘의 밑바탕이 되는 존재이고 많은 코딩테스트에서 심심치 않게 등장하기에 다뤄보았습니다. 마지막으로 지난 포스트들에서 구현한 행렬 클래스 전체를 다시 한번 살펴보면서 마무리하도록 하겠습니다.

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 = [[float(e) for e in row] for row in rows]
            else:
                self.rows = [[float(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 = [[float(fill(r,c)) for c in xcols] for r in xrows]
            else:  # Fill with 'fill' value
                self.rows = [[float(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])

    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)

    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]

    @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.)

    def __add__(self, A):
        '''
        Add matrix by elements, both matrices must have the same size
        Examples:
        >>> A = Matrix([[4,3,0],[2,1,0]])
        >>> B = Matrix([[1,2,0],[3,4,0]])
        >>> C = A+B
        '''

        if not isinstance(A, Matrix):  # A가 행렬이 아닐 경우 (int)
            if self.nrows == self.ncols:  
                A = Matrix.identity(self.nrows, A)
            elif self.nrows == 1 or self.ncols == 1:
                A = Matrix([[A for c in range(self.ncols)] for r in range(self.nrows)])
            else:
                raise RuntimeError('inavailable add')

        if A.nrows != self.nrows or A.ncols != self.ncols:  # Does not match shape
            raise ArithmeticError('incompatible dimensions')

        C = Matrix(self.nrows, self.ncols)
        for r in range(self.nrows):
            for c in range(self.ncols):
                C[r,c] = A[r,c] + self[r,c]
        return C

    def __sub__(self, A):
        '''
        Add matrix by elements, both matrices must have the same size
        Examples:
        >>> A = Matrix([[4,3,0],[2,1,0]])
        >>> B = Matrix([[1,2,0],[3,4,0]])
        >>> C = A-B
        '''

        if not isinstance(A, Matrix):  # A가 행렬이 아닐 경우 (int)
            if self.nrows == self.ncols:  
                A = Matrix.identity(self.nrows, A)
            elif self.nrows == 1 or self.ncols == 1:
                A = Matrix([[A for c in range(self.ncols)] for r in range(self.nrows)])
            else:
                raise RuntimeError('inavailable add')

        if A.nrows != self.nrows or A.ncols != self.ncols:  # Does not match shape
            raise ArithmeticError('incompatible dimensions')

        C = Matrix(self.nrows, self.ncols)
        for r in range(self.nrows):
            for c in range(self.ncols):
                C[r,c] = self[r,c] - A[r,c]
        return C

    def __radd__(self, A):
        return self + A
    
    def __rsub__(self, A):
        return self - A
        
    def __neg__(self):
        return Matrix(self.nrows, self.ncols, fill=lambda r, c: -self[r, c])

    def __rmul__(self, x):
        import copy
        M = copy.deepcopy(self)
        for r in range(M.nrows):
            for c in range(M.ncols):
                M[r,c] *= x
        return M

    def __mul__(self, A):
        if isinstance(A, (list, tuple)):
            return (self*Matrix(len(A), 1, fill=lambda r, c: A[r]))
        elif not isinstance(A, Matrix):  # in case of integer A
            return A*self  # __rmul__
        elif self.ncols == 1 and A.ncols == 1 and self.nrows == A.nrows:  # vector inner product
            return sum(self[r,0]*A[r,0] for r in range(self.nrows))
        elif self.ncols != A.nrows:
            raise ArithmeticError('incompatible dimension')

        M = Matrix(self.nrows, A.ncols)
        for r in range(self.nrows):
            for c in range(A.ncols):
                for k in range(self.ncols):
                    M[r,c] += self[r,k]*A[k,c]

        return M

    def __rtruediv__(self, x):
        '''Computes x/A'''

        import copy
        if self.ncols != self.nrows:
            raise ArithmeticError('matrix not squred')

        A = copy.deepcopy(self)
        B = Matrix.identity(self.ncols, x)
        for c in range(A.ncols):
            ## 1
            #for r in range(c+1, A.ncols):
            #    if abs(A[r,c]) > abs(A[c,c]):
            #        A.swap_rows(r,c)
            #        B.swap_rows(r,c)
            p = 0. + A[c,c]  # trick to make sure it is float
            ## 2
            for k in range(A.ncols):
                A[c,k] = A[c,k] / p
                B[c,k] = B[c,k] / p
            ## 3
            for r in list(range(0, c)) + list(range(c+1, A.ncols)):  # except 'c' column
                p = 0. + A[r,c]
                for k in range(A.ncols):
                    A[r,k] -= A[c,k]*p
                    B[r,k] -= B[c,k]*p

        return B

    def __truediv__(self, A):
        if isinstance(A, Matrix):
            return self*(1./A)  # matrix / matrix
        else:
            return (1./A)*self  # matrix / scalar     

    @property
    def T(self):                    
        return Matrix(self.ncols, self.nrows, fill=lambda r, c: self[c,r])