49

我对在摊销常数时间内将对象附加到 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"

这种方法的效率如何？有没有更优雅的方式？

4

3 回答 3

53

一次添加一个元素时，将元素添加到列表中非常慢。看这两个例子：

我将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

还是很慢。

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

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

好吧，最后一个绝对是要走的路。

于 2013-06-11T17:26:40.400 回答
22

这很容易。您只需要通过以下方式添加它：

list1$bar <- bar
于 2013-06-11T14:35:21.987 回答
6

在 R 中更改列表/向量长度的操作总是将所有元素复制到一个新列表中，因此会很慢，O(n)。在环境中存储是 O(1)，但具有更高的常量开销。有关多种方法的实际 O(1) 附加和基准比较，请参阅我在https://stackoverflow.com/a/32870310/264177上对另一个问题的回答。

于 2016-01-25T11:44:33.517 回答