3

ベクトル/（非対称）行列（対称のような構造を持つ行列は、もちろんループで利用できますが、私には関係ありません質問) インデックスのコレクションによってポイントされます。基本的に、このコードは、たとえば 2D マトリックスを通るルートのコストを計算するために使用できます。GPUではなくCPUを利用する方法を探しています。

関連するコードを次に示します。私がより興味を持っているのは最初のケースです。ラムダを使用してインデックス ベクトルをキャプチャすることは可能だと考えていましstd::accumulateたが、おそらく他の演算子を使用して、より適切な方法が既にあるかどうか疑問に思いました。ループは私の好みでも非常に明確であるため、「本当の問題」ではありませんが、非常にきちんとした、またはより効率的なオンラインライナーを探しています...

template<typename out_type>
out_type sum(std::vector<float> const& matrix, std::vector<int> const& indices)
{
    out_type cost = 0;
    for(decltype(indices.size()) i = 0; i < indices.size() - 1; ++i) 
    {
        const int index = indices.size() * indices[i] + indices[i + 1];
        cost += matrix[index];
    }

    const int index = indices.size() * indices[indices.size() - 1] + indices[0];
    cost += matrix[index];

    return cost;
}

template<typename out_type>
out_type sum(std::vector<std::vector<float>> const& matrix, std::vector<int> const& indices)
{
    out_type cost = 0;
    for(decltype(indices.size()) i = 0; i < indices.size() - 1; i++) 
    {
        cost += matrix[indices[i]][indices[i + 1]];
    }
    cost += matrix[indices[indices.size() - 1]][indices[0]];

    return cost;
}

ああ、PPL / TBBも公正なゲームです。

編集

後付けとして、ジョンにコメントしたように、入力と出力の型が異なる可能性があるため、計算にstd::common_typeを使用する場所はありますか? これは少し手を振っており、テクニックやライブラリの学習に似ています。よろしければ、コード kataの形式。

編集 2

現在、ブロガーtheowl84によるSSE コードを使用して STL ベクトルを処理する方法に関するブログ記事で説明されているように、ループを高速化するオプションが 1 つあります。コードは を使用していますが、 DirectXMathライブラリにも何かあるのではないでしょうか。__m128 directly

編集 3

さて、いくつかの具体的なコードを書いた後、私std::accumulateはうまくいかないことがわかりました。または、少なくとも、それ自体が現在の値と合計のみにアクセスできるため、きちんとした方法でその[indices[i + 1]部分を実行する方法を見つけることができませんでした。その点では、小説家のアプローチが最も実りあるものに見えます。matrix[indices[i]][indices[i + 1]];std::accumulate

DeadMGは、アソシアティビティに関する注意事項を伴うparallel_reduceの使用を提案し、 novocratによってさらにコメントされました。インターフェイスがちょっと面倒に思えたので、 parallel_reduceを使用できるかどうかは調べませんでした。それ以外は、私のコードはシリアルに実行されますが、並列削減バージョンと同じ浮動小数点の問題が発生する可能性があります。パラレルバージョンは、シリアルバージョンよりも（はるかに）予測不可能になる可能性がありますが、私は思います.

これは少し関係がありませんが、ここでつまずいた人にとっては興味深いかもしれませんし、ここまで読んだ人にとっては、NAG ブログの Wandering Precision の記事に (非常に) 興味があるかもしれません。再注文！次に、#AltDevBlogADay同期 RTS エンジンと非同期の話 の分散設定で、まさにこの問題についていくつかの反省があります。また、ACCU (ちなみに、一般的なメーリング リストは優れており、参加は無料です) には、浮動小数点の精度に関する記事 (たとえば、この) がいくつか掲載されています。接線から接線へ、幾何学的計算におけるFernando Cacciola のロバストネスの問題を見つけました 元は ACCU メーリング リストからの良い記事です。

そして、std::common_type. そのための使用法が見つかりませんでした。パラメータとして2つの異なるタイプがある場合、戻り値はによって決定される可能性があります/決定されるべきstd::common_typeです。おそらく、より適切なのはstd::is_convertible、static_assert目的の結果の型が引数の型から変換可能であることを確認することです (明確なエラー メッセージを使用して)。それ以外は、戻り値/中間計算値の精度がオーバーフローなどのない合計の結果を表すのに十分であることを確認することしかできませんが、そのための標準的な機能に出くわしていません。

それについては、ご列席の皆様。私は自分自身を楽しんだ、これを読んでいる人もこれから何かを得ることを願っている.

4

2 に答える 2

1

適切な値を取得matrixして生成するイテレータを生成できます。indices

class route_iterator
{
  vector<vector<float>> const& matrix;
  vector<int> const& indices;
  int i;

public:
  route_iterator(vector<vector<float>> const& matrix_, vector<int> const& indices_,
                 int begin = 0)
  : matrix(matrix_), indices(indices_), i(begin)
  { }
  float operator*() {
    return matrix[indices[i]][indices[(i + 1) % indices.size()]];
  }
  route_iterator& operator++() {
    ++i;
    return *this;
  }
};

次に、累積が からroute_iterator(matrix, indices)まで実行されroute_iterator(matrix, indices, indices.size())ます。

確かに、これは、スマート コンパイラーが並列処理に変換しなくても順次処理されます。本当に必要なのは、マップとフォールド (累積) 操作の並列処理です。

于 2012-09-08T21:16:46.857 に答える
0 
out_type cost = 0;
for(decltype(indices.size()) i = 0; i < indices.size() - 1; i++) 
{
    cost += matrix[indices[i]][indices[i + 1]];
}

これは基本的にstd::accumulateです。PPL は (TBB もそうです) parallel_reduceを提供します。これには結合性が必要ですが交換性は必要ありません+。実数/浮動小数点数/整数は結合性があります。

于 2012-09-08T21:40:27.253 に答える