预分配或更改向量的大小

Question

我有一个过程需要“老化”。这意味着我

从p值开始，p比较小
对于 n>p，使用最近生成的 p 值生成第 n 个值（例如，p+1 从值 1 到 p 生成，p+2 从值 2、p+1 等生成）
重复直到 n=N，其中 N 很大

现在，只有最近生成的 p 值对我有用，所以我有两种实现方法。我也可以

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

两种方法各有利弊。

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

第二个的优点是我们预先分配了我们需要的所有内存。第二个缺点是我们存储的比我们需要的多得多。

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

提前干杯。

编辑：大约，p一般是小十位，N可以是几千位

Answer 1

...only the most recently generated p values will be useful to me...

Start with a vector of p initial values. At each iteration, mutate the vector, removing the first element, and replacing the last element with the most recently generated value.

Cons of the first are that we are changing the length of the vector at each iteration.

无需更改向量的长度。只需将其元素向左移动（覆盖第一个元素）并将新数据写入 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]

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 值存储在数组中，而无需在每个步骤中复制任何内容或 re-allocate 内存。

Answer 3

第一个解决方案还有另一个巨大的缺点：删除数组的第一项需要 O(n) 时间，因为元素应该在内存中移动。这肯定会导致算法在 二次时间 中运行s，这是 不合理的 。按照@ForceBru 的建议移动项目也应该导致这个二次运行时间（因为移动许多项目只是为了每次增加一个值）。

与第一个相比，第二个解决方案应该相当快，但事实上，它会使用大量内存，所以它应该是 sub-optimal（在 RAM 中写入值需要时间）。

更快的解决方案是使用称为 deque. Such data structure enable you to remove the first item in constant time and append a new value at the end also in constant time. That being said, it also introduces some overhead to be able to do that. Julia provide such data structure 的数据结构（尤其是队列）。

由于 in-flight 项的数量在您的算法中似乎是有限的，您可以实施 滚动缓冲区 。幸运的是，Julia 也实现了这一点：参见 CircularBuffer。这个解决方案应该非常简单和快速（因为你想做的操作在 O(1) 时间内完成）。

预分配或更改向量的大小

Preallocate or change size of vector

memory

performance

immutability

julia