没有for循环的集合中n个连续项的总和

Question

我正在寻找如何删除我的 for 循环以计算集合中 n 个连续项目的总和。

Example: for the collection {1,2,1,3,2} and n=3 (where n is the number of consecutive items to process), the result would be {0,0,4,6,6}

{1,2,1,3,2} and n=3 produces {0,0,4,6,6}

要确定两个连续项的总和，我知道我可以这样做：

std::adjacent_difference(std::begin(collection), 
                          std::end(collection), 
                         std::begin(adjacent_sum), 
[](const int x, const int y) { return std::abs(x - y); });

但是为了确定 n 个连续项目的总和，我被这样一个事实所困扰，像 std::transform 这样的算法在我需要索引时处理值。我是否应该在算法之外使用索引作为变量来维护状态。

这是一个用 Visual Studio 2019 编译的完整示例：

#include <iostream>   
#include <numeric>    
#include <vector>

// Compute the sum of the n consecutive items
// Ex: {1,2,1,3,2} and n=3
// result: {0,0,4,6,6}
std::vector<int> adjacent_difference_n(const std::vector<int> collection, const size_t num_consecutive_items) 
{
    std::vector<int> result {};
    const auto collection_size = collection.size();

    for (size_t idx = 0; idx < num_consecutive_items - 1; idx++)
    {
        result.emplace_back(0);
    }

    if (collection_size >= num_consecutive_items)
    {
        // For each element starting at num_consecutive_items
        for (auto idx = num_consecutive_items - 1; idx < collection_size; idx++)
        {
            // Compute the sum of the previous num_consecutive_item
            // Loop includes the current item
            auto sum = 0;
            auto prev_idx = idx - (num_consecutive_items - 1); 
            while (prev_idx <= idx)
            {
                sum += collection[prev_idx++];                
            }
            result.emplace_back(sum);
        }
    }

    return result;
}

int main()
{
    const std::vector<int> collection = { 1, 2, 1, 3, 2 };
    const auto result = adjacent_difference_n(collection, 3);
    for (auto& value : result) std::cout << value << " ";
    std::cout << std::endl;
    return 0;
}

Answer 1

我终于找到了解决问题的方法。

对于任何感兴趣的人，我使用 std::fill and std::for_each:

#include <iostream>   
#include <vector>
#include <numeric>
#include <algorithm>

// Compute the sum of the n consecutive items
// Ex: {1,2,1,3,2} and n=3
// result: {0,0,4,6,6}
std::vector<int> adjacent_sum_n(const std::vector<int> collection, const size_t num_consecutive_items)
{
    // Create the result collection with the same size than the specified collection
    const auto collection_size = collection.size();
    std::vector<int> result{};
    result.resize(collection_size);

    // Fill to zero the items that have not enough previous items
    std::fill(begin(result), begin(result) + num_consecutive_items - 1, 0);

    // For each remaining items, compute the sum the n consecutive items
    auto idx = num_consecutive_items - 1;
    std::for_each(begin(result) + idx,
                   end(result),
    [&](auto& value)
    {
        const auto first_item_idx = idx - num_consecutive_items + 1;
        const auto sum = std::accumulate(begin(collection) + first_item_idx,
            begin(collection) + idx + 1,
            0);
        ++idx;
        value = sum;
    });

    return result;
}

int main()
{
    const std::vector<int> collection = { 1, 2, 1, 3, 2 };

    const auto result = adjacent_sum_n(collection, 3);

    for (auto& value : result) std::cout << value << " ";

    std::cout << std::endl;

    return 0;
}

Answer 2

您可以通过减去第一项并添加新项来避免内部循环更新部分和：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <class T>
auto partial_sum_n(std::vector<T> const& src, size_t m)
{
    // Initialize the resulting vector with zeroes
    std::vector<T> result(src.size());
    if (m == 0  or  src.size() < m)
        return result;

    auto first = src.cbegin();
    auto it = std::next(first, m);

    // Sum the first elements and assign to the first non zero element
    auto sum = std::accumulate(first, it, T(0));
    auto dest = std::next(result.begin(), m - 1);
    *dest = sum;

    // Fill the rest of the vector 
    std::transform(it, src.cend(),
                   ++dest,
                   [first, sum] (T const& x) mutable {
                       sum += x - *(first++);    // <-- Just update the sum
                       return sum;
                   });

    return result;
}

int main()
{
    const std::vector<int> collection{ 1, 2, 1, 3, 2 };
    const auto result = partial_sum_n(collection, 3);
    for (auto const value : result)
        std::cout << ' ' << value;
    std::cout << '\n';
}

没有for循环的集合中n个连续项的总和

Sum of n consecutive items in a collection without for loops

c++

c++-standard-library