logo标签列表

如何在R语言中以平摊常数时间O(1)将一个对象添加到列表中？

rperformancelistappendbig-o
257

如果我有一个 R 的列表mylist，你可以这样将一个项目obj添加到它中：

mylist[[length(mylist)+1]] <- obj

但肯定有更紧凑的方法。当我刚开始学习R时，我尝试写 lappend()，像这样：

lappend <- function(lst, obj) {
    lst[[length(lst)+1]] <- obj
    return(lst)
}

但是由于R的按名称调用语义（lst在调用时实际上被复制），因此这显然行不通，所以对lst的更改在lappend()作用域之外是不可见的。我知道你可以在R函数中进行环境操作，以达到超出函数范围并改变调用环境的目的，但这似乎是用大锤写一个简单的附加函数。

有人能建议一种更美观的方法吗？如果它适用于向量和列表，则奖励得分。

7
R有不可变数据的特性，这种特性通常在函数式语言中出现。我不得不说，你只能接受它。它既有优点也有缺点。 - Dan
8
不是按值传递，否则这不会成为一个问题。R实际上使用了按需调用的方式。（参考网页：http://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need） - Nick
4
一个好主意是预先分配你的向量/列表：N = 100 mylist = vector('list', N) for (i in 1:N) {#mylist[[i]] = ...} 避免在R中“增长”对象。 - Fernando
我在这里意外地找到了答案，https://dev59.com/-2Qn5IYBdhLWcg3wJ0e5?lq=1 实现起来很难，但算法却很简单！ - KH Kim
@Fernando：好的，但这并不普适，它只适用于您可以预先知道确切最终长度的情况下（或者如果您可以使用上限来解决问题）。 - smci
显示剩余3条评论
17个回答
2

我认为你想要做的是将参数通过引用（指针）传递给函数——创建一个新的环境（这些通过引用传递给函数）并将列表添加到其中：

listptr=new.env(parent=globalenv())
listptr$list=mylist

#Then the function is modified as:
lPtrAppend <- function(lstptr, obj) {
    lstptr$list[[length(lstptr$list)+1]] <- obj
}

现在您只是修改现有的列表（而不是创建一个新的）。
1
这似乎又具有二次时间复杂度。问题显然在于列表/向量的调整大小没有按照大多数语言中通常的方式实现。 - eold
是的 - 看起来在末尾添加很慢 - 可能是因为列表是递归的，而R最擅长向量操作而不是循环类型操作。最好做： - DavidM
1
system.time(for(i in c(1:10000) mylist[i]=i) (a few seconds), or better yet do it all in one operation: system.time(mylist=list(1:100000)) (less than a second), then modifying that preallocated list with the for loop will also be faster. 在编程中，使用system.time函数可以测量代码的执行时间。如果您需要将数字1到10000存储在列表中，使用for循环逐个添加元素可能需要几秒钟的时间。更好的方法是一次性使用system.time函数和list函数将数字1到100000存储在列表中，这样只需要不到一秒钟的时间。此外，使用预先分配的列表并通过for循环修改它也会更快。 - DavidM
2
这是一种简单的向 R List 添加项目的方法：
# create an empty list:
small_list = list()

# now put some objects in it:
small_list$k1 = "v1"
small_list$k2 = "v2"
small_list$k3 = 1:10

# retrieve them the same way:
small_list$k1
# returns "v1"

# "index" notation works as well:
small_list["k2"]

或者通过编程方式实现：
kx = paste(LETTERS[1:5], 1:5, sep="")
vx = runif(5)
lx = list()
cn = 1

for (itm in kx) { lx[itm] = vx[cn]; cn = cn + 1 }

print(length(lx))
# returns 5
这并不是真正的追加。如果我有100个对象，我想以编程方式将它们追加到列表中怎么办？R有一个append()函数，但它实际上是一个连接函数，只能用于向量。 - Nick
append()适用于向量和列表，并且它是真正的附加（基本上与连接相同，所以我不明白你的问题在哪里）。 - hadley
9
追加函数应该改变现有对象，而不是创建新对象。真正的追加操作不会具有O(N^2) 的行为。 - Nick
1

还有来自rlist的list.append（文档链接）

require(rlist)
LL <- list(a="Tom", b="Dick")
list.append(LL,d="Pam",f=c("Joe","Ann"))

它非常简单而高效。

1
看起来不像是 R 语言... 是 Python 吗？ - JD Long
1
我进行了一次编辑并尝试了一下：它非常慢。最好使用c()或list方法。两者都要快得多。 - 5th
1
看一下 rlist::list.append() 的代码，它本质上是 base::c() 的一个包装器。 - nbenn
0
> LL<-list(1:4)

> LL

[[1]]
[1] 1 2 3 4

> LL<-list(c(unlist(LL),5:9))

> LL

[[1]]
 [1] 1 2 3 4 5 6 7 8 9
2
我认为这不是楼主想要的追加方式。 - joran
这不是在列表中添加元素。这里是增加整数向量的元素，该向量是列表的唯一元素。该列表仅有一个元素，即整数向量。 - Sergio
0

为了验证，我运行了@Cron提供的基准代码。除了在更新的i7处理器上运行更快之外，还有一个主要区别：现在by_index的性能几乎与list_一样好：

Unit: milliseconds
              expr        min         lq       mean     median         uq
    env_with_list_ 167.882406 175.969269 185.966143 181.817187 185.933887
                c_ 485.524870 501.049836 516.781689 518.637468 537.355953
             list_   6.155772   6.258487   6.544207   6.269045   6.290925
          by_index   9.290577   9.630283   9.881103   9.672359  10.219533
           append_ 505.046634 543.319857 542.112303 551.001787 553.030110
 env_as_container_ 153.297375 154.880337 156.198009 156.068736 156.800135

以下是基准代码，直接从@Cron的答案中复制而来（以防他稍后更改内容）：

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj}

microbenchmark(times = 5,
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = {
            a <- list(0)
            for(i in 1:n) {a <- append(a, i)}
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)}
            listptr
        }
)
请查看我上面的评论。list_ 不提供与其他内容相同的结果。因此，这种比较是无效的！ - David Bellot
0

这是一个非常有趣的问题，我希望我的想法能为解决它提供一种方法。这种方法可以提供一个平面列表而不需要索引，但它确实有list和unlist来避免嵌套结构。我不确定速度如何，因为我不知道如何对其进行基准测试。

a_list<-list()
for(i in 1:3){
  a_list<-list(unlist(list(unlist(a_list,recursive = FALSE),list(rnorm(2))),recursive = FALSE))
}
a_list

[[1]]
[[1]][[1]]
[1] -0.8098202  1.1035517

[[1]][[2]]
[1] 0.6804520 0.4664394

[[1]][[3]]
[1] 0.15592354 0.07424637
我想要补充的是它确实给出了一个两层嵌套列表，但仅此而已。列表和取消列表的工作方式对我来说并不是很清楚，但这是通过测试代码得出的结果。 - xappppp
0
我运行了以下基准测试：
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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接