我很好奇一个类型的对象是如何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)。