3

我想知道是否有一种更简洁（或更好，更有效）的方法来求和向量/（不对称）矩阵的值（具有对称结构的矩阵，当然可以在循环中利用，但与我的无关问题）由一组索引指向。基本上，此代码可用于计算通过 2D 矩阵的路线的成本。我正在寻找一种利用 CPU 而不是 GPU 的方法。

这是一些相关的代码，我更感兴趣的是第一个案例。我在想可以使用std::accumulatelambda 来捕获索引向量，但后来我想知道，是否已经有一种更简洁的方法，也许还有其他一些运算符。循环不是“真正的问题”，因为我的口味也很清楚，但是在寻找超级整洁或更高效的在线...

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也是公平的游戏。

编辑

作为事后的想法和对 John 的评论，由于输入和输出类型可能不同，是否有地方在计算中使用std::common_type ？这有点像挥手，更像是学习技术和图书馆。代码 kata的一种形式，如果你愿意的话。

编辑 2

现在，有一个选项可以使循环更快，博主 theowl84 在博客中解释了如何使用SSE 代码处理 STL 向量。代码使用，但我想知道DirectXMath库中是否也有一些东西。__m128 directly

编辑 3

现在，在编写了一些具体代码之后，我发现std::accumulate不会让我走得太远。或者至少我找不到以简洁的方式完成该[indices[i + 1]部分的方法，因为它本身只能访问当前值和总和。从这个角度来看，novocrat 的方法似乎是最富有成效的方法。matrix[indices[i]][indices[i + 1]];std::accumulate

DeadMG建议使用带有关联性警告的parallel_reduce ， novocrat进一步评论。我没有去看看是否可以使用parallel_reduce，因为界面看起来有点麻烦，无法快速尝试。除此之外，即使我的代码是串行执行的，它也会遇到与并行缩减版本相同的浮动问题。虽然并行版本会/可能比串行版本更不可预测，我认为。

这有点切题，但这里的一些绊脚石可能会感兴趣，对于那些已经读过这篇文章的人来说，可能对NAG 博客中的Wandering Precision文章（非常）感兴趣，其中详细介绍了一些甚至由硬件指令引入的复杂问题重新订购！然后在#AltDevBlogADay Synchronous RTS Engines and a Tale of Desyncs中对分布式设置中的这个问题进行了一些反思。此外，ACCU（顺便说一下，通用邮件列表非常好，并且可以免费加入）包含几篇关于浮点精度的文章（例如this ）。切线切线，我发现了Fernando Cacciola在几何计算中的鲁棒性问题 成为一篇好文章，最初来自 ACCU 邮件列表。

然后是std::common_type. 我找不到那个用途。如果我有两种不同的类型作为参数，那么返回值可以/应该由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 回答