私は累乗反復アルゴリズムで疎行列のイェール表現を使用しています。すべてがうまくいきます。
しかし、ここで問題が発生しました。私の教授は疎行列を順序付けされていないデータ ファイルで送信します。行列は対称であるため、インデックスのペアは 1 つしか存在しません。
問題は、私の実装では、要素を順番に挿入する必要があることです。
私は何かを読んで、その後スパースマトリックスに挿入しようとしました:
1) 密行列の使用。
2) 別の疎行列の実装を使用して、std::map を試しました。
3) プライオリティ キュー、priority_queues の配列を作成しました。要素 i,j を priority_queue[i] に挿入するので、priority_queue[i] をポップすると、行 i の最小の j-index が取得されます。
しかし、私が使用する最大の行列は 100k x 100k のようなものになるため、非常に高速でメモリ効率の良いものが必要です。
助言がありますか？下手な英語でごめんなさい:(
多くのスパース ローダーの動作方法は、中間の純粋なトリプル構造を使用することです。つまり、ファイルがどのように見えても、次のようなものにロードしますvector< tuple< row, column, value> >。
次に、そのからスパース構造を構築します。その理由は、まさにあなたが遭遇しているものです。疎行列構造には、各行/列の要素数を知る必要がある、または入力を並べ替える必要があるなどの制約がある可能性があります。トリプル配列を必要なものに (つまり、並べ替えることで) マッサージできます。
これにより、対称性のジレンマを解決することも簡単になります。ソース ファイル内のすべてのトリプルについて、中間構造に と の両方を挿入します(row, column, value)。(column, row, value)
もう 1 つのオプションは、教授のファイルを並べ替えるスクリプトを単純に作成することです。
参考までに、まばらな世界では、行列の次元ではなく、要素の数 (非ゼロ) が重要です。100k-by-100k意味のない情報です。たとえば、そのマトリックス全体が完全に空になる可能性があります。