列表的内部实现是什么? [英] What is the internal implementation of lists?

问题描述

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

I am curious how an object of type list is implemented. Is it

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

1. a dynamic vector that will automatically increase its size when it is full.
2. a linked list where appending an item is O(1), but accessing an item is O(n).
3. a tree structure with O(log(n)) item access.
4. a hashtable with O(1) item access.

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

I am curious because lists can have key-value pairs that make them look like hash tables, but the elements are in order, which looks like a vector.

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

Edit: because length(list(runif(1e4))) is 1, so when append element to a list, it looks like that it copy the whole list every time, that makes it very slow:

但是访问速度比矢量慢得多:

But the access speed is much slower than a vector:

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个元素的列表:

init a list with 10000 elements:

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 

对于键&值访问权限:

For the key & value access:

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).

It's not an O(1) access, so it's not a hash table. My conclusion is that it's not a dynamic array since appending items will cause memory accesses every time; it's not a hashtable since access by key is not O(1).

推荐答案

列表实质上只是R对象(SEXP)的数组.调整大小会导致复制整个数据，并且名称查找是线性的.

Lists are essentially just arrays of R objects (SEXP). Resizing causes copies of the whole data and name lookup is linear.

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

Alternatively, you can use environments, which use hash tables internally.

这篇关于列表的内部实现是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！