r - 为什么循环的执行时间与循环的大小不成正比

Question

我写了这个“坏”函数(自愿慢)来构建向量并测试执行时间:

f <- function(n){
  vec <- c()
  for (i in 1:n) {
    vec <- c(vec, i)
  }
}

我认为如果我将循环的大小乘以 10，那么函数的执行时间会按比例增加。但是我们可以看到执行时间完全不成比例，甚至非常优越:

> system.time(f(1e+04))
utilisateur     système      écoulé 
0.14        0.00        0.14 
> system.time(f(1e+05))
utilisateur     système      écoulé 
13.35        0.00       13.49 
> system.time(f(1e+06))

Timing stopped at: 1322.7 0.29 1338.59

也许这是一个基本的计算概念，但我想知道为什么这个循环的执行时间(但我认为这对于一般的循环来说是一样的)与循环的大小不成正比？

谢谢

Answer 1

这是由增量增长对象引起的。每次增加对象的大小时 ( vec <- c(vec, i) ) 都必须在内存中为新对象分配一个新位置。这涉及分配一组新的内存，并将旧对象加上新的部分复制到新分配的空间中。当对象增长时，这个操作变得越来越昂贵。这解释了为什么时间不是线性增长而是指数增长:分配复制步骤与新分配空间的大小不是线性关系，因此运行时间也与循环大小不是线性关系。