在循环中收集未知数量的结果

Question

如果事先不知道最终结果的数量,那么在R中循环收集结果的惯用方法是什么？这是一个玩具示例:

results = vector('integer')
i=1L
while (i < bigBigBIGNumber)  {
    if (someCondition(i)) results = c(results, i)
    i = i+1
}
results

这个例子的问题是(我假设)它将具有二次复杂性,因为向量需要在每个附加处重新分配.(这是正确的吗？)我正在寻找一种避免这种情况的解决方案.

我发现Filter,但它需要预生成1:bigBigBIGNumber,我想避免节省内存.(问题:是否for (i in 1:N)还预生成1:N并将其保留在内存中？)

我可以制作像这样的链表:

results = list()
i=1L
while (i < bigBigBIGNumber)  {
    if (someCondition(i)) results = list(results, i)
    i = i+1
}
unlist(results)

(请注意,这不是连接.它正在构建一个类似的结构list(list(list(1),2),3),然后展平unlist.)

有比这更好的方法吗？通常使用的惯用方法是什么？(我对R.很新.)我正在寻找有关如何解决这类问题的建议.关于紧凑(易写)和快速代码的建议是最受欢迎的!(但我想专注于快速和内存效率.)

Answer 1

这是一种算法，它在输出列表填满时将其大小加倍，从而实现一些线性计算时间，如基准测试所示：

test <- function(bigBigBIGNumber = 1000) {

  n <- 10L
  results <- vector("list", n)
  m <- 0L
  i <- 1L
  while (i < bigBigBIGNumber)  {
    if (runif(1) > 0.5) {
      m <- m + 1L
      results[[m]] <- i
      if (m == n) {
        results <- c(results, vector("list", n))
        n <- n * 2L
      }
    }
    i = i + 1L
  }
  unlist(results)
}

system.time(test(1000))
#    user  system elapsed 
#   0.008   0.000   0.008 
system.time(test(10000))
#    user  system elapsed 
#   0.090   0.002   0.093 
system.time(test(100000))
#    user  system elapsed 
#   0.885   0.051   0.936 
system.time(test(1000000))
#    user  system elapsed 
#   9.428   0.339   9.776