3

第一次在这里发帖，我是初学者 - 希望我能让自己有用......

我试图找到并理解完成我所追求的工作的 ADT/概念。我猜它已经在那里了。

我有一个对象的数组/列表/树（待决定的容器），每个对象都有一个与在进程迭代中未使用的数量相关的计数。随着迭代的进行，每个对象的计数累加 1。想法是迟早我将需要任何未使用的对象正在使用的内存，因此我将删除它们以为不在 RAM 中的对象腾出空间（将有一个初始计数'0'） - 但是，如果事实证明我使用了一个仍在内存中的对象，它的计数将重置为'0'，我拍拍自己的背部，因为不必访问其内容的磁盘。

缓存？

主流程循环中将包含类似于以下内容的内容：

if (object needs to be added && (totalNumberOfObjects > someConstant))
    object with highest count deleted from RAM and the (heap??)
    newObject added with a count of '0'

if (an object already in RAM is accessed by the process)
    accessedObject count is set to '0'

for (All objects in RAM) 
    count++

我可能会大吵大闹（漫长而混乱的时间）并自己搞砸，但我认为从 word go 中学习最有效的方法会很有趣。

像堆一样的东西？

4

1 回答 1

2

您可以为此使用堆，但我认为这将是矫枉过正。听起来你不会有很多不同的计数值，并且每个计数都会有很多对象。如果这是真的，那么您只需要将对象线程化到具有相同计数的对象列表中。这些列表本身排列在一个出队中（或 C++ 坚持称之为“双端队列”）。

这里的关键是你需要增加所有对象的计数，如果可能的话，你可能希望它是 O(1)，而不是 O(N)。这是可能的：关键是每个列表的标题还包含其计数与下一个较小计数的差异。具有最小计数的列表的标题包含从 0 开始的增量，这是最小的计数。要增加所有对象的计数，您只需将该单个数字增加一即可。

要将对象的计数设置为 0，请从其列表中删除该对象（这意味着您始终需要通过其列表迭代器来引用对象，或者您需要实现自己的侵入式链表），然后 (1) 将其添加到底部列表，如果该列表的计数为 0，或者 (2) 创建一个计数为 0 的新底部列表，仅包含该对象。

创建新对象的过程是相同的，不同之处在于您不必将其从当前列表中取消链接。

要从内存中逐出对象，请选择顶部列表（即计数最多的列表）开头的对象。如果该列表为空，则将其从出队中弹出。如果需要更多内存，可以重复此操作。

所以所有操作，包括“增加所有计数”，都是 O(1)。不幸的是，存储开销是每个对象两个指针，加上每个唯一计数的两个指针和一个整数（在最坏的情况下，这与对象的数量相同，但在实践中可能要少得多）。由于很难想象任何其他算法使用少于一个指针加上每个对象的计数，这可能甚至不是时空权衡；额外的空间需求是最小的。

于 2012-12-07T05:53:31.567 回答