预先分配或更改vector的大小

Question

我有一个需要" burn-in "的过程。这意味着I

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个值

两种方法各有利弊。

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

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

最好的方法是什么?它是否取决于我最需要关心的性能方面?最快的方法是什么?

提前干杯

编辑:大约，p通常在低几十的数量级，N可以是几千

Answer 1

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

与第一个解决方案相比，第二个解决方案应该相当快，但实际上，它可能使用大量内存，因此它应该是次优的(在RAM中写入值需要时间)。

一个更快的解决方案是使用一种叫做deque的数据结构。这样的数据结构使您能够在常量时间内删除第一个项目，并在常量时间内在末尾添加一个新值。话虽如此，它也引入了一些能够做到这一点的开销。Julia提供了这样的数据结构(尤其是队列)。

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

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

Answer 3

…只有最近生成的p值才对我有用。

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

第一种方法的缺点是每次迭代都要改变vector的长度。

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