R中的高效链表(有序集)

Question

从数据库游标中读取记录时,通常会提前知道有多少行.这使得无法预先分配正确大小的列表来存储这些对象.

当我们总大小未知时,将所有记录存储在列表中的有效方法是什么？基本列表类型很慢,因为每次附加元素时它都会复制整个列表:

x <- list()
for(i in 1:1e5){
  x[[i]] <- list("foo" = rnorm(3), bar = TRUE)
}

环境更有效,但它是地图而不是有序集.所以我们需要将索引转换为字符串,然后对键进行排序以检索值,这似乎不是最理想的:

env <- new.env()
for(i in 1:1e5){
  env[[sprintf("%09d", i)]] <- list("foo" = rnorm(3), bar = TRUE)
}
x <- lapply(sort(ls(env)), get, env, inherits = FALSE)

A pairlist应该是R中的链表,但是只要从R中追加一个元素,R就会将它强行插入到常规列表中.

Answer 1

这很慢:

 > x <- list()
 > for(i in 1:1e5){x[[i]]=list(foo=rnorm(3),bar=TRUE)}

我放弃了等待.但这很快,几乎是瞬间的:

 > x <- list()
 > length(x)=1e5
 > for(i in 1:1e5){x[[i]]=list(foo=rnorm(3),bar=TRUE)}

所以我认为要走的路是每次将列表长度扩展10000,并在到达最后一个元素并知道最终输出时将其修剪回去.

 > length(x)=2e5  # extend by another 1e5
 > for(i in 1:1e5){x[[i+1e5]]=list(foo=rnorm(3),bar=TRUE)}
 > length(x)=3e5  # and again... but this time only 100 more elts:
 > for(i in 1:100){x[[i+2e5]]=list(foo=rnorm(3),bar=TRUE)}
 > length(x) = 2e5 + 100

另一种方法是每次需要更多元素时将列表大小加倍.

Answer 2

不久前，我做了一些实验，在 R 中使用配对列表与列表来实现堆栈和队列，并将它们放在这个包中： https: //github.com/wch/qstack。我在自述文件中添加了一些基准。

简而言之：使用配对列表并不比使用列表快，并且随着列表的增长而加倍。还：

• 直接修改任何其他 R 代码使用的配对列表是危险的，因为 R 假定配对列表是修改时复制的。
• 列表的内存效率更高，因为项目不需要指向下一个项目的指针。
• 列表中的随机访问比配对列表中的随机访问快得多。
• 如果您需要在其中插入或删除项目（使用 C），配对列表会更快。