Sparse Matrix Multiplication

Sparse Matrix Multiplication

문제 내용

Matrix Dot(곱)을 연산 하시오

 

접근 방법

기본적인 수학 문제이다.

그런데 의외로 이런 문제를 코드로 변환 시키려고 보면 머리가 멈춘다.

아... 진짜 그냥 바보같다.

아무튼 다음과 같은 접근 방식으로 풀었다.

1. A 배열을 arows * acols, B배열을 brows * bcols 라고 명명할 수 있다.
2. acols와 brows의 크기가 같아야 곱셈이 가능하다
3. 결과 배열은 arows * bcols가 된다.

위의 3가지를 이용해서 문제를 접근했는데,

기본적인 loop를 어떻게 돌것이냐? 가 가장 중요한 첫번째 step이다.

A배열을 loop 시킬까? 아니면 B배열을 loop 시킬까?

결론은 Result 배열인 arow * bcols를 loop 시켜야 한다.

결국 result[arow][bcols] 에 각 A의 Col과 B의 Row가 곱해서 Sum이 되기 때문이다.

그래서

for arows inc

   for bcols inc

       result[arows][bcols] = A[arow][??] * B[??][bcols]

를 기본 코드로 두었다. 

위의 ?? 부분은 aclos와 brows의 길이가 같기때문에 해당 길이만큼 순환 시켜주면 목표한 result[arows][bcols]에 곱셈이 되어서 더해질 수 있다.

만들어진 코드는 아래와 같다.

var multiply = function(mat1, mat2) {
    let result = new Array(mat1.length).fill(0).map(_=> new Array(mat2[0].length).fill(0));
    
    for(let arow = 0; arow < mat1.length; arow++){
        for(let bcol = 0; bcol < mat2[0].length; bcol++){
            for(let brow = 0; brow < mat2.length; brow++){
                result[arow][bcol] += mat1[arow][brow] * mat2[brow][bcol];
            }
        }
    }
    
    
    return result;
};

혹시 위 코드가 최적화 코드가 아닌가 해서 다른 사람코드를 찾아봤는데, 이게 최적화 코드 맞았다.

위의 Matrix연산은 Concurrent 개발을 통해서 

            for(let brow = 0; brow < mat2.length; brow++){
                result[arow][bcol] += mat1[arow][brow] * mat2[brow][bcol];
            }

이 부분을 동시 계산 가능하도록 만들 수 있다.

2021.05.31 - [JAVA] - Java의 동기화 및 Locking 기법 들 (Synchronized, ReentrantLock, Semaphore, Atomic Package, varHandle)

이 내용을 참고하면 좋다.