r - 列表的内部实现是什么？

Question

我很好奇list类型的对象是如何实现的。是吗


一个动态向量，当其充满时会自动增加其大小。
链接列表，其中添加项目为O(1)，但访问项目为O(n)。
具有O(log(n))项目访问权限的树形结构。
具有O(1)项目访问权的哈希表。


我很好奇，因为列表可以具有键值对，使它们看起来像哈希表，但是元素却是有序的，看起来像向量。

编辑：因为length(list(runif(1e4)))为1，所以当将元素追加到列表时，看起来每次都复制整个列表，这使其非常慢：

但是访问速度比向量慢得多：

z1 <- runif(1e4)
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

输出：

user  system elapsed 
0.060   0.000   0.062 

但：

z1 <- list(runif(1e4))
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

输出：

user  system elapsed 
1.31    0.00    1.31 

初始化一个包含10000个元素的列表：

z1 <- as.list(runif(1e4))
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

输出：

user  system elapsed 
0.060   0.000   0.065 

对于键和值访问：

z1 <- list()
for(i in 1:10000){key <- as.character(i); z1[[key]] <- i} 
system.time({
  for(i in 1:10000) x <- z1[["1"]]
})
system.time({
  for(i in 1:10000) x <- z1[["10000"]]
})

输出为：

user  system elapsed 
0.01    0.00    0.01 
user  system elapsed 
1.78    0.00    1.78 

这不是 O(1)访问，因此它不是哈希表。我的结论是，它不是动态数组，因为附加项将每次导致内存访问。它不是哈希表，因为按键访问不是 O(1)。

Answer 1

列表本质上只是R对象（SEXP）的数组。调整大小会导致整个数据的副本，并且名称查找是线性的。

或者，您可以使用内部使用哈希表的环境。