행렬의 곱셈

고딩때 많이 풀었던 그거다

좌측 행렬은 가로, 우측 행렬은 세로를 곱해서 새로운 행렬은 만든다...

1. arr1의 길이만큼
2. return[i][n]에 arr1[i][j] * arr2[j][k]를 배열로 넣는다

arr2의 가로세로를 바꾸면 시간복잡도가 한 차원 내려가지 않을까 생각했는데 결국 계산은 똑같이 하기때문에 의미가 없었다.

코드 구현 과정

뭔가 이상하다... 행하고 열을 바꿔보자

생각해보니 arr2의 2차 배열의 길이만큼 연산을 해야하니 col1과 2를 바꾸었다

다른 사람의 코드와 속도 비교

function sol00(arr1, arr2) {
  const answer = [];

  const row1 = arr1.length;
  const col1 = arr2[0].length;
  const col2 = arr1[0].length;

  for (let i = 0; i < row1; i++) {
    const newArray = [];
    for (let j = 0; j < col1; j++) {
      let sum = 0;
      for (let k = 0; k < col2; k++) {
        sum += arr1[i][k] * arr2[k][j];
      }
      newArray.push(sum);
    }
    answer.push(newArray);
  }

  return answer;
}

function sol10(arr1, arr2) {
  return arr1.map((row) =>
    arr2[0].map((x, y) => row.reduce((a, b, c) => a + b * arr2[c][y], 0))
  );
}

function sol20(A, B) {
  return A.map(function (row) {
    return row.map(function (_, i) {
      return row.reduce(function (sum, cell, j) {
        return sum + cell * B[j][i];
      }, 0);
    });
  });
}

sol10과 sol20은 사실상 같은 코드다. 화살표 함수와 중첩된 함수의 차이 정도...

시간 복잡도는 셋다 $O(n * o * p)$이다
n = arr1의 행
o = arr1의 행 = arr2의 열
p = arr2의 열

또 sol20에서 reduce가 범위 초과하는 문제가 발견되어 B[0]으로 수정했다.

처음에는 내 코드가 제일 빨랐는데 행렬의 크기가 커지니까 연산량이 더 많은 배율로 증가했다.

10배가 아니라 100배로 해보자

뭔가 충격적인 결과다...

어짜피 처음에 2배 빠르기 때문에 처리 시간이 2배율로 더 증가해도 그렇게 큰 차이가 나지는 않는다?...

애초에 행렬을 100만개나 쉬지않고 처리할 일이 있을지도 의문이고?

배운 점

1. 큰 덩어리의 데이터를 처리할 때 for문 중첩보다 map/reduce를 중첩하는게 더 효율적일 수 있다.
   자바스크립트 엔진에서의 최적화 차이인듯 하다

2. 항상 큰 덩어리로 처리할 게 아니라면 작은 덩어리일 때 빠른 방식으로 짜는것도 좋을 것 같다

3. 거의 같은 함수라도 구현 방법에 따라서 인자를 다르게 설정해야할 수 있다. (sol20이 reduce > B[0] 으로 바꾼 것)

코드

const arr1 = [
  [2, -3, 4, 1, -1, 3],
  [1, 0, -1, 2, 3, -2],
  [3, 5, -2, 1, 0, 4],
  [0, 1, 2, -3, 4, 2],
  [4, -1, 0, 3, 2, 1],
];

const arr2 = [
  [-2, 3, 1, 0],
  [1, 4, -1, 2],
  [0, -1, 2, -2],
  [3, -2, 1, 1],
  [2, 1, -3, 0],
  [-1, 2, 0, 3],
];

function multiplyElements(arr, factor) {
  return arr.map((row) => row.map((value) => value * factor));
}

const n1 = 100;
const n2 = 100;

const arr12 = arr1.map((row) => {
  const newRow = [];
  for (let i = 0; i < n1; i++) {
    newRow.push(...row);
  }
  return newRow;
});

const arr22 = [];
for (let i = 0; i < n1; i++) {
  arr2.forEach((row) => arr22.push([...row]));
}

const arr13 = multiplyElements(arr1, n2);
const arr23 = multiplyElements(arr2, n2);

function sol00(arr1, arr2) {
  const answer = [];

  const row1 = arr1.length;
  const col1 = arr2[0].length;
  const col2 = arr1[0].length;

  for (let i = 0; i < row1; i++) {
    const newArray = [];
    for (let j = 0; j < col1; j++) {
      let sum = 0;
      for (let k = 0; k < col2; k++) {
        sum += arr1[i][k] * arr2[k][j];
      }
      newArray.push(sum);
    }
    answer.push(newArray);
  }

  return answer;
}

function sol10(arr1, arr2) {
  return arr1.map((row) =>
    arr2[0].map((x, y) => row.reduce((a, b, c) => a + b * arr2[c][y], 0))
  );
}

function sol20(A, B) {
  return A.map(function (row) {
    return B[0].map(function (_, i) {
      return row.reduce(function (sum, cell, j) {
        return sum + cell * B[j][i];
      }, 0);
    });
  });
}

function runtime(func, a, b) {
  const n = 1000000;
  const startTime = Date.now();

  for (let i = 0; i < n; i++) {
    func(a, b);
  }

  const endTime = Date.now();
  const executionTime = endTime - startTime;

  console.log(
    `${func.name} 함수 반복 횟수 ${n}회, 실행시간 : ${executionTime} ms`
  );
}

const list = [sol00, sol10, sol20];

for (let i = 0; i < list.length; i++) {
  for (let k = 0; k < 3; k++) {
    runtime(list[i], arr1, arr2);
  }
  console.log(`배열이 ${n1}배로 길어진 경우`);
  for (let k = 0; k < 3; k++) {
    runtime(list[i], arr12, arr22);
  }
  console.log(`배열의 원소가 ${n2}배로 커진경우`);
  for (let k = 0; k < 3; k++) {
    runtime(list[i], arr13, arr23);
  }
  console.log("---");
}