我读过可以使用加倍数组来实现缓存遗忘堆栈。
有人可以解释一下分析如何使每次推送和弹出都具有1/B摊销的 I/O 复杂性吗？
问问题
370 次
2 回答
3
堆栈支持以下操作：
- 推
- 流行音乐
虽然这两个操作可以使用 O(1) 推送和 O(1) 弹出的单链表执行，但它存在缓存问题，因为存储的元素分散在内存中。对于这种方法，我们推送到列表的前面，然后从列表的前面弹出。
我们可以使用动态数组作为我们的数据结构，并推送和弹出到数组的末尾。（我们将跟踪数组中最后填充的位置作为我们的索引，并在我们推送和弹出元素时对其进行修改）。
弹出将是 O(1)，因为我们不需要调整数组的大小。
如果数组末尾有多余的空间，则推送将是 O(1)。
问题是当我们尝试推动一个元素但没有空间时。在这种情况下，我们创建一个两倍大 (2n) 的新数组，然后复制 n 个元素中的每一个，然后推送元素。
假设我们有一个数组，它的大小已经为 n，但开始时是空的。
如果我将 n+1 个元素推送到数组上，那么前 n 个元素需要 O(1)*n = O(n) 时间。
+1 元素需要 O(n) 时间，因为它必须构建数组的新副本。
所以将 n+1 个元素推入数组是 O(2n)，但我们可以去掉这个常数，只说它是 O(n) 或元素数量呈线性关系。
因此，虽然推送单个元素可能比恒定操作花费更长的时间，但推送大量元素需要线性量的工作。
动态数组是缓存友好的，因为所有元素都尽可能彼此靠近，因此多个元素应该位于相同的缓存行中。
于 2012-08-27T04:31:45.923 回答
1
我认为标准堆栈是缓存无视的。您仅在 1/B 的访问中出错，因为任何推送/弹出序列都必须是相邻的地址，因此您只能在每 B 次操作中命中一个新的高速缓存行。（注意：参数需要至少 2 个缓存行来防止抖动。）
于 2012-08-27T03:19:14.730 回答