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

Question

partial_sum算法在STL中有哪些实际应用和使用场景？

还有哪些有趣或非平凡的示例或用例？

- Matthieu N.

Answer 1

我将其用于简单标记-清除垃圾收集器在我的玩具λ演算解释器中减少内存使用。

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

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

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

将重新映射表放入刚释放的热内存中，对数据缓存尤其友好。

- Potatoswatter

---

当我想要构建离散概率分布的累积分布函数时，我会使用partial_sum。 - Alexandre C.

partial_sum 也被称为“扫描”。Matlab 中的名称是“cumsum”，表示累积和。 - Tyson Hilmer

这个回答似乎是关于此主题最有趣的。但是，真的很难理解你到底做了什么，以及partial_sum如何帮助你。所以，如果你能发一些代码来使事情容易理解就好了。 - Nawaz

Answer 2

需要注意的是，部分和是撤销相邻差异的运算，就像减法撤销加法一样。或者更好的比喻是，如果你还记得微积分，微分是撤销积分的运算。更好的比喻是因为相邻差异本质上就是微分，而部分和则是积分。

假设你有一个汽车模拟器，在每个时间步长中需要知道位置、速度和加速度。你只需要存储其中一个值，因为你可以计算出另外两个值。比如说你存储了每个时间步长的位置，你可以通过取位置的相邻差分来得到速度，通过速度的相邻差分来得到加速度。或者，如果你存储了加速度，你可以对其进行部分和运算来得到速度，对速度进行部分和运算来得到位置。

部分和是那种大多数人不太经常使用但在找到合适的情境时非常有用的函数，类似于微积分。

- Bowie Owens

Answer 3

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

但那段代码不是用 C++ 写的，所以我自己做了部分求和。

- Steve Jessop

---

从精度的角度来看，实际上在感兴趣的点评估概率密度函数比你尝试做的更好。但这仍然是一个很好的建议。 - Matthieu N.

@sonicoder：抱歉，我不明白你的意思。数组就是函数，这就是离散分布与连续分布的区别。没有更加精确的问题。 - Steve Jessop

抱歉，我之前想得有点偏了，脑子里一直在想着连续的事情。 - Matthieu N.

这是一个最小可运行的示例：http://stackoverflow.com/a/42332864/895245 - Ciro Santilli OurBigBook.com

Answer 4

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

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

- James McNellis

---

很高兴告诉你，iota 在 C++0x 中已经“复活”了。 - Steve Jessop

这些例子更像是在sgi stl和cpp-ref页面上找到的琐碎例子，但还是不错的尝试。 - Matthieu N.

@sonicoder：嗯，我在回答中提到的第一个例子是我使用partial_sum的唯一情况。它肯定不像Potatoswatter的回答那样令人兴奋。 - James McNellis

这很像我的答案。你的序列总是增加1；而我的有时会增加0。我对这里的回应感到非常惊讶，我应该发布那个程序...等我有时间的时候... - Potatoswatter

Answer 5

个人使用案例：轮盘赌选择

我正在使用partial_sum来实现轮盘赌选择算法（链接：link text）。该算法从一个给定的容器中随机选择元素，其概率与事先线性给定的某个值成正比。

由于我选择的所有元素都带有不一定归一化的值，因此我使用partial_sum算法构建了类似于“轮盘”的东西，因为我要对所有元素求和。然后我在这个范围内选择一个随机变量（最后一个partial_sum是所有元素的总和），并使用stl::lower_bound搜索“轮盘”，找到我的随机搜索落在哪里。lower_bound算法返回的元素就是被选择的元素。

除了使用partial_sum可以获得清晰表达的代码之外，我还可以在使用GCC并行模式进行实验时获得一些速度优势，其中包括某些算法的并行版本之一，即partial_sum（链接：link text）。

我知道的另一个用途：并行处理中最重要的算法基元之一（但可能与STL有些远离）

如果您对使用partial_sum（在这种情况下，可能更多地使用同义词“扫描”或“prefix_sum”）进行优化的算法感兴趣，则可以去并行算法社区了解更多信息。他们一直需要它。如果没有使用它，您将无法找到基于快速排序或归并排序的并行排序算法。这个操作是最重要的并行原语之一，通常用于计算动态算法中的偏移量。考虑快速排序中的分区步骤，它被分成并送入并行线程。在计算之前，您不知道每个分区槽中的元素数量。因此，您需要为所有线程提供某些偏移量以备后续访问。

也许您会在现在炙手可热的GPU处理中找到更多信息。有关Nvidia的CUDA和扫描基元以及一些应用示例的简短文章，您可以在第39章：使用CUDA进行并行前缀求和（扫描）中找到。

- sascha

Answer 6

个人使用案例：从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

- user1641854

Answer 7

你可以构建一个“移动总和”（移动平均的前身）：

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);

- chrisaycock

---

在 partial_sum 之前进行移位和减法运算可以减少溢出的可能性。 - Potatoswatter

此外，考虑将您的moving_sum函数参数改为迭代器，而不是向量。 - Björn Pollex

什么是“移动总和”？ - Nawaz

Answer 8

你知道吗，我有一次实际上使用了 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循环的情况，只是我们添加相邻的数字以避免太多的工作。这个想法是，当我们可以添加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

这样可以为我们提供从index=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<TYPE>(),data[i-1]))来实现。

显然是O(N^2)。但仍然有趣和有意思...

- Mr.Ree

---

这是一个非常普遍的问题，Programming Pearls第8列提供了一个O(n)的答案，链接为http://www.cs.bell-labs.com/cm/cs/pearls/sketch08.html和http://www.cs.bell-labs.com/cm/cs/pearls/maxsum.c。 - Matthieu N.

我承认错误。我之前没有看过《编程珠玑》或这个特定的问题。我之前（错误地）被告知O(NlogN)是最好的解决方案。虽然我很想删除我的帖子，但也许让它作为一个例子更好。（对我自己和其他人都是如此...） - Mr.Ree

Answer 9

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

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

如果你想并行化这段代码，就需要了解部分和。我正在使用GNU的 partial_sum 并行版本，用于类似的操作。

- Jørgen Fogh

Answer 10

我经常使用偏和来计算序列中基于先前值的当前值，而不是简单求和。

例如，如果您要集成一个函数。每个新步骤都取决于之前的步骤，vt += dvdt 或 vt = integrate_step(dvdt, t_prev, t_prev+dt);。

- kirill_igum