数组的累积乘积：std::accumulate vs 循环

Question

假设我想计算数组前 k 个元素的累积乘积。

int arr[8] = {3, 5, 7, 4, 8, 9, 1, 2};
int k = 3;

就性能而言，哪一个是最佳选择？

方案一.普通for循环

int result = 1;
for (size_t i = 0; i < k; ++i) {
    result *= arr[i];
}

选项2.积累

result = std::accumulate(std::begin(arr),
                         std::begin(arr) + k,
                         1,
                         [](const int& x, const int &y) { return x*y; });

我对 k 较小的情况特别感兴趣，例如 k = 3 或 k = 4。在这种情况下，花哨的 C++11 做事方式真的值得吗？

Answer 1

简短的回答：使用算法而不是手写循环与性能无关！您可以看到一个可能的实现 here。您会注意到这只是一个循环，您也可以自己编写。

更好的比较是手写循环 vs:

auto result = std::accumulate(std::begin(arr),
                              std::begin(arr) + k,
                              1,
                              std::multiplies<>{});

相当于手写循环，不需要C++11（仅auto、std::begin和std::end，std::multiplies<>需要C ++14，但在你使用 std::multiplies<int>).

之前

该算法的优点是表现力和可读性。你不能给一个循环命名，而算法名称告诉它它做了什么。二元运算符和初始值也更容易替换。初始值不一定与元素同类型，从中推导出accumulate的return类型。如果您想乘以更多的值并避免溢出，您只需将 1 替换为 1L。如果您后来决定不想乘法，而是想加法，您只需将 std::multiplies 替换为 std::plus。对于手写循环，这种重构需要深入细节并考虑整个循环，而不是只更改您想要更改的一个细节。除此之外，哪个是“更好”是基于意见的。性能方面预计不会有太大差异，如果有的话。

请注意，C++11 和 C++14 带来的变化不仅仅是“花哨”。在 C++11 之前，调用看起来像这样：

int result = std::accumulate(arr,                        // <- int
                             arr + k,
                             1,                          // <- int
                             std::multiplies<int>{});    // <- int

此处用于结果的类型出现了 3 次，这使得上面关于轻松替换初始值类型的观点变得毫无意义。 auto 和具有模板化 operator() 的仿函数带来的变化并不是花哨的，而是显着减少了犯错误的机会。

TL;DR

对于像您这样简单的循环，我可能会使用手写循环。它清晰易读，不太可能有任何花哨的算法可以提高它的性能。

Answer 2

两种方法都可以；都不错。他们之间的选择见仁见智。

后者几乎不是“花哨的 C++11”，因为使用的唯一有意义的 C++11 功能是 lambda，它可以用 std::multiplies 替换，或者在一般情况下用函数对象替换“花哨的 C++98”。（是的 std::begin 也在 C++11 中添加，但您可以简单地删除它，因为它不是必需的）。

我想推荐一个范围替代方案。不幸的是 C++20 没有包含 std::ranges::accumulate，所以我不得不建议使用非标准算法来代替：

std::ranges::subrange sub1(arr, arr + k);
auto sub2 = std::views::counted(arr, k); // alternative
std::span sub3(arr, k);                  // less general alternative

// no standard ranges alternative for this yet
auto result = ranges::accumulate(sub1, 1, std::multiplies<>{});

Which one is the best option in terms of performance?

Both/neither。任何体面的优化器都应该产生相同的程序集。

数组的累积乘积：std::accumulate vs 循环

Cumulative product of an array: std::accumulate vs loop

c++

accumulate