预分配或更改向量大小

Question

我有这样一种情况，我需要 "烧入" 一个进程。这意味着:

1. 从 p 值开始，p 相对较小
2. 对于 n > p，使用最近生成的 p 值生成第 n 个值 (例如，从值 1 到 p 生成 p+1 的值，从值 2、p+1 生成 p+2，依此类推)
3. 重复以上步骤，直到 n = N，其中 N 较大

现在，我只需要最近生成的 p 值，因此有两种方法可以实现这一点。我可以:

• 从 p 初始值向量开始。在每次迭代中，改变向量，删除第一个元素，并用最近生成的值替换最后一个元素或
• 预先分配长度为 N 的大型数组，其中前 p 个元素是初始值。在第 n 次迭代中，改变第 n 个值以包含最近生成的值

这两种方法都有优缺点。

第一种方法的优点是我们只存储最相关的值。第一种方法的缺点是我们在每次迭代时改变向量的长度。

第二种方法的优点是我们预先分配所有需要的内存。第二种方法的缺点是我们存储了比所需更多的内容。

最好的方法是什么？这取决于我最需要关心的性能方面吗？哪个方法最快？

提前祝福您！

- user4945884

---

我没有答案，但是我相信大概了解可能的p和N值会很有用！ - Giovanni

公正的观点，已编辑！ - user4945884

Answer 1

第一种解决方案有一个巨大的缺点：从数组中移除第一个元素需要 O(n) 的时间，因为元素在内存中必须被移动。这会导致算法运行时间呈二次函数增长，是不合理的。正如@ForceBru所建议的那样，将项目进行移位也会导致这种二次运行时间（因为每次都要移动许多项目才能添加一个值）。

与第一种解决方案相比，第二种解决方案应该更快，但确实可能使用了大量内存，因此它应该是次优的（将值写入RAM需要时间）。

更快的解决方案是使用称为双端队列的数据结构。这种数据结构可以在常量时间内删除第一个项目，并在常量时间内附加新值。话虽如此，它也引入了某些开销，以便能够执行此操作。Julia提供这样的数据结构（更准确地说是队列）。

由于算法中正在处理的项目量似乎是有界的，因此可以实现一个滚动缓冲区。幸运的是，Julia也实现了这一点：请参见CircularBuffer。此解决方案应该非常简单和快速（因为要执行的操作在它上面以 O(1) 计时完成）。

- Jérôme Richard

---

很遗憾，我只能接受一个答案！而且我似乎找不到关于如何实际使用Deque或CircularBuffer的好文档，所以我将使用CircularArrays。谢谢！ - user4945884

Answer 2

对于你的用例，使用CircularArrays.jl 可能是最简单的：

julia> using CircularArrays

julia> c = CircularArray([1,2,3,4])
4-element CircularVector(::Vector{Int64}):
 1
 2
 3
 4

julia> for i in 5:10
           c[i] = i
           @show c
       end
c = [5, 2, 3, 4]
c = [5, 6, 3, 4]
c = [5, 6, 7, 4]
c = [5, 6, 7, 8]
c = [9, 6, 7, 8]
c = [9, 10, 7, 8]

如您所见，通过使用递增索引，数组将在内部进行环绕（丢弃不再需要的旧值），以此方式您可以持续使用并存储更多数据。

这样一来，您就可以在数组中始终存储最后p个值，而无需每次复制任何内容或重新分配内存。

- Bogumił Kamiński

Answer 3

“...只有最近生成的p值对我有用...”

“从一个包含p个初始值的向量开始。在每次迭代中，改变向量，删除第一个元素，并将最新生成的值替换为最后一个元素。”

“第一种方法的缺点是我们在每次迭代时都会改变向量的长度。”

“没有必要改变向量的长度。只需将其元素向左移动（覆盖第一个元素），并将新数据写入the_vector[end]即可：”

the_vector = [1,2,3,4,5,6]

function shift_and_add!(vec::AbstractVector, value)
    vec[1:end-1] .= @view vec[2:end] # shift
    vec[end] = value # replace the last value
    vec
end

@assert shift_and_add!(the_vector, 80) == [2,3,4,5,6,80]
# `the_vector` will be mutated
@assert the_vector == [2,3,4,5,6,80]

- ForceBru