9

我知道预先分配一个向量或一个矩阵很有用，因为它们总是存储在一个连续的内存块中。

但是，就列表而言，它可以包含不同长度和模式的元素。所以我的第一个猜测是，一个列表可能只包含指向其元素真实地址的指针。我对么？这里有一个相关的问题列表的内部实现是什么？它说列表本质上是一个数组，但它没有涵盖元素如何存储在列表中，而每个元素的大小可能会发生变化。

示例 1：如果一个列表包含a,b,c,d,e，并且何时myList$a<-1:1000000，该列表是就地修改（这意味着仅a更新）还是整个列表被复制和更新？

示例 2

> system.time( { myList <- list()
+                myList$a <- 1:10000000
+                myList$b <- 1:10000100
+                myList$c <- 1:10000200 
+                myList$d <- 1:10000300})
   user  system elapsed 
   0.01    0.02    0.03

> system.time({ myList2<-list(a=1:10000000,b=1:10000100,c=1:10000200,d=1:10000300) })
   user  system elapsed 
   0.00    0.03    0.03

与没有预分配myList相比，效率会很低吗？myList2还是根本没有明显的性能差异，无论有多大a,b,c,d，因为第一个只复制了几倍的指针？

这里涉及到预分配。列表看起来如何？它是否只为指针预分配内存？如果是这种情况，我看不出有任何用处，因为无论如何都不会为指针复制太多数据。

> system.time( { myList <- vector("list", 4)
+                myList[[1]] <- 1:10000000
+                myList[[2]] <- 1:10000100
+                myList[[3]]  <- 1:10000200 
+                myList[[4]] <- 1:10000300
+                names(myList) <- letters[1:4]})
   user  system elapsed 
   0.01    0.02    0.03
4

2 回答 2

7 
 system.time( { myList <- list()
   myList$a <- 1:100000
   myList$b <- 1:100001
   myList$c <- 1:100002 
   myList$d <- 1:100003})
#   user  system elapsed 
#  0.019   0.001   0.022 

 system.time({ myList<-list(a=1:100000,b=1:100001,c=1:100002,d=1:100003) })
#   user  system elapsed 
#  0.001   0.001   0.002

通常建议进行预分配，尽管您所做的看起来不像我认为的预分配。这就是我会给出的描述。

system.time( { myList <- vector("list", 4)
   myList[[1]] <- 1:100000
   myList[[2]] <- 1:100001
   myList[[3]]  <- 1:100002 
   myList[[4]] <- 1:100003
   names(myList) <- letters[1:4]})
#   user  system elapsed 
#  0.001   0.001   0.001

顺便说一句：我不认为列表只是一个指针的心理模型是有用的。很多时候，简单的分配会创建一个全新的临时副本，然后重新分配该名称。

于 2013-08-25T01:26:41.047 回答
7

这对于评论来说太长了——但不是一个完整的答案。

就修改时的复制而言，命名列表与未命名列表的处理方式不同。

复制（对于大型对象）

这是一个复杂的问题。请参阅http://radfordneal.wordpress.com/2013/07/02/fixing-rs-named-problems-in-pqr/以获得合理的解释，并注意其中一些更改正在 R 的开发版本中实现。另请参阅http://r.789695.n4.nabble.com/Confused-about-NAMED-td4103326.html以进一步了解潜在的复杂性

以下是各种预分配可能性的一些时间安排

# preallocated contents so timing is list related only
.a <- seq_len(1e6); .b <- seq_len((1e6 + 1))
.c <- seq_len((1e6 + 2)); .d <- seq_len((1e6 + 3))



f1 <- function(){
# using `$<-` empty list
  x <- list()
  x$a <- .a
  x$b <- .b
  x$c <- .c 
  x$d <- .d
  x
}


f2 <- function(){
  # using `[[<-` on empty list
  x <- list()
  x[['a']] <- .a
  x[['b']] <- .b
  x[['c']] <- .c
  x[['d']] <- .d
  x
}


f3 <- function(){
  # using `[[<-` on empty list, naming later
  x <- list()
  x[[1]] <- .a
  x[[2]] <- .b
  x[[3]] <- .c
  x[[4]] <- .d
  names(x) <- letters[1:4]
  x
}

f4 <- function(){ 
  # just define the list
  x <- list(a = .a, b = .b,
            c = .c, d = .d)
}


f5 <- function(){ 
  # create a list of length 4, then fill and name
  x <- vector(mode = 'list', length = 4)
  x[[1]] <- .a
  x[[2]] <- .b
  x[[3]] <- .c
  x[[4]] <- .d
  names(x) <- letters[1:4]
  x
}

# f6 <- function(){
#  # this doesn't work!
#  # it creates a list of length 8
#  x <- vector(mode = 'list', length = 4)
#  x[['a']] <- .a
#  x[['b']] <- .b
#  x[['c']] <- .c
#  x[['d']] <- .d
#  x
# }


f7 <-function(){
# pre allocate list, name then fill
x <- vector(mode = 'list', length = 4)
  names(x) <- letters[1:4]
  x[[1]] <- .a
  x[[2]] <- .b
  x[[3]] <- .c
  x[[4]] <- .d
  x
}

f8 <- function(){
# preallocate correct length and then name
# and fill by name
  x <- vector(mode = 'list', length = 4)
  names(x) <- letters[1:4]
  x[['a']] <- .a
  x[['b']] <- .b
  x[['c']] <- .c
  x[['d']] <- .d
  x
}

library(microbenchmark)
microbenchmark(f1(),f2(),f3(),f4(),f5(),f7(),f8(),times=100)


microbenchmark(f1(),f2(),f3(),f4(),f5(),f7(),f8(),times=100)
# Unit: microseconds
#   expr      min       lq   median       uq       max neval
#   f1()    6.038   11.169   12.980   14.791    34.110   100
#   f2() 2528.881 4387.962 4707.014 6472.823 74586.266   100
#   f3() 2532.805 4537.376 4714.258 5353.722 74903.206   100
#   f4() 2475.756 4531.489 4721.503 6331.860 74460.395   100
#   f5() 2508.959 4512.474 4759.535 6673.551  7966.668   100
#   f7() 2545.181 4477.761 4709.127 6372.610  7964.856   100
#   f8() 2508.053 4467.799 4669.131 6181.993 74236.726   100
#
#  All results are identical.
all(identical(f1(),f2()),identical(f1(),f3()),
    identical(f1(),f4()),identical(f1(),f5()),
    identical(f1(),f7()),identical(f1(),f8()))

# [1] 是的

所有结果都是相同的。

显然在空列表上使用 $<-` 是明显的赢家。这违背了我对什么应该是最快的想法

于 2013-08-26T00:25:27.173 回答