Nic*_*ick 235 performance big-o r list append
如果我有一些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函数中做环境黑客攻击到达外部你的函数范围和mutate调用环境,但这似乎是一个大锤子写一个简单的追加函数.
任何人都可以建议一个更美丽的方式吗？奖励点,如果它适用于矢量和列表.
Dir*_*tel 252
如果它是一个字符串列表,只需使用该c()函数:
R> LL <- list(a="tom", b="dick")
R> c(LL, c="harry")
$a
[1] "tom"
$b
[1] "dick"
$c
[1] "harry"
R> class(LL)
[1] "list"
R>
这对矢量也有效,所以我得到奖励积分吗？
编辑(2015年2月1日):这篇文章即将迎来五岁生日.某些读者不断重复任何缺点,所以一定要看下面的一些评论.list类型的一个建议:
newlist <- list(oldlist, list(someobj))
一般来说,R类型可能很难为所有类型和用途提供一个而且只有一个成语.
pho*_*ger 93
OP(在2012年4月更新的问题修订版中)有兴趣知道是否有一种方法可以在分摊的常量时间内添加到列表中,例如可以使用C++ vector<>容器来完成.到目前为止,最佳答案(s？)仅显示了给定固定大小问题的各种解决方案的相对执行时间,但没有直接解决任何各种解决方案的算法效率.许多答案下面的评论讨论了一些解决方案的算法效率,但到目前为止(截至2015年4月),它们得出了错误的结论.
随着问题规模的增长,算法效率可以在时间(执行时间)或空间(消耗的内存量)中捕获增长特征.针对固定大小问题对各种解决方案进行性能测试并不能解决各种解决方案的增长率问题.OP有兴趣知道是否有一种方法可以在"摊销的恒定时间"中将对象附加到R列表.那是什么意思？为了解释,首先让我描述"恒定时间":
常数或O(1)增长:
如果要完成既定任务所需的时间保持不变的问题的规模增加一倍,那么我们就说该算法具有一定时间的增长,还是在"大O"符号表示,表现出O(1)时间的增长.当OP表示"摊销"恒定时间时,他只是意味着"从长远来看"......即,如果执行单个操作偶尔需要比正常时间长得多(例如,如果预分配缓冲区耗尽并且偶尔需要调整大小缓冲区大小),只要长期平均性能是恒定时间,我们仍称它为O(1).
为了比较,我还将描述"线性时间"和"二次时间":
线性或O(n)增长:
如果执行给定任务所需的时间加倍,因为问题的大小加倍,那么我们说算法表现出线性时间或O(n)增长.
二次或O(n 2)增长:
如果执行给定任务所需的时间增加了问题大小的平方,那么我们称算法表现出二次时间或O(n 2)增长.
还有许多其他效率类算法; 我按照维基百科的文章进行进一步讨论.
我感谢@CronAcronis的回答,因为我是R的新手,很高兴有一个完整构造的代码块来对本页面提供的各种解决方案进行性能分析.我借用他的代码进行分析,我在下面复制(包装在一个函数中):
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}
runBenchmark <- function(n) {
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
}
)
}
@CronAcronis发布的结果肯定似乎表明该a <- list(a, list(i))方法是最快的,至少对于10000的问题大小,但单个问题大小的结果不能解决解决方案的增长.为此,我们需要运行至少两个具有不同问题大小的分析测试:
> runBenchmark(2e+3)
Unit: microseconds
expr min lq mean median uq max neval
env_with_list_ 8712.146 9138.250 10185.533 10257.678 10761.33 12058.264 5
c_ 13407.657 13413.739 13620.976 13605.696 13790.05 13887.738 5
list_ 854.110 913.407 1064.463 914.167 1301.50 1339.132 5
by_index 11656.866 11705.140 12182.104 11997.446 12741.70 12809.363 5
append_ 15986.712 16817.635 17409.391 17458.502 17480.55 19303.560 5
env_as_container_ 19777.559 20401.702 20589.856 20606.961 20939.56 21223.502 5
> runBenchmark(2e+4)
Unit: milliseconds
expr min lq mean median uq max neval
env_with_list_ 534.955014 550.57150 550.329366 553.5288 553.955246 558.636313 5
c_ 1448.014870 1536.78905 1527.104276 1545.6449 1546.462877 1558.609706 5
list_ 8.746356 8.79615 9.162577 8.8315 9.601226 9.837655 5
by_index 953.989076 1038.47864 1037.859367 1064.3942 1065.291678 1067.143200 5
append_ 1634.151839 1682.94746 1681.948374 1689.7598 1696.198890 1706.683874 5
env_as_container_ 204.134468 205.35348 208.011525 206.4490 208.279580 215.841129 5
>
首先,关于min/lq/mean/median/uq/max值的一句话:由于我们为5次运行中的每次运行执行完全相同的任务,在理想的世界中,我们可以预期它将完全相同每次运行的时间量.但是由于我们正在测试的代码尚未加载到CPU的缓存中,因此第一次运行通常会偏向更长的时间.在第一次运行之后,我们期望时间相当一致,但是由于计时器滴答中断或与我们正在测试的代码无关的其他硬件中断,我们的代码偶尔会从缓存中逐出.通过测试代码片段5次,我们允许在第一次运行期间将代码加载到缓存中,然后为每个片段提供运行完成的机会,而不受外部事件的干扰.出于这个原因,并且因为我们每次在完全相同的输入条件下运行完全相同的代码,我们将仅考虑'min'时间足以在各种代码选项之间进行最佳比较.
请注意,我选择首先运行问题大小为2000,然后是20000,因此我的问题大小从第一次运行到第二次运行增加了10倍.
list解决方案的性能:O(1)(恒定时间)
让我们首先看看list解决方案的增长,因为我们可以立即告诉它,这是两个分析运行中最快的解决方案:在第一次运行中,执行2000次"附加"任务需要854 微秒(0.854 毫秒).在第二次运行中,执行20000次"追加"任务需要8.746毫秒.一个天真的观察者会说,"啊,list解决方案表现出O(n)增长,因为问题规模增长了10倍,执行测试所需的时间也增加了." 该分析的问题在于OP想要的是单个对象插入的增长率,而不是整个问题的增长率.知道了,很明显,list解决方案提供了OP想要的内容:在O(1)时间内将对象附加到列表的方法.
其他解决方案的性能
其他解决方案都没有达到解决方案的速度list,但无论如何都要检查它们:
大多数其他解决方案在性能上似乎都是O(n).例如,该by_index解决方案是一种非常流行的解决方案,它基于我在其他SO帖子中找到它的频率,需要11.6毫秒来附加2000个对象,并且953毫秒来追加十倍于许多对象.整个问题的时间增加了100倍,所以一个天真的观察者可能会说"啊,by_index解决方案表现出O(n 2)增长,因为问题规模增长了十倍,执行测试所需的时间增长了乘以100倍." 和以前一样,这种分析是有缺陷的,因为OP对单个对象插入的增长感兴趣.如果我们将整体时间增长除以问题的规模增长,我们发现附加对象的时间增长只增加了10倍,而不是100倍,这与问题规模的增长相匹配,因此by_index解决方案是O (N).没有列出的解决方案显示O(n 2)增长用于附加单个对象.
Jan*_*nis 40
在其他答案中,只有list方法导致O(1)追加,但它导致深度嵌套的列表结构,而不是简单的单个列表.我使用了以下数据结构,它们支持O(1)(摊销)附加,并允许将结果转换回普通列表.
expandingList <- function(capacity = 10) {
buffer <- vector('list', capacity)
length <- 0
methods <- list()
methods$double.size <- function() {
buffer <<- c(buffer, vector('list', capacity))
capacity <<- capacity * 2
}
methods$add <- function(val) {
if(length == capacity) {
methods$double.size()
}
length <<- length + 1
buffer[[length]] <<- val
}
methods$as.list <- function() {
b <- buffer[0:length]
return(b)
}
methods
}
和
linkedList <- function() {
head <- list(0)
length <- 0
methods <- list()
methods$add <- function(val) {
length <<- length + 1
head <<- list(head, val)
}
methods$as.list <- function() {
b <- vector('list', length)
h <- head
for(i in length:1) {
b[[i]] <- head[[2]]
head <- head[[1]]
}
return(b)
}
methods
}
使用它们如下:
> l <- expandingList()
> l$add("hello")
> l$add("world")
> l$add(101)
> l$as.list()
[[1]]
[1] "hello"
[[2]]
[1] "world"
[[3]]
[1] 101
这些解决方案可以扩展为完全支持与列表相关的操作的对象,但这仍然是读者的练习.
命名列表的另一个变体:
namedExpandingList <- function(capacity = 10) {
buffer <- vector('list', capacity)
names <- character(capacity)
length <- 0
methods <- list()
methods$double.size <- function() {
buffer <<- c(buffer, vector('list', capacity))
names <<- c(names, character(capacity))
capacity <<- capacity * 2
}
methods$add <- function(name, val) {
if(length == capacity) {
methods$double.size()
}
length <<- length + 1
buffer[[length]] <<- val
names[length] <<- name
}
methods$as.list <- function() {
b <- buffer[0:length]
names(b) <- names[0:length]
return(b)
}
methods
}
基准
使用@ phonetagger代码进行性能比较(基于@Cron Arconis代码).我还添加了一个better_env_as_container并改变env_as_container_了一点.原件env_as_container_坏了,实际上并没有存储所有数字.
library(microbenchmark)
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(lab)]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj}
env2list <- function(env, len) {
l <- vector('list', len)
for (i in 1:len) {
l[[i]] <- env[[as.character(i)]]
}
l
}
envl2list <- function(env, len) {
l <- vector('list', len)
for (i in 1:len) {
l[[i]] <- env[[paste(as.character(i), 'L', sep='')]]
}
l
}
runBenchmark <- function(n) {
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(hash=TRUE, parent=globalenv())
for(i in 1:n) {lPtrAppend(listptr, i, i)}
envl2list(listptr, n)
},
better_env_as_container = {
env <- new.env(hash=TRUE, parent=globalenv())
for(i in 1:n) env[[as.character(i)]] <- i
env2list(env, n)
},
linkedList = {
a <- linkedList()
for(i in 1:n) { a$add(i) }
a$as.list()
},
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]]
}
},
expandingList = {
a <- expandingList()
for(i in 1:n) { a$add(i) }
a$as.list()
},
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]
}
)
}
# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
expandingList <- function(capacity = 10) {
buffer <- vector('list', capacity)
length <- 0
methods <- list()
methods$double.size <- function() {
buffer <<- c(buffer, vector('list', capacity))
capacity <<- capacity * 2
}
methods$add <- function(val) {
if(length == capacity) {
methods$double.size()
}
length <<- length + 1
buffer[[length]] <<- val
}
methods$as.list <- function() {
b <- buffer[0:length]
return(b)
}
methods
}
linkedList <- function() {
head <- list(0)
length <- 0
methods <- list()
methods$add <- function(val) {
length <<- length + 1
head <<- list(head, val)
}
methods$as.list <- function() {
b <- vector('list', length)
h <- head
for(i in length:1) {
b[[i]] <- head[[2]]
head <- head[[1]]
}
return(b)
}
methods
}
# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
namedExpandingList <- function(capacity = 10) {
buffer <- vector('list', capacity)
names <- character(capacity)
length <- 0
methods <- list()
methods$double.size <- function() {
buffer <<- c(buffer, vector('list', capacity))
names <<- c(names, character(capacity))
capacity <<- capacity * 2
}
methods$add <- function(name, val) {
if(length == capacity) {
methods$double.size()
}
length <<- length + 1
buffer[[length]] <<- val
names[length] <<- name
}
methods$as.list <- function() {
b <- buffer[0:length]
names(b) <- names[0:length]
return(b)
}
methods
}
结果:
> runBenchmark(1000)
Unit: microseconds
expr min lq mean median uq max neval
env_with_list_ 3128.291 3161.675 4466.726 3361.837 3362.885 9318.943 5
c_ 3308.130 3465.830 6687.985 8578.913 8627.802 9459.252 5
list_ 329.508 343.615 389.724 370.504 449.494 455.499 5
by_index 3076.679 3256.588 5480.571 3395.919 8209.738 9463.931 5
append_ 4292.321 4562.184 7911.882 10156.957 10202.773 10345.177 5
env_as_container_ 24471.511 24795.849 25541.103 25486.362 26440.591 26511.200 5
better_env_as_container 7671.338 7986.597 8118.163 8153.726 8335.659 8443.493 5
linkedList 1700.754 1755.439 1829.442 1804.746 1898.752 1987.518 5
inlineLinkedList 1109.764 1115.352 1163.751 1115.631 1206.843 1271.166 5
expandingList 1422.440 1439.970 1486.288 1519.728 1524.268 1525.036 5
inlineExpandingList 942.916 973.366 1002.461 1012.197 1017.784 1066.044 5
> runBenchmark(10000)
Unit: milliseconds
expr min lq mean median uq max neval
env_with_list_ 357.760419 360.277117 433.810432 411.144799 479.090688 560.779139 5
c_ 685.477809 734.055635 761.689936 745.957553 778.330873 864.627811 5
list_ 3.257356 3.454166 3.505653 3.524216 3.551454 3.741071 5
by_index 445.977967 454.321797 515.453906 483.313516 560.374763 633.281485 5
append_ 610.777866 629.547539 681.145751 640.936898 760.570326 763.896124 5
env_as_container_ 281.025606 290.028380 303.885130 308.594676 314.972570 324.804419 5
better_env_as_container 83.944855 86.927458 90.098644 91.335853 92.459026 95.826030 5
linkedList 19.612576 24.032285 24.229808 25.461429 25.819151 26.223597 5
inlineLinkedList 11.126970 11.768524 12.216284 12.063529 12.392199 13.730200 5
expandingList 14.735483 15.854536 15.764204 16.073485 16.075789 16.081726 5
inlineExpandingList 10.618393 11.179351 13.275107 12.391780 14.747914 17.438096 5
> runBenchmark(20000)
Unit: milliseconds
expr min lq mean median uq max neval
env_with_list_ 1723.899913 1915.003237 1921.23955 1938.734718 1951.649113 2076.910767 5
c_ 2759.769353 2768.992334 2810.40023 2820.129738 2832.350269 2870.759474 5
list_ 6.112919 6.399964 6.63974 6.453252 6.910916 7.321647 5
by_index 2163.585192 2194.892470 2292.61011 2209.889015 2436.620081 2458.063801 5
append_ 2832.504964 2872.559609 2983.17666 2992.634568 3004.625953 3213.558197 5
env_as_container_ 573.386166 588.448990 602.48829 597.645221 610.048314 642.912752 5
better_env_as_container 154.180531 175.254307 180.26689 177.027204 188.642219 206.230191 5
linkedList 38.401105 47.514506 46.61419 47.525192 48.677209 50.952958 5
inlineLinkedList 25.172429 26.326681 32.33312 34.403442 34.469930 41.293126 5
expandingList 30.776072 30.970438 34.45491 31.752790 38.062728 40.712542 5
inlineExpandingList 21.309278 22.709159 24.64656 24.290694 25.764816 29.158849 5
我添加了linkedList和expandingList两个内联版本.的inlinedLinkedList基本上是一个副本list_,但它也转换嵌套结构回一个普通的列表.除此之外,内联和非内联版本之间的差异是由于函数调用的开销.
所有变体expandingList和linkedList显示O(1)都会增加性能,基准时间与附加项目的数量成线性关系.linkedList慢于expandingList,并且函数调用开销也是可见的.因此,如果您真的需要所有速度(并希望坚持R代码),请使用内联版本expandingList.
我还看了一下R的C实现,这两种方法应该是O(1)追加任何大小,直到你的内存不足.
我也改变了env_as_container_,原始版本将存储索引"i"下的每个项目,覆盖以前附加的项目.在better_env_as_container我加入非常相似,env_as_container_但没有deparse东西.两者都表现出O(1)性能,但它们的开销比链接/扩展列表要大很多.
内存开销
在CR实现中,每个分配的对象有4个字和2个int的开销.该linkedList方法为每个附加分配一个长度为2的列表,在64位计算机上每个附加项目总共(4*8 + 4 + 4 + 2*8 =)56个字节(不包括内存分配开销,因此可能更接近64字节).该expandingList方法在每个附加项目时使用一个单词,并在向量长度加倍时使用一个副本,因此每个项目的总内存使用量最多为16个字节.由于内存全部在一个或两个对象中,因此每个对象的开销是无关紧要的.我没有深入研究env内存使用情况,但我认为它会更接近linkedList.
Ars*_*eny 17
在Lisp中我们这样做了:
> l <- c(1)
> l <- c(2, l)
> l <- c(3, l)
> l <- rev(l)
> l
[1] 1 2 3
虽然它是'缺点',而不仅仅是'c'.如果需要以empy列表开头,请使用l < - NULL.
你想要这样的东西吗？
> push <- function(l, x) {
lst <- get(l, parent.frame())
lst[length(lst)+1] <- x
assign(l, lst, envir=parent.frame())
}
> a <- list(1,2)
> push('a', 6)
> a
[[1]]
[1] 1
[[2]]
[1] 2
[[3]]
[1] 6
这不是一个非常有礼貌的功能(指定parent.frame()是有点粗鲁)但IIUYC这是你要求的.
如果您将列表变量作为带引号的字符串传递,则可以从函数中访问它,如:
push <- function(l, x) {
assign(l, append(eval(as.name(l)), x), envir=parent.frame())
}
所以:
> a <- list(1,2)
> a
[[1]]
[1] 1
[[2]]
[1] 2
> push("a", 3)
> a
[[1]]
[1] 1
[[2]]
[1] 2
[[3]]
[1] 3
>
或额外的信贷:
> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
>
小智 5
不知道为什么你不认为你的第一种方法行不通。您在 lappend 函数中有一个错误：length(list) 应该是 length(lst)。这工作正常并返回带有附加 obj 的列表。
我对这里提到的方法进行了一些小比较.
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
}
)
结果:
Unit: milliseconds
expr min lq mean median uq max neval cld
env_with_list_ 188.9023 198.7560 224.57632 223.2520 229.3854 282.5859 5 a
c_ 1275.3424 1869.1064 2022.20984 2191.7745 2283.1199 2491.7060 5 b
list_ 17.4916 18.1142 22.56752 19.8546 20.8191 36.5581 5 a
by_index 445.2970 479.9670 540.20398 576.9037 591.2366 607.6156 5 a
append_ 1140.8975 1316.3031 1794.10472 1620.1212 1855.3602 3037.8416 5 b
env_as_container_ 355.9655 360.1738 399.69186 376.8588 391.7945 513.6667 5 a