如果我有一些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函数中进行环境入侵，从而超出函数的作用域并改变调用环境，但对于编写一个简单的附加函数来说，这似乎是一个巨大的打击。
有谁能提出一个更漂亮的方法吗?如果它对向量和列表都适用，那就更好了。
当前回答
在其他答案中，只有列表方法会导致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
}
and
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_，但没有离开的东西。两者都表现出O(1)性能，但它们的开销比链接/展开列表要大得多。
内存开销
In the C R implementation there is an overhead of 4 words and 2 ints per allocated object. The linkedList approach allocates one list of length two per append, for a total of (4*8+4+4+2*8=) 56 bytes per appended item on 64-bit computers (excluding memory allocation overhead, so probably closer to 64 bytes). The expandingList approach uses one word per appended item, plus a copy when doubling the vector length, so a total memory usage of up to 16 bytes per item. Since the memory is all in one or two objects the per-object overhead is insignificant. I haven't looked deeply into the env memory usage, but I think it will be closer to linkedList.
其他回答
这是一个简单的方法来添加项目到R列表:
# 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
The OP (in the April 2012 updated revision of the question) is interested in knowing if there's a way to add to a list in amortized constant time, such as can be done, for example, with a C++ vector<> container. The best answer(s?) here so far only show the relative execution times for various solutions given a fixed-size problem, but do not address any of the various solutions' algorithmic efficiency directly. Comments below many of the answers discuss the algorithmic efficiency of some of the solutions, but in every case to date (as of April 2015) they come to the wrong conclusion.
算法效率捕获随着问题规模增长的时间(执行时间)或空间(内存消耗量)的增长特征。给定一个固定大小的问题，为各种解决方案运行性能测试并不能解决各种解决方案的增长速度。OP感兴趣的是知道是否有一种方法可以在“平摊常数时间”中将对象追加到R列表中。这是什么意思?为了解释，首先让我描述一下“常数时间”:
Constant or O(1) growth: If the time required to perform a given task remains the same as the size of the problem doubles, then we say the algorithm exhibits constant time growth, or stated in "Big O" notation, exhibits O(1) time growth. When the OP says "amortized" constant time, he simply means "in the long run"... i.e., if performing a single operation occasionally takes much longer than normal (e.g. if a preallocated buffer is exhausted and occasionally requires resizing to a larger buffer size), as long as the long-term average performance is constant time, we'll still call it O(1). For comparison, I will also describe "linear time" and "quadratic time": Linear or O(n) growth: If the time required to perform a given task doubles as the size of the problem doubles, then we say the algorithm exhibits linear time, or O(n) growth. Quadratic or O(n2) growth: If the time required to perform a given task increases by the square of the problem size, them we say the algorithm exhibits quadratic time, or O(n2) growth.
还有很多其他效率算法;我参考维基百科的文章进行进一步讨论。
我感谢@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
>
First of all, a word about the min/lq/mean/median/uq/max values: Since we are performing the exact same task for each of 5 runs, in an ideal world, we could expect that it would take exactly the same amount of time for each run. But the first run is normally biased toward longer times due to the fact that the code we are testing is not yet loaded into the CPU's cache. Following the first run, we would expect the times to be fairly consistent, but occasionally our code may be evicted from the cache due to timer tick interrupts or other hardware interrupts that are unrelated to the code we are testing. By testing the code snippets 5 times, we are allowing the code to be loaded into the cache during the first run and then giving each snippet 4 chances to run to completion without interference from outside events. For this reason, and because we are really running the exact same code under the exact same input conditions each time, we will consider only the 'min' times to be sufficient for the best comparison between the various code options.
请注意，我选择首先运行问题大小为2000，然后运行问题大小为20000，因此我的问题大小从第一次运行到第二次运行增加了10倍。
表解性能:O(1)(常数时间)
Let's first look at the growth of the list solution, since we can tell right away that it's the fastest solution in both profiling runs: In the first run, it took 854 microseconds (0.854 milliseconds) to perform 2000 "append" tasks. In the second run, it took 8.746 milliseconds to perform 20000 "append" tasks. A naïve observer would say, "Ah, the list solution exhibits O(n) growth, since as the problem size grew by a factor of ten, so did the time required to execute the test." The problem with that analysis is that what the OP wants is the growth rate of a single object insertion, not the growth rate of the overall problem. Knowing that, it's clear then that the list solution provides exactly what the OP wants: a method of appending objects to a list in O(1) time.
其他解决方案的性能
其他的解决方案都没有接近列表解决方案的速度，但无论如何，检查它们都是有信息的:
Most of the other solutions appear to be O(n) in performance. For example, the by_index solution, a very popular solution based on the frequency with which I find it in other SO posts, took 11.6 milliseconds to append 2000 objects, and 953 milliseconds to append ten times that many objects. The overall problem's time grew by a factor of 100, so a naïve observer might say "Ah, the by_index solution exhibits O(n2) growth, since as the problem size grew by a factor of ten, the time required to execute the test grew by a factor of 100." As before, this analysis is flawed, since the OP is interested in the growth of a single object insertion. If we divide the overall time growth by the problem's size growth, we find that the time growth of appending objects increased by a factor of only 10, not a factor of 100, which matches the growth of the problem size, so the by_index solution is O(n). There are no solutions listed which exhibit O(n2) growth for appending a single object.
如果你将列表变量作为一个带引号的字符串传入，你可以像这样从函数内部到达它:
push <- function(l, x) {
assign(l, append(eval(as.name(l)), x), envir=parent.frame())
}
so:
> 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
>
不知道为什么你不认为你的第一种方法是行不通的。在lappend函数中有一个错误:length(list)应该是length(lst)。这很好，并返回一个带有附加obj的列表。
为了验证，我运行了@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
}
)
