Pot*_*ter 24
我用它来减少玩具lambda演算解释器中一个简单的标记扫描垃圾收集器的内存使用量.
GC池是一个大小相同的对象数组.目标是消除未链接到其他对象的对象,并将剩余的对象压缩到数组的开头.由于对象在内存中移动,因此需要更新每个链接.这需要对象重映射表.
partial_sum允许表以压缩格式存储(每个对象只有一位),直到扫描完成并释放内存.由于对象很小,这大大减少了内存使用.
remove_if将标记的对象压缩到池的开头.partial_sum布尔值生成指向新池的指针/索引表.
它对数据缓存特别友好,可以将重映射表放在刚刚释放的内存中,因此仍然很热.
关于部分和的一点需要注意的是,它是一个操作,它可以解除相邻的差异 - 就像 - undoes +.或者更好的是,如果你记得微积分,那么差异化就会解除整合.更好,因为相邻差异本质上是差异,部分和是整合.
假设您已经模拟了汽车,并且在每个步骤中您都需要知道位置,速度和加速度.您只需存储其中一个值,因为您可以计算其他两个值.假设您在每个时间步都存储位置,您可以采用相邻的位置差来给出速度和速度的相邻差值来给出加速度.或者,如果存储加速度,则可以采用部分和来给出速度,速度的部分和给出位置.
部分总和是大多数人不会经常出现的功能之一,但在找到合适的情况时非常有用.很像微积分.
上次我(将要)使用它是将离散概率分布(p(X = k)的数组)转换为累积分布(p(X <= k)的数组).要从分布中选择一次,您可以随机选择[0-1]中的数字,然后二进制搜索到累积分布.
但是,这段代码不是用C++编写的,所以我自己做了部分求和.
您可以使用它来生成单调递增的数字序列.例如,以下生成vector包含数字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>());