我运行了以下基准测试:
bench=function(...,n=1,r=3){
a=match.call(expand.dots=F)$...
t=matrix(ncol=length(a),nrow=n)
for(i in 1:length(a))for(j in 1:n){t1=Sys.time();eval(a[[i]],parent.frame());t[j,i]=Sys.time()-t1}
o=t(apply(t,2,function(x)c(median(x),min(x),max(x),mean(x))))
round(1e3*`dimnames<-`(o,list(names(a),c("median","min","max","mean"))),r)
}
ns=10^c(3:7)
m=sapply(ns,function(n)bench(n=5,
`vector at length + 1`={l=c();for(i in 1:n)l[length(l)+1]=i},
`vector at index`={l=c();for(i in 1:n)l[i]=i},
`vector at index, initialize with type`={l=integer();for(i in 1:n)l[i]=i},
`vector at index, initialize with length`={l=vector(length=n);for(i in 1:n)l[i]=i},
`vector at index, initialize with type and length`={l=integer(n);for(i in 1:n)l[i]=i},
`list at length + 1`={l=list();for(i in 1:n)l[[length(l)+1]]=i},
`list at index`={l=list();for(i in 1:n)l[[i]]=i},
`list at index, initialize with length`={l=vector('list',n);for(i in 1:n)l[[i]]=i},
`list at index, initialize with double length, remove null`={l=vector("list",2*n);for(i in 1:n)l[[i]]=i;l=head(l,i)},
`list at index, double when full, get length from variable`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==len){len=len*2;length(l)=len}};l=head(l,i)},
`list at index, double when full, check length inside loop`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==length(l)){length(l)=i*2}};l=head(l,i)},
`nested lists`={l=list();for(i in 1:n)l=list(l,i)},
`nested lists with unlist`={if(n<=1e5){l=list();for(i in 1:n)l=list(l,i);o=unlist(l)}},
`nested lists with manual unlist`={l=list();for(i in 1:n)l=list(l,i);o=integer(n);for(i in 1:n){o[n-i+1]=l[[2]];l=l[[1]]}},
`JanKanis better_env_as_container`={env=new.env(hash=T,parent=globalenv());for(i in 1:n)env[[as.character(i)]]=i},
`JanKanis inlineLinkedList`={a=list();for(i in 1:n)a=list(a,i);b=vector('list',n);head=a;for(i in n:1){b[[i]]=head[[2]];head=head[[1]]}},
`JanKanis inlineExpandingList`={l=vector('list',10);cap=10;len=0;for(i in 1:n){if(len==cap){l=c(l,vector('list',cap));cap=cap*2};len=len+1;l[[len]]=i};l[1:len]},
`c`={if(n<=1e5){l=c();for(i in 1:n)l=c(l,i)}},
`append vector`={if(n<=1e5){l=integer(n);for(i in 1:n)l=append(l,i)}},
`append list`={if(n<=1e9){l=list();for(i in 1:n)l=append(l,i)}}
)[,1])
m[rownames(m)%in%c("nested lists with unlist","c","append vector","append list"),4:5]=NA
m2=apply(m,2,function(x)formatC(x,max(0,2-ceiling(log10(min(x,na.rm=T)))),format="f"))
m3=apply(rbind(paste0("1e",log10(ns)),m2),2,function(x)formatC(x,max(nchar(x)),format="s"))
writeLines(apply(cbind(m3,c("",rownames(m))),1,paste,collapse=" "))
输出:
1e3 1e4 1e5 1e6 1e7
2.35 24.5 245 2292 27146 vector at length + 1
0.61 5.9 60 590 7360 vector at index
0.61 5.9 64 587 7132 vector at index, initialize with type
0.56 5.6 54 523 6418 vector at index, initialize with length
0.54 5.5 55 522 6371 vector at index, initialize with type and length
2.65 28.8 299 3955 48204 list at length + 1
0.93 9.2 96 1605 13480 list at index
0.58 5.6 57 707 8461 list at index, initialize with length
0.62 5.8 59 739 9413 list at index, initialize with double length, remove null
0.88 8.4 81 962 11872 list at index, double when full, get length from variable
0.96 9.5 92 1264 15813 list at index, double when full, check length inside loop
0.21 1.9 22 426 3826 nested lists
0.25 2.4 29 NA NA nested lists with unlist
2.85 27.5 295 3065 31427 nested lists with manual unlist
1.65 20.2 293 6505 8835 JanKanis better_env_as_container
1.11 10.1 110 1534 27119 JanKanis inlineLinkedList
2.66 26.3 266 3592 47120 JanKanis inlineExpandingList
1.22 118.6 15466 NA NA c
3.64 512.0 45167 NA NA append vector
6.35 664.8 71399 NA NA append list
上表显示的是每种方法的中位数时间,而不是平均时间,因为偶尔会出现单次运行时间比典型运行时间长得多的情况,这会扭曲平均运行时间。但是在第一次运行后,没有任何一种方法变得更快,因此每种方法的最小时间和中位数时间通常是相似的。
方法“按索引访问向量”(
l=c();for(i in 1:n)l[i]=i
)比“在向量末尾添加元素”(
l=c();for(i in 1:n)l[length(l)]=i
)快约5倍,因为获取向量长度比向向量添加元素需要更长的时间。当我使用预定长度初始化向量时,代码速度提高了约20%,但使用特定类型进行初始化并没有什么区别,因为类型只需要在向量添加第一个项目时更改一次。对于列表,当您比较“按索引访问列表”和“使用预定长度初始化的按索引访问列表”方法时,使用预定长度初始化列表会随着列表长度的增加而产生更大的差异,因为它使代码在长度为1e6时快约两倍,在长度为1e7时快约3倍。
“索引列表”方法(l=list();for(i in 1:n)l[[i]]=i
)比“长度+1的列表”方法(l=list();for(i in 1:n)l[[length(l)+1]]=i
)快3-4倍。
JanKanis的链表和扩展列表方法比“索引列表”慢,但比“长度+1的列表”快。链表比扩展列表更快。
有些人声称append
函数比c
函数更快,但在我的基准测试中,append
比c
慢3-4倍。
在上面的表格中,长度为1e6和1e7的三种方法缺失:“c”,“追加向量”和“追加列表”,因为它们具有二次时间复杂度,“嵌套列表与unlist”由于导致堆栈溢出而缺失。
"嵌套列表"选项是最快的,但它不包括扁平化列表所需的时间。当我使用unlist
函数来扁平化嵌套列表时,在列表长度约为1.26e5或更高时,我会遇到堆栈溢出,因为unlist
函数默认情况下会递归调用自身:n=1.26e5;l=list();for(i in 1:n)l=list(l,list(i));u=unlist(l)
。而当我重复调用unlist(recursive=F)
时,即使对于仅有10,000个项的列表也需要大约4秒钟才能运行:for(i in 1:n)l=unlist(l,recursive=F)
。但是,当我手动对列表进行解析时,即使对于一百万个项的列表,也只需约0.3秒钟就可以运行:o=integer(n);for(i in 1:n){o[n-i+1]=l[[2]];l=l[[1]]}
。
如果您事先不知道要附加多少项到列表中,但是知道最大项目数量,则可以尝试在最大长度处初始化列表,然后稍后删除NULL值。另一种方法是每次列表变满时将列表大小加倍(如果您对列表的长度有一个变量,并且另一个变量用于添加到列表中的项目数,则可以更快地完成此操作,因此您不必在循环每次迭代时检查列表对象的长度):
ns=10^c(2:7)
m=sapply(ns,function(n)bench(n=5,
`list at index`={l=list();for(i in 1:n)l[[i]]=i},
`list at length + 1`={l=list();for(i in 1:n)l[[length(l)+1]]=i},
`list at index, initialize with length`={l=vector("list",n);for(i in 1:n)l[[i]]=i},
`list at index, initialize with double length, remove null`={l=vector("list",2*n);for(i in 1:n)l[[i]]=i;l=head(l,i)},
`list at index, initialize with length 1e7, remove null`={l=vector("list",1e7);for(i in 1:n)l[[i]]=i;l=head(l,i)},
`list at index, initialize with length 1e8, remove null`={l=vector("list",1e8);for(i in 1:n)l[[i]]=i;l=head(l,i)},
`list at index, double when full, get length from variable`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==len){len=len*2;length(l)=len}};l=head(l,i)},
`list at index, double when full, check length inside loop`={len=1;l=list();for(i in 1:n){l[[i]]=i;if(i==length(l)){length(l)=i*2}};l=head(l,i)}
)[,1])
m2=apply(m,2,function(x)formatC(x,max(0,2-ceiling(log10(min(x)))),format="f"))
m3=apply(rbind(paste0("1e",log10(ns)),m2),2,function(x)formatC(x,max(nchar(x)),format="s"))
writeLines(apply(cbind(m3,c("",rownames(m))),1,paste,collapse=" "))
输出:
1e4 1e5 1e6 1e7
9.3 102 1225 13250 list at index
27.4 315 3820 45920 list at length + 1
5.7 58 726 7548 list at index, initialize with length
5.8 60 748 8057 list at index, initialize with double length, remove null
33.4 88 902 7684 list at index, initialize with length 1e7, remove null
333.2 393 2691 12245 list at index, initialize with length 1e8, remove null
8.6 83 1032 10611 list at index, double when full, get length from variable
9.3 96 1280 14319 list at index, double when full, check length inside loop