STL的“ partial_sum”有什么实际用途？ [英] What are practical uses for STL's 'partial_sum'?

问题描述

partial_sum 算法的实际用途是什么/在哪里？ noreferrer> STL ？

What/where are the practical uses of the partial_sum algorithm in STL?

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

What are some other interesting/non-trivial examples or use-cases?

推荐答案

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

I used it to reduce memory usage of a simple mark-sweep garbage collector in my toy lambda calculus interpreter.

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

The GC pool is an array of objects of identical size. The goal is to eliminate objects that aren't linked to other objects, and condense the remaining objects into the beginning of the array. Since the objects are moved in memory, each link needs to be updated. This necessitates an object remapping table.

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

partial_sum allows the table to be stored in compressed format (as little as one bit per object) until the sweep is complete and memory has been freed. Since the objects are small, this significantly reduces memory use.

1. 递归标记使用过的对象并填充布尔数组。


2. 使用 remove_if 将标记的对象压缩到池的开头。


3. 使用布尔值上的partial_sum ，以生成指向新池的指针/索引表。
   
   
   
   • 之所以有效，是因为第N个标记对象的数组中N的前1个N，并且获得池索引N。
   
   

1. Recursively mark used objects and populate the Boolean array.
2. Use remove_if to condense the marked objects to the beginning of the pool.
3. Use partial_sum over the Boolean values to generate a table of pointers/indexes into the new pool.
   • This works because the Nth marked object has N preceding 1's in the array and acquires pool index N.

对数据特别友好缓存以将重映射表放到刚刚释放的内存中，因此仍然很热。

It's especially friendly to the data cache to put the remap table in the just-freed, thus still hot, memory.

这篇关于STL的“ partial_sum”有什么实际用途？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！