Numpy를 활용해 이중 루프 없애기!

프로그래밍을 하다보면 이중 포문이 종종 등장한다. O(N^2)의 시간복잡도를 보통 가지기 때문에 이중 포문을 사용하기 보다는 벡터 연산을 활용해 계산하는 것이 훨씬 효율적이다.

이중 포문을 해결하기 위해서는 당연한 소리 같지만 먼저 Inner Loop를 없애고 그 다음에 Outer Loop를 없애주면 된다. 예를 들어 Hilbert Matrix를 만드는 예시를 생각하보자.

1. 이중 포문을 활용한 Hilbert Matrix 생성 예시

    A = [[0]*n for i in range(n)]
    z = [1+i for i in range(n)]
    for i in range(n):
        for j in range(n):
            A[i][j]=1/(i+j+1)

2. 우선 Inner Loop를 없앤다

    n = 10
    A = np.zeros((n,n))
    z = np.array([1+i for i in range(n)])

    for i in range(n):
        b = i+z
        A[i,:]=1/b

3. Vector 연산으로 Outer Loop 없애기

    A = 1/(np.repeat(z,n).reshape(n,n)+z)
    print(A)

np.repeat과 reshape으로 matrix A의 shape 맞게 행렬을 만드는 것이 포인트이다.
특히 np.repeat은 벡터 연산을 하는데 종종 사용되므로 알아두면 유용할 것이다!