【基本情報】独学マラソン 疎行列 Day 32

この記事は自分用の備忘録です。

疎行列とは

0がいっぱいある行列（二次元配列）

[
  [3, 0, 0, 0, 0],
  [0, 2, 2, 0, 0],
  [0, 0, 0, 1, 3],
  [0, 0, 0, 2, 0],
  [0, 0, 0, 0, 1]
]

やること

0がいっぱいあるとデータとして効率が悪いので、0をなくした良い感じのデータに変換せよ

やってみる

sparseMatrix.ts

// 元データ
const matrix: number[][] = [
  [3, 0, 0, 0, 0],
  [0, 2, 2, 0, 0],
  [0, 0, 0, 1, 3],
  [0, 0, 0, 2, 0],
  [0, 0, 0, 0, 1]
];

// 圧縮データ構造の型
type SparseMatrix = [number[], number[], number[]];

// 疎行列を圧縮データ構造に変換する関数
function transformSparseMatrix(matrix: number[][]): SparseMatrix {
  const sparseMatrix: SparseMatrix = [[], [], []];

  for (let i = 0; i < matrix.length; i++) {        
    for (let j = 0; j < matrix[i].length; j++) {    
      if (matrix[i][j] !== 0) {                    
        sparseMatrix[0].push(i + 1);        // rowを入れる
        sparseMatrix[1].push(j + 1);        // columnを入れる   
        sparseMatrix[2].push(matrix[i][j]); // 値を入れる
      }
    }
  }

  return sparseMatrix;
}

// 疎行列を圧縮データ構造に変換
const result: SparseMatrix = transformSparseMatrix(matrix);

// 結果の表示
console.log("行番号:", result[0]);
console.log("列番号:", result[1]);
console.log("値:", result[2]);

実行!!

(1,1)->3
(2,2)->2
(2,3)->2
...

合っている！

感想

めっちゃ数Cだった。

参考