多くのゼロを含む行列のデータ構造ですか？

Question

C++では、ゼロの約90％（ゼロの真の周波数はユーザー入力に依存する）で作られた非常に大きな正方行列をRAMに保存する必要があります。これらすべてのゼロにメモリを割り当てることはRAMの無駄になります。

RAMをほとんど使用しないクラスを作成して、この大きなマトリックスにinstance.getElement(row,column)のような要素を付けると便利ですか？

Answer 1

多くの方法があります。しかし、最初に考慮する必要があるのは、アクセスする要素がより複雑になるため、これを実行するとパフォーマンスが低下することです。第二に、LAPACKのような有名なライブラリを使うことができません。私が知る限り、それらは複雑なデータ構造のためのインタフェースを提供しないからです。だから、数学演算をしたいときはいつでも、行列を圧縮解除して平らにしなければなりません。そうしないと、実際には簡単ではない操作を行うコードを再開発する必要がありますする。 LAPACKをした人々はそれを数年間研究しました。

私が言っていることは、これを行う前の結果を考えてみてください。

今結果を述べた後、私は頭の上から方法を言及することができます。

1. あなたの行列をcolumn major（つまりメモリの列の後の列）に並べ替えて、メモリ内で連続したフラットな配列として考えてみましょう。
2. この行列は、多くのゼロを持つリストです。あなたの質問は：これらのゼロをどのように排除するのですか？

はよく行くために多くの方法があり、それぞれの方法は、私は方法のいくつかを言及してみましょう、あなたのアプリケーションに依存して異なる計算の複雑さを持つことになります。

• あなたはlinked listを使用することができ、どこすべての要素はstd::pairになり、現在の行列要素の値と次に利用可能な要素のインデックスが格納されます。

• リンクされたリストを使用すると、圧縮ソフトウェアが動作する方法を使用して、すべての要素の前にいくつのゼロがあるかを数え、すべての要素のコンテナに格納できます。

あなたは、実際に行く方法がたくさんあると思います。しかし、あなた自身に尋ねます：あなたが探している計算の複雑さは何ですか？

これが役に立ちます。

Answer 2

マップにすべてを保存するクラスを作成できます。したがって、存在しない要素を要求する場合は0を返し、それ以外の場合は要素を返します。

#include <map> 

using namespace std; 

#define ROW_LENGTH 10; 

map<int, int> entries = map<int, int>(); 

int getElement(int row, int column) { 
    int key = column * ROW_LENGTH + row; 

    if (entries.find(key) == entries.end()) { 
    return 0; 
    } else { 
    return entries[key]; 
    } 
} 
void setElement(int row, int column, int value) { 
    int key = column * ROW_LENGTH + row; 

    entries[key] = value; 
} 

Answer 3

疎行列操作を行うには、固有ライブラリを使用できます。ここにリンクがあります：https://eigen.tuxfamily.org/dox/group__TutorialSparse.html

Eigenは高性能線形代数ライブラリです。スパース行列は、2Dリンクリストのように格納されます（または、ネットワークと言うべきですか）。すべての非ゼロ項目には、同じ行の次の非ゼロ項目を指すポインタと、同じ列の次の非ゼロ項目を指すポインタの2つのポインタがあります。スパース行列をベクトルに反復的に乗じることに基づく行列積および他の多くの線形アルベグラ操作は、2Dリンクリスト表現において効率的に行うことができる。

Answer 4

マトリックスを動的に変更する必要がない場合は、[1]を参照してCRS形式（圧縮行ストレージ）を使用できます。ポインタを格納するために余分なスペースが必要な、他の答えで提案されているリンクされたリストよりはるかにコンパクトです。これは、別の答えで引用されたSuiteSparse [2]やEigen [3]や自分のOpenNLライブラリ[4]など、多くのソフトウェアライブラリで実装されています。行列に要素を動的に挿入する必要がある場合は、より複雑になります。私はしばしば、動的に割り当てられた行の配列を使用します（1つに1つ）。各行にはJ値のペアが格納されます。この構造もOpenNL [4]で実装されています。

[1] https://en.wikipedia.org/wiki/Sparse_matrix

[2] http://faculty.cse.tamu.edu/davis/suitesparse.html

[3] http://eigen.tuxfamily.org/

[4] http://alice.loria.fr/software/geogram/doc/html/nl_8h.html