c++ - 如何使用 std::accumulate 对单独定义的索引指向的 vector 中的值进行巧妙的求和(替换循环)

Question

我想知道是否有一种更简洁(或更好、更有效)的方法来对 vector/(非对称)矩阵的值求和(具有类似对称结构的矩阵，当然可以在循环中利用，但不是那样与我的问题相关)由一组索引指出。基本上，此代码可用于计算通过二维矩阵的路线成本。我正在寻找一种利用 CPU 而不是 GPU 的方法。

下面是一些相关的代码，我比较感兴趣的是第一种情况。我在想可以将 std::accumulate 与 lambda 一起使用来捕获索引 vector ，但后来我想知道，是否已经有更简洁的方法，也许与其他运算符一起使用。这不是一个“真正的问题”，因为循环对我的口味来说也很清楚，但在寻找 super 整洁或更高效的在线程序时......

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在计算中输入和输出类型可能不同？这有点挥手，更像是学习技术和图书馆。 code kata 的一种形式，如果你愿意的话。

编辑2

现在，有一种方法可以使循环更快，在博客文章中有解释 How to process a STL vector using SSE code由博主 theowl84 撰写。代码中直接使用了__m128，但是不知DirectXMath里面有没有图书馆也是。

编辑3

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

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

这有点离题，但这里的一些绊脚石可能会感兴趣，而那些读到这里的人可能会对文章 Wandering Precision 感兴趣(非常)在 NAG blog ，其中详细介绍了一些甚至由硬件指令重新排序引入的复杂问题!然后在#AltDevBlogADay Synchronous RTS Engines and a Tale of Desyncs 中对分布式设置中的这个问题进行了一些反射(reflection)。 .另外，ACCU (顺便说一下，一般邮件列表非常好，而且可以免费加入)有几篇关于浮点精度的文章(例如 this)。相切相切，我找到了 Fernando Cacciola 的 Robustness issues in geometric computing成为一篇值得阅读的好文章，最初来自 ACCU 邮件列表。

然后是 std::common_type。我找不到它的用法。如果我有两种不同的类型作为参数，那么返回值可以/应该由 std::common_type 决定。也许更相关的是 std::is_convertible 和 static_assert 以确保所需的结果类型可以从参数类型转换(带有干净的错误消息)。除此之外，我只能检查返回值/中间计算值的准确性是否足以表示求和结果而不会溢出之类的，但我还没有遇到过标准的工具。

女士们，先生们，我想就是这样。我玩得很开心，我希望阅读本文的人也能从中有所收获。

Answer 1

您可以生成一个采用矩阵 和索引 并产生适当值的迭代器。

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())。

不过，不可否认，这在没有智能编译器将其转换为并行的情况下进行顺序化。您真正想要的是并行映射和折叠(累积)操作。