データ構造のスパース行列

このセクションでは、スパース行列とは何か、およびそれらをメモリ内でどのように表現できるかを説明します。したがって、行列のほとんどの要素が0の場合、行列はスパース行列になります。別の定義は、最大1/3の非ゼロ要素（m x nの約30％）を持つ行列はスパース行列と呼ばれます。

コンピュータのメモリ内の行列を使用して、効率的な方法でいくつかの操作を実行します。ただし、行列が本質的にスパースである場合は、操作を効率的に実行するのに役立つ可能性がありますが、メモリ内のスペースが大きくなります。そのスペースには目的がありません。したがって、スパース行列を格納するために他の種類の構造に従います。

以下のようなスパース行列があるとします-

ご覧のとおり、ゼロ以外の要素が8つ、ゼロ値が28あります。この行列は6*6=36のメモリスペースを使用しています。マトリックスのサイズが大きい場合、スペースの浪費が増加します。

テーブル構造を使用して、スパース行列に関する情報を格納できます。以下のようにXというテーブルを作成するとします-

ここで、最初の列は行番号を保持し、2番目の列は列番号を保持しています。 3つ目は、M [row、col]に存在するデータを保持することです。このテーブルの各行は、3つのパラメーターがあるため、トリプレットと呼ばれます。最初のトリプレットは、マトリックスのサイズ情報を保持しています。行=6および列=6は、行列Mが6x6行列であることを示しています。値フィールドは、配列に存在するゼロ以外の要素の数を示しています。

このテーブルも9*3 =36のスペースを使用しているので、ゲインはどこにありますか？行列のサイズが8*8 =64であるが、要素が8つしかない場合、テーブルXも36単位のスペースを取ります。固定された3つの列があり、行の数はゼロ以外の要素の数によって変化することがわかります。したがって、ゼロ以外の要素がT個ある場合、空間の複雑さはO（3 * T）=O（T）になります。行列の場合、O（m x n）になります。