STL 的“partial_sum”有哪些实际用途？

Question

STL 中 partial_sum 算法的实际用途是什么？

还有哪些其他有趣/重要的示例或用例？

Answer 1

关于部分和需要注意的一件事是，它是撤销相邻差值的操作，就像 - 撤销 + 一样。或者如果你还记得微积分就像微分消除积分的方式，那就更好了。更好，因为相邻差本质上是微分，部分和是积分。

假设您要模拟一辆汽车，并且在每个时间步都需要知道位置、速度和加速度。您只需要存储这些值之一，因为您可以计算其他两个值。假设您存储每个时间步的位置，您可以采用位置的相邻差值来给出速度，并采用速度的相邻差值来给出加速度。或者，如果您存储加速度，则可以采用部分和来给出速度，而速度的部分和给出位置。

部分求和是大多数人不会经常出现的函数之一，但当您找到正确的情况时，它会非常有用。很像微积分。

Answer 2

上次我（本来）使用它是在将离散概率分布（p(X = k) 的数组）转换为累积分布（p(X <= k) 的数组）时。要从分布中选择一次，您可以从 [0-1) 中随机选择一个数字，然后对累积分布进行二分搜索。

不过，该代码不是用 C++ 编写的，所以我自己完成了部分求和。

Answer 3

您可以使用它来生成单调递增的数字序列。例如，以下代码生成一个包含数字 1 到 42 的向量：

std::vector<int> v(42, 1);
std::partial_sum(v.begin(), v.end(), v.begin());

这是日常用例吗？可能不是，尽管我多次发现它很有用。

您还可以使用 std::partial_sum 生成阶乘列表。 （不过，这甚至没那么有用，因为典型的整数数据类型可以表示的阶乘数量非常有限。不过，这很有趣:-D）

std::vector<int> v(10, 1);
std::partial_sum(v.begin(), v.end(), v.begin());
std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());

Answer 4

个人用例：轮盘轮选择

我在轮盘轮选择算法中使用 partial_sum (链接文本）。该算法从容器中随机选择元素，其概率与预先给定的某个值成线性。

因为我要选择的所有元素都带有不一定标准化的值，所以我使用 partial_sum 算法来构造类似“轮盘赌轮”的东西，因为我对所有元素进行了求和。然后我在这个范围内选择一个随机变量（最后一个 partial_sum 是所有变量的总和），并使用 stl::lower_bound 搜索我的随机搜索落地的“轮子” 。 lower_bound 算法返回的元素是所选元素。

除了使用 partial_sum 获得清晰且富有表现力的代码的优势之外，我在尝试 GCC 并行模式，为某些算法带来并行化版本，其中之一是partial_sum (链接文本）。

我知道的另一个用途：并行处理中最重要的算法原语之一（但可能与 STL 有点距离）

如果您对使用 partial_sum< 的深度优化算法感兴趣/code> （在这种情况下，同义词“scan”或“prefix_sum”下的结果可能比并行算法社区更多。他们一直需要它。您找不到基于 quicksort 或 mergesort 而不使用它。此操作是最重要的并行原语之一。我认为它最常用于计算动态算法中的偏移量。考虑快速排序中的分区步骤，该步骤被分割并馈送到并行线程。在计算之前，您不知道分区的每个槽中的元素数量。因此，您需要为所有线程提供一些偏移量以便以后访问。

也许您会在当前热门的 GPU 处理主题中找到更多信息。一篇关于 Nvidia 的 CUDA 和 scan-primitive 的简短文章，其中包含一些应用程序示例，您可以在 < em>第 39 章. 使用 CUDA 并行前缀和（扫描） 。

Answer 5

个人用例：CLRS 计数排序的中间步骤：

COUNTING_SORT (A, B, k)

for i ← 1 to k do
    c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i


// std::partial_sum here
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]


// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1

Answer 6

您可以构建一个“移动总和”（移动平均线的前体）：

template <class T>
void moving_sum (const vector<T>& in, int num, vector<T>& out)
{
    // cummulative sum
    partial_sum (in.begin(), in.end(), out.begin());

    // shift and subtract
    int j;
    for (int i = out.size() - 1; i >= 0; i--) {
        j = i - num;
        if (j >= 0)
            out[i] -= out[j];
    }    
}

然后用以下命令调用它：

vector<double> v(10);
// fill in v
vector<double> v2 (v.size());
moving_sum (v, 3, v2);

Answer 7

你知道，我实际上曾经使用过 partial_sum() 一次......这是我在工作面试中被问到的一个有趣的小问题。我非常喜欢它，我回家并把它编码了。

问题是：给定一个连续的整数序列，找到具有最高值的最短子序列。例如：

Value: -1  2  3 -1  4 -2 -4  5
Index:  0  1  2  3  4  5  6  7

我们会找到子序列 [1,4]

现在明显的解决方案是运行 3 个 for 循环，迭代所有可能的开始和结束。结束，依次将每个可能的子序列的值相加。效率低下，但编码速度快且不易出错。 （特别是当第三个 for 循环只是 accumulate(start,end,0) 时。）

正确的解决方案涉及分而治之/自下而上的方法。例如，将问题空间分成两半，并为每一半计算该部分中包含的最大子序列、包括起始数字的最大子序列、包括结束数字的最大子序列以及整个部分的子序列。有了这些数据，我们就可以将两半结合在一起，而无需对其中任何一个进行任何进一步的评估。显然，每一半的数据可以通过进一步将每一半分成两半（四分之一）、将每个四分之一分成两半（八分之一）等来计算，直到我们有简单的单例情况。这一切都非常有效。

但除此之外，我还想探索第三种（效率稍低）的选择。它类似于 3-for-loop 情况，只是我们添加相邻的数字以避免这么多工作。这个想法是，当我们可以添加 t1=a+b、t2=t1+c 和 t3=t2+d 时，就不需要添加 a+b、a+b+c 和 a+b+c+d。这是空间/计算权衡的问题。它的工作原理是转换序列：

Index: 0 1 2  3  4
FROM:  1 2 3  4  5
  TO:  1 3 6 10 15

从而为我们提供所有可能的子字符串，从索引 = 0 开始，到索引 = 0,1,2,3,4 结束。

然后我们迭代这个集合，减去连续的可能的“开始”点...

FROM:  1 3 6 10 15
  TO:  - 2 5  9 14
  TO:  - - 3  7 12
  TO:  - - -  4  9
  TO:  - - -  -  5

从而给我们所有可能的子序列的值（总和）。

我们可以通过max_element()找到每次迭代的最大值。

第一步最容易通过 partial_sum() 完成。

其余步骤通过 for 循环和 transform(data+i,data+size,data+i,bind2nd(minus(),data[i-1]))< /em>.

显然 O(N^2)。但还是很有趣、很好玩...

Answer 8

部分和在并行算法中通常很有用。考虑代码

for (int i=0; N>i; ++i) {
  sum += x[i];
  do_something(sum);
}

如果您想并行化此代码，您需要知道部分和。我正在使用 GNU 并行版本的partial_sum 来做一些非常类似的事情。

Answer 9

我经常使用部分求和，不是求和而是根据前一个值计算序列中的当前值。

例如，如果您集成一个功能。每个新步骤都是前一个步骤，vt += dvdt 或 vt =integrat_step(dvdt, t_prev, t_prev+dt);。

Answer 10

在非参数贝叶斯方法中，有一个 Metropolis-Hastings 步骤（每个观察）决定对新的或现有的聚类进行采样。如果必须对现有集群进行采样，则需要使用不同的权重来完成。这些加权似然在以下示例代码中进行模拟。

#include <random>                                                                                                       
#include <iostream>                                                                                                     
#include <algorithm>                                                                                                    

int main() {                                                                                                            

    std::default_random_engine generator(std::random_device{}());                                                       
    std::uniform_real_distribution<double> distribution(0.0,1.0);                                                       

    int K = 8;                                                                                                          

    std::vector<double> weighted_likelihood(K);                                                                         
    for (int i = 0; i < K; ++i) {                                                                                       
        weighted_likelihood[i] = i*10;                                                                                  
    }                                                                                                                   
    std::cout << "Weighted likelihood: ";                                                                               
    for (auto i: weighted_likelihood) std::cout << i << ' ';                                                            
    std::cout << std::endl;                                                                                             

    std::vector<double> cumsum_likelihood(K);                                                                           
    std::partial_sum(weighted_likelihood.begin(), weighted_likelihood.end(), cumsum_likelihood.begin());                

    std::cout << "Cumulative sum of weighted likelihood: ";                                                             
    for (auto i: cumsum_likelihood) std::cout << i << ' ';                                                              
    std::cout << std::endl;                                                                                             

    std::vector<int> frequency(K);                                                                                      

    int N = 280000;                                                                                                     
    for (int i = 0; i < N; ++i) {                                                                                       
        double pick = distribution(generator) * cumsum_likelihood.back();                                               

        auto lower = std::lower_bound(cumsum_likelihood.begin(), cumsum_likelihood.end(), pick);                        
        int index = std::distance(cumsum_likelihood.begin(), lower);                                                    
        frequency[index]++;                                                                                             
    }                                                                                                                   

    std::cout << "Frequencies: ";                                                                                       
    for (auto i: frequency) std::cout << i << ' ';                                                                      
    std::cout << std::endl;                                                                                             

}

请注意，这与 https://stackoverflow.com/users/13005/steve-jessop。添加它是为了提供有关特定情况的更多上下文（非参数贝叶斯方法，例如 Neal 使用 Dirichlet 过程作为先前的算法）以及结合使用 partial_sum 和 lower_bound 的实际代码。

Answer 11

我用它来减少我的玩具 lambda 演算解释器中简单标记-清除垃圾收集器的内存使用量。

GC 池是大小相同的对象的数组。目标是消除未链接到其他对象的对象，并将剩余对象压缩到数组的开头。由于对象是在内存中移动的，因此每个链接都需要更新。这需要一个对象重映射表。

partial_sum 允许以压缩格式存储表（每个对象仅一位），直到扫描完成并释放内存为止。由于对象很小，因此可以显着减少内存使用。

1. 递归地标记使用过的对象并填充布尔数组。
2. 使用 remove_if 将标记的对象压缩到池的开头。
3. 对布尔值使用 partial_sum 来生成新池中的指针/索引表。
   • 这是有效的，因为第 N 个标记的对象在数组中有 N 个前面的 1，并获取池索引 N。
4. 再次扫描池并使用重映射表替换每个链接。

将重映射表放在刚刚释放的、仍然很热的内存中对数据缓存特别友好。