列表的内部实现是什么？

Question

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

1. 一个动态矢量,当它满时会自动增加它的大小.
2. 附加项目的链接列表O(1),但访问项目是O(n).
3. 具有O(log(n))项目访问权限的树结构.
4. 具有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)的数组.调整大小会导致整个数据的副本和名称查找是线性的.

或者,您可以使用在内部使用哈希表的环境.