为什么一个循环的执行时间是不成正比的循环

Question

我写了这个“坏”作用的大小（volontary慢）来构建载体和测试执行时间：

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)）时，都必须在内存中为新对象分配一个新位置。这涉及分配一组新内存，并将旧对象和新部分复制到新分配的空间中。当物体变大时，这种操作变得越来越昂贵。这解释了为什么时间不会线性增长但呈指数增长：分配 - 复制步骤在新分配空间的大小上不是线性的，因此运行时间也与循环的大小不成线性关系。