4

MATLAB関数の機能を実装しようとしていますsparse。

次のような特定のインデックスでスパース行列に値を挿入します。

同じインデックスの値がすでにマトリックスに存在する場合は、新しい値と古い値が追加されます。

それ以外の場合は、新しい値がマトリックスに追加されます。

機能addNodeは正常に動作しますが、問題は非常に遅いことです。この関数を約100000回ループで呼び出し、プログラムの実行に3分以上かかります。MATLABは、このタスクをほんの数秒で実行します。コードを最適化する方法や、自分の関数の代わりにstlアルゴリズムを使用して、目的を達成する方法はありますか？

コード：

struct SparseMatNode
{
   int x;
   int y;
   float value;
};

std::vector<SparseMatNode> SparseMatrix;

void addNode(int x, int y, float val)
{
   SparseMatNode n;
   n.x = x;
   n.y = y;
   n.value = val;

   bool alreadyPresent = false;

   int i = 0;
   for(i=0; i<SparseMatrix.size(); i++)
   {
    if((SparseMatrix[i].x == x) && (SparseMatrix[i].y == y))
    {
        alreadyPresent = true;
        break;
    }
   }

   if(alreadyPresent)
   {
    SparseMatrix[i].value += val;
    if(SparseMatrix[i].value == 0.0f)
        SparseMatrix.erase(SparseMatrix.begin + i);
   }
   else
    SparseMatrix.push_back(n);
}
4

5 に答える 5

5

スパース行列は、試みているように、通常、トリプレットのベクトルとして保存されません。

MATLAB (および他の多くのライブラリ) は、静的行列に対して非常に効率的な Compressed Sparse Column (CSC) データ構造を使用します。sparseまた、MATLAB 関数は、一度に 1 つのエントリを作成しません(試みているように)。トリプレット エントリの配列を取り、シーケンス全体を CSC 行列にパックします。静的疎行列を作成しようとしている場合は、これが最適です。

エントリの効率的な挿入と削除をサポートする動的な疎行列オブジェクトが必要な場合は、さまざまな構造 (おそらくstd::mapトリプレットの 1 つ、または列リストの配列) を調べることができます。データ形式の詳細については、こちらを参照してください。

また、多くの優れたライブラリがあります。疎行列演算/因数分解などを行いたい場合は、 SuiteSparseが適切なオプションです。それ以外の場合は、Eigenも適切な疎サポートを備えています。

于 2012-11-19T07:44:01.077 に答える
3

スパース行列は通常、圧縮スパース行 (CSR) または圧縮スパース列 (CSC、Harwell-Boeing とも呼ばれる) 形式で格納されます。MATLAB は既定で CSC、IIRC を使用しますが、ほとんどの疎行列パッケージは CSR を使用する傾向があります。

いずれにせよ、これが学習演習ではなく本番用である場合は、スパース行列をサポートする行列パッケージを使用することをお勧めします. C++ の世界では、私のお気に入りはEigenです。

于 2012-11-19T07:40:54.327 に答える
2

まばらなノードのベクトルを並べ替えてみましたか? ノードを追加するたびに線形検索を実行すると、コストがかかります。その場で挿入し、常にバイナリ検索を実行できます。

于 2012-11-19T07:40:11.637 に答える
2

最初の考えは、要素を見つけるための独自の機能を実装しているということです。それstd::findが目的です。したがって、代わりに：

bool alreadyPresent = false;

int i = 0;
for(i=0; i<SparseMatrix.size(); i++)
{
  if((SparseMatrix[i].x == x) && (SparseMatrix[i].y == y))
  {
    alreadyPresent = true;
    break;
  }
}

あなたは書くべきです：

auto it = std::find(SparseMatrix.begin(), SparseMatrix().end(), Comparer);

whereは 2 つのオブジェクトComparerを比較する関数です。SparseMatNode

しかし、主な改善は、適切なコンテナーを使用することから得られます。の代わりにstd::vector、連想コンテナを使用する方がはるかに優れています。このように、要素を見つけることはO(logN)複雑ではなく単純になりO(N)ます。SparseMatNode次のように、クラスをわずかに変更できます。

typedef std::pair<int, int> Coords;
typedef std::pair<const Coords, float> SparseMatNode;

もちろん、この typedef をクラス内でカバーして、より優れたインターフェイスを提供することもできます。

その後：

std::unordered_map<Coords, float> SparseMatrix;

このようにして、次を使用できます。

auto it = SparseMatrix.find(std::make_pair(x, y));

より効率的に要素を見つけることができます。

于 2012-11-19T07:54:54.137 に答える
-1

疎行列は巨大で圧縮する必要があるため、 を使用できますstd::unordered_map。行列のインデックス (xとy) は常に正であると仮定します。

#include <unordered_map>

const size_t MAX_X =  1000*1000*1000;
std::unordered_map <size_t, float> matrix;

void addNode (size_t x, size_t y, float val)
{
   size_t index = x + y*MAX_X;
   matrix[index] += val;      //this function can be still faster
   if (matrix[index] == 0)    //using find() / insert() methods
       matrix.erase(index);
}

std::unordered_mapお使いのシステムで が利用できない場合は、試してみるstd::tr1::unordered_mapかstdext::hash_map...

より多くのメモリを使用できる場合は、double代わりに を使用するとfloat、処理速度が少し向上します。

于 2012-11-19T07:34:21.847 に答える