预分配或更改向量的大小

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

两种方法各有利弊。

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

第二种的优点是我们预先分配我们需要的所有内存。第二个缺点是我们存储的数量远远超出了我们的需要。

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

提前干杯。

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