我们再来一次:将一个元素附加到R中的列表中

Question

对于在摊销的常数时间内将对象附加到R中的列表,我不满意？

> list1 <- list("foo", pi)
> bar <- list("A", "B")

我怎么能新元素追加bar到list1？显然,c()不起作用,它变平bar:

> c(list1, bar)
[[1]]
[1] "foo"

[[2]]
[1] 3.141593

[[3]]
[1] "A"

[[4]]
[1] "B"

索引作业的分配:

> list1[[length(list1)+1]] <- bar
> list1
[[1]]
[1] "foo"

[[2]]
[1] 3.141593

[[3]]
[[3]][[1]]
[1] "A"

[[3]][[2]]
[1] "B"

这种方法的效率是多少？有更优雅的方式吗？

Answer 1

在一次执行一个元素时,向列表中添加元素非常慢.看这两个例子:

我将Result变量保留在全局环境中以避免复制到评估框架并告诉R在哪里查找它.GlobalEnv$,以避免盲目搜索<<-:

Result <- list()

AddItemNaive <- function(item)
{
    .GlobalEnv$Result[[length(.GlobalEnv$Result)+1]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemNaive(i))
#   user  system elapsed 
#  15.60    0.00   15.61 

慢.现在让我们尝试第二种方法:

Result <- list()

AddItemNaive2 <- function(item)
{
    .GlobalEnv$Result <- c(.GlobalEnv$Result, item)
}

system.time(for(i in seq_len(2e4)) AddItemNaive2(i))
#   user  system elapsed 
#  13.85    0.00   13.89

仍然很慢.

现在让我们尝试使用an environment,并在此环境中创建新变量,而不是将元素添加到列表中.这里的问题是必须命名变量,所以我将使用计数器作为字符串来命名每个项目"slot":

Counter <- 0
Result <- new.env()

AddItemEnvir <- function(item)
{
    .GlobalEnv$Counter <- .GlobalEnv$Counter + 1

    .GlobalEnv$Result[[as.character(.GlobalEnv$Counter)]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemEnvir(i))
#   user  system elapsed 
#   0.36    0.00    0.38 

哇快得多.:-)可能有点尴尬,但它的工作原理.

最后一种方法使用一个列表,但不是一次增加一个元素的大小,而是每次列表填满时它的大小加倍.列表大小也保存在专用变量中,以避免使用length以下任何减速:

Counter <- 0
Result <- list(NULL)
Size <- 1

AddItemDoubling <- function(item)
{
    if( .GlobalEnv$Counter == .GlobalEnv$Size )
    {
        length(.GlobalEnv$Result) <- .GlobalEnv$Size <- .GlobalEnv$Size * 2
    }

    .GlobalEnv$Counter <- .GlobalEnv$Counter + 1

    .GlobalEnv$Result[[.GlobalEnv$Counter]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemDoubling(i))
#   user  system elapsed 
#   0.22    0.00    0.22

它甚至更快.并且像任何列表一样易于工作.

让我们尝试使用更多迭代的最后两个解决方案:

Counter <- 0
Result <- new.env()

system.time(for(i in seq_len(1e5)) AddItemEnvir(i))
#   user  system elapsed 
#  27.72    0.06   27.83 


Counter <- 0
Result <- list(NULL)
Size <- 1

system.time(for(i in seq_len(1e5)) AddItemDoubling(i))
#   user  system elapsed 
#   9.26    0.00    9.32

好吧,最后一个是定义的方式.

Answer 2

这很容易.您只需要按以下方式添加它:

list1$bar <- bar

Answer 3

改变R中列表/向量长度的操作总是将所有元素复制到一个新列表中,因此速度很慢,O(n).在环境中存储是O(1)但具有更高的恒定开销.对于实际的O(1)附加和许多方法的基准比较,请参阅我在/sf/answers/2300921731/上对其他问题的回答.