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

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个回答

261

如果这是一个字符串列表,只需使用 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 类型很难为所有类型和用途制定一个通用的习惯用语。


21
这并不是添加,而是连接。在调用 C(LL, c="harry") 后,“LL”仍将有两个元素。 - Nick
27
将值重新分配给LL变量:LL <- c(LL, c="harry") - Dirk Eddelbuettel
53
这仅适用于字符串。如果a、b和c是整数向量,则行为完全不同。 - Alexandre Rademaker
8
@Dirk:你的括号嵌套方式与我的不同。我对c()的调用有两个参数:我要附加到其中的列表,即list(a=3, b=c(4, 5)),以及我要附加的项,即c=c(6, 7)。如果你使用我的方法,你会发现附加了2个列表项(67,名称为c1c2),而不是一个明显意图的单个2元素向量c - j_random_hacker
8
结论是 mylist <- list(mylist, list(obj)) 吗?如果是的话,修改答案会更好。 - Matthew
显示剩余12条评论

103

该OP(在问题的2012年4月更新版本中)想知道是否有一种方法可以像使用C++的vector<>容器那样在摊销常数时间内添加到列表中。到目前为止,最好的答案仅显示给定固定大小问题的各种解决方案的相对执行时间,但不直接解决任何各种解决方案的算法效率。许多答案下面的评论讨论了一些解决方案的算法效率,但在截至2015年4月的每种情况下都得出了错误的结论

算法效率捕获增长特征,无论是时间(执行时间)还是空间(占用内存量) 随着问题规模的增长而变化。对于给定的固定大小问题运行各种解决方案的性能测试并不解决各种解决方案的增长率。该OP想知道是否有一种方法可以在“摊销常数时间”内向R列表附加对象。这是什么意思呢?为了解释,首先让我描述“常数时间”:

  • 恒定O(1)增长:

    如果执行给定任务所需的时间保持不变,当问题规模翻倍时,则称算法表现出恒定时间增长,或者在“大O”符号表示法中表示为O(1)时间增长。当OP说“摊销常数时间”时,他只是意味着“从长远来看”……也就是说,如果单个操作偶尔花费的时间比正常情况下要长得多(例如,如果预分配的缓冲区用完并且偶尔需要调整大小以获得更大的缓冲区大小),只要长期平均性能是恒定时间,我们仍然将其称为O(1)。

    为了比较,我还将描述“线性时间”和“二次时间”:

  • 线性O(n)增长:

    如果执行给定任务所需的时间随着问题规模的翻倍而翻倍,则称算法表现出线性时间O(n)增长。

  • 二次方O(n2)增长:

    如果执行给定任务所需的时间按问题规模的平方增加,则称算法表现出二次时间O(n2)增长。

还有许多其他效率类的算法;我将在维基百科文章中进行进一步讨论。

我感谢@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发布的结果明确表明,在问题大小为10000时,a <- list(a,list(i))方法是最快的,但单一问题大小的结果并没有解决解决方案的增长问题。为了解决这个问题,我们需要运行至少两个不同问题大小的分析测试:

> 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次,我们允许代码在第一次运行时加载到缓存中,然后给每个片段4次机会运行到完成,而不受外部事件的干扰。因此,由于我们确实在每次运行时都在运行完全相同的代码,并且在完全相同的输入条件下运行,我们只考虑“min”时间足以在各种代码选项之间进行最佳比较。

请注意,我选择首先使用2000个问题大小运行,然后是20000个问题大小运行,因此我的问题大小从第一次运行到第二次运行增加了10倍。

列表(list)解决方案的性能:O(1)(常数时间)

让我们首先看一下列表(list)解决方案的增长情况,因为我们可以立即看出它是两个分析运行中最快的解决方案:在第一次运行中,执行2000个“append”任务需要854秒(0.854秒)。在第二次运行中,执行20000个“append”任务需要8.746毫秒。一个天真的观察者会说:“啊,列表(list)的解决方案表现出O(n)的增长,因为随着问题规模增加了十倍,执行测试所需的时间也增加了。”但是,这种分析的问题在于OP想要的是单个对象插入的增长率,而不是整体问题的增长率。有了这个认识,就清楚了,列表(list)解决方案提供了OP想要的东西:以O(1)时间向列表中添加对象的方法。

其他解决方案的性能

其他任何解决方案都无法接近列表(list)解决方案的速度,但检查它们仍然是有益的:

大多数其他解决方案的性能似乎都是O(n)。例如,by_index解决方案,这是一种非常流行的解决方案,基于我在其他SO帖子中发现它的频率,需要11.6毫秒来添加2000个对象,并且需要953毫秒来添加十倍数量的对象。整个问题的时间增长了100倍,因此一个天真的观察者可能会说:“啊,by_index解决方案展示了O(n2)的增长,因为随着问题规模增加了十倍,执行测试所需的时间增长了100倍。”与之前一样,这种分析是错误的,因为OP对单个对象插入的增长感兴趣。如果我们将整体时间增长除以问题大小的增长,我们发现附加对象的时间增长仅增加了10倍,而不是100倍,这与问题大小的增长相匹配,因此by_index解决方案是O(n)的。没有列出显示附加单个对象具有O(n2)增长的解决方案。


1
给读者:请阅读JanKanis的答案,它对我上面的发现提供了非常实用的扩展,并深入探讨了各种解决方案在R的C实现内部工作负载方面的情况。 - phonetagger
7
不确定列表选项是否实现了所需功能:> length(c(c(c(list(1)), list(2)), list(3))) [1] 3
length(list(list(list(list(1)), list(2)), list(3))) [1] 2。看起来更像是嵌套列表。
- Picarus
1
@Picarus - 我认为你是对的。我已经不再使用R了,但幸运的是JanKanis发布了一个更有用的O(1)解决方案,并注意到了你提出的问题。我相信JanKanis会感谢你的点赞。 - phonetagger
@phonetagger,你应该编辑你的答案。并不是每个人都会阅读所有的答案。 - Picarus
“not a single answer has addressed the actual question” --> 问题在于原始问题并不是关于算法复杂度的,看一下问题的编辑历史。OP首先问如何在列表中添加元素,几个月后,他改变了问题。 - Carlos Cinelli
@CarlosCinelli - 你说得对,感谢指出。我已经相应地修改了我的回答开头。 - phonetagger

43
在其他答案中,只有 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

我已添加了linkedListexpandingList,以及两者的内联版本。 inlinedLinkedList基本上是list_的副本,但它还将嵌套结构转换回普通列表。除此之外,内联和非内联版本之间的差异是由于函数调用的开销。

所有变体的expandingListlinkedList都显示O(1)的附加性能,基准测试时间随附加项目数量呈线性缩放。 linkedListexpandingList慢,并且函数调用开销也可见。所以如果你确实需要尽可能快的速度(并希望坚持使用R代码),请使用expandingList的内联版本。

我还查看了R的C实现,对于任何大小的情况下,这两种方法都应该是O(1)附加,直到内存不足为止。

我还更改了env_as_container_,原始版本会将每个项存储在索引“i”下,覆盖之前添加的项。我添加的better_env_as_containerenv_as_container_非常相似,但没有deparse。两者都具有O(1)性能,但开销比链接/扩展列表要大得多。

内存开销

在C R实现中,每个分配的对象有4个字和2个整数的开销。 linkedList方法每次附加会分配一个长度为两个的列表,64位计算机上每个附加的项目总共使用(4*8+4+4+2*8=)56字节(不包括内存分配开销,因此可能更接近64字节)。 expandingList方法每个附加项使用一个字,加倍向量长度时使用一次复制,因此每个项的总内存使用量高达16字节。由于所有内存都在一个或两个对象中,因此每个对象的开销是微不足道的。我没有深入研究env内存使用情况,但我认为它将更接近于linkedList


保留列表选项的意义是什么,如果它不能解决我们试图解决的问题? - Picarus
1
@Picarus 我不确定你的意思。为什么我要将它保留在基准测试中?与其他选项进行比较。list_选项更快,如果您不需要转换为普通列表,即如果您将结果用作堆栈,则可能会有用。 - JanKanis
@Gabor Csardi在stackoverflow.com/a/29482211/264177的另一个问题中发布了一种更快的将环境转换回列表的方法。我也在我的系统上进行了基准测试。它比better_env_as_container快大约两倍,但仍然比linkedList和expandingList慢。 - JanKanis
深度嵌套(n = 99999)列表对于某些应用程序似乎是可管理和可容忍的:有人想要基准测试nestoR吗?(我在nestoR中使用的environment还是有点新手。)我的瓶颈几乎总是花费在编码和数据分析上的人工时间,但我很欣赏在这篇文章中找到的基准测试。至于内存开销,对于我的应用程序,每个节点最多不超过1 kB也无妨。我会保留大型数组等。 - Ana Nimbus

17

在 Lisp 中我们是这样做的:

> l <- c(1)
> l <- c(2, l)
> l <- c(3, l)
> l <- rev(l)
> l
[1] 1 2 3

虽然它是'cons',而不仅仅是'c'。如果你需要从一个空列表开始,使用l <- NULL。


3
太棒了!所有其他的解决方案都返回了一些奇怪的嵌套列表。 - metakermit
4
在Lisp中,将元素添加到一个列表的开头是O(1)操作,而将其添加到末尾则需要O(n)时间,@flies。性能提升的需求超过了反转操作的需要。但在R语言中不是这样的,在pairlist中也不是,即使它通常与列表最相似。 - Palec
@Palec “这在R中不是这种情况” - 我不确定你指的是哪个“这”。你是说添加不是O(1),还是不是O(n)? - flies
1
我是说,如果你在编写Lisp代码,你的方法会很低效,@flies。那个评论是为了解释答案为什么是这样写的。据我所知,在R中,这两种方法在性能上是相当的。但现在我不确定摊销复杂度。自从我上次发表评论以来,我就没有碰过R了。 - Palec
4
在 R 中,这种方法的时间复杂度为 O(n)。c() 函数会将其参数复制到一个新的向量/列表中并返回该向量/列表。 - JanKanis

7
你可能需要这样的东西吗?
> 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()赋值有点粗鲁),但据我所知,这正是你想要的。


5
如果将列表变量作为引用字符串传入,您可以在函数内部像这样访问它:
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
> 

1
这基本上是我想要的行为,但它仍然在内部调用append,导致O(n^2)的性能问题。 - Nick

5

不确定您为什么认为您的第一种方法行不通。您在lappend函数中有一个错误:length(list)应该是length(lst)。这样做很好,可以返回一个附加了obj的列表。


4
你是完全正确的。代码中有一个bug,我已经修复了它。我已经测试了我提供的lappend()函数,它的表现似乎与c()和append()函数一样好,它们都表现出O(n^2)的行为。 - Nick

5
我已经对这里提到的方法进行了小比较。
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 

这是很棒的信息:我永远不会猜到 list = list 不仅是赢家,而且胜出了1到2个数量级! - WestCoastProjects
这个比较是无效的:list_没有创建期望中的整数列表。它将包含列表的列表。在每次迭代中,都会创建一个具有2个元素的新列表,一个是新整数,另一个是相同列表的先前版本。因为值不被覆盖,内部执行了一个简单的引用复制。这就是为什么它如此快,但我们根本没有相同的对象。对于所有其他示例,我们都有长度为n+1的列表。 - David Bellot
@DavidBellot 这是正确的,它是用于基准测试级别的。你可以在最后将其压平 :) - Cron Merdek

3

尝试使用 lappend 函数。

lappend <- function (lst, ...){
  lst <- c(lst, list(...))
  return(lst)
}

从这个页面添加命名向量到列表中获取其他建议。

再见。


3
事实上,c()函数有一个微妙之处。如果您执行以下操作:
x <- list()
x <- c(x,2)
x = c(x,"foo")

您将如预期般获得以下内容:

[[1]]
[1]

[[2]]
[1] "foo"

但是如果你添加一个矩阵,x <- c(x, matrix(5,2,2),你的列表将会有另外4个值为5的元素! 你最好这样做:

x <- c(x, list(matrix(5,2,2))

它适用于任何其他对象,并且您将按预期获得结果:
[[1]]
[1]

[[2]]
[1] "foo"

[[3]]
     [,1] [,2]
[1,]    5    5
[2,]    5    5

最终,您的函数变成了:

push <- function(l, ...) c(l, list(...))

它适用于任何类型的对象。您可以更聪明地做到:

push_back <- function(l, ...) c(l, list(...))
push_front <- function(l, ...) c(list(...), l)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接