Python 的 R 的 xrange 替代方案或如何懒惰地循环遍历大型数据集？

Question

以下示例基于 discussion about using expand.grid with large data. As you can see it ends up with error. I guess this is due to possible combinations which is according to mentioned 页数 687 亿：

> v1 <-  c(1:8)
> v2 <-  c(1:8)
> v3 <-  c(1:8)
> v4 <-  c(1:8)
> v5 <-  c(1:8)
> v6 <-  c(1:8)
> v7 <-  c(1:8)
> v8 <-  c(1:8)
> v9 <-  c(1:8)
> v10 <- c(1:8)
> v11 <- c(1:8)
> v12 <- c(1:8)
> expand.grid(v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12)
Error in rep.int(rep.int(seq_len(nx), rep.int(rep.fac, nx)), orep) : 
  invalid 'times' value
In addition: Warning message:
In rep.int(rep.int(seq_len(nx), rep.int(rep.fac, nx)), orep) :
  NAs introduced by coercion to integer range

即使有八个向量，它也会耗尽我的 CPU and/or RAM (> expand.grid(v1, v2, v3, v4, v5, v6, v7, v8))。 Here I've found some improvements which suggests using outer or rep.int. Those solutions works with two vectors so I've not able to apply it for 12 vectors but I guess the principle is the same: It creates large matrix which resides in memory. I'm wondering if there is something like python's xrange which evaluates lazily? Here 我找到了 delayedAssign 函数，但我想这无济于事，因为还提到了以下内容：

Unfortunately, R evaluates lazy variables when they are pointed to by a data structure, even if their value is not needed at the time. This means that infinite data structures, one common application of laziness in Haskell, are not possible in R.

使用嵌套循环是否只能解决此问题？

PS：我没有具体问题，但假设您出于某种原因需要使用接受 12 个整数参数的函数进行一些计算。还假设您需要对这 12 个整数进行所有组合并将结果保存到文件中。使用 12 个嵌套循环并将结果连续保存到文件将起作用（尽管它会很慢但不会占用您的 RAM）。展示了如何使用 expand.grid 和 apply 函数来替换两个嵌套循环。问题是使用 expand.grid 创建具有 12 个长度为 8 的向量的矩阵有一些缺点：

生成这样的矩阵很慢
这么大的矩阵消耗内存很大（687亿行8列）
使用 apply 对该矩阵的进一步迭代也很慢

所以在我看来，功能方法比程序解决方案慢得多。我只是想知道是否有可能懒惰地创建理论上不适合内存的大型数据结构并对其进行迭代。就这些了。

Answer 1

一种（可以说更多 "proper"）方法来解决这个问题是为 @BenBolker 建议的 iterators 编写自己的迭代器（关于编写扩展的 pdf 是 here）。缺少更正式的东西，这是一个穷人的迭代器，类似于 expand.grid 但手动推进。（注意：考虑到每次迭代的计算量 "more expensive" 比这个函数本身就足够了。这确实可以改进，但是 "it works"。）

此函数 returns 每次返回函数时都会返回一个命名列表（带有提供的因子）。它是懒惰的，因为它没有扩展整个可能的列表；争论本身并不懒惰，他们应该立即'consumed'。

lazyExpandGrid <- function(...) {
  dots <- list(...)
  sizes <- sapply(dots, length, USE.NAMES = FALSE)
  indices <- c(0, rep(1, length(dots)-1))
  function() {
    indices[1] <<- indices[1] + 1
    DONE <- FALSE
    while (any(rolls <- (indices > sizes))) {
      if (tail(rolls, n=1)) return(FALSE)
      indices[rolls] <<- 1
      indices[ 1+which(rolls) ] <<- indices[ 1+which(rolls) ] + 1
    }
    mapply(`[`, dots, indices, SIMPLIFY = FALSE)
  }
}

示例用法：

nxt <- lazyExpandGrid(a=1:3, b=15:16, c=21:22)
nxt()
#   a  b  c
# 1 1 15 21
nxt()
#   a  b  c
# 1 2 15 21
nxt()
#   a  b  c
# 1 3 15 21
nxt()
#   a  b  c
# 1 1 16 21

## <yawn>

nxt()
#   a  b  c
# 1 3 16 22
nxt()
# [1] FALSE

注意：为了简洁起见，我使用了as.data.frame(mapply(...))作为示例；无论哪种方式，它都可以工作，但是如果命名列表对您来说工作正常，则不需要转换为 data.frame。

编辑

基于，这是一个大大改进的版本，它 (a) 更快并且 (b) 允许任意搜索。

lazyExpandGrid <- function(...) {
  dots <- list(...)
  argnames <- names(dots)
  if (is.null(argnames)) argnames <- paste0('Var', seq_along(dots))
  sizes <- lengths(dots)
  indices <- cumprod(c(1L, sizes))
  maxcount <- indices[ length(indices) ]
  i <- 0
  function(index) {
    i <<- if (missing(index)) (i + 1L) else index
    if (length(i) > 1L) return(do.call(rbind.data.frame, lapply(i, sys.function(0))))
    if (i > maxcount || i < 1L) return(FALSE)
    setNames(Map(`[[`, dots, (i - 1L) %% indices[-1L] %/% indices[-length(indices)] + 1L  ),
             argnames)
  }
}

它可以在没有参数（自动增加内部计数器）、一个参数（查找并设置内部计数器）或向量参数（查找每个并将计数器设置为最后一个）的情况下工作，returns一个data.frame).

最后一个用例允许对设计的子集进行抽样 space：

set.seed(42)
nxt <- lazyExpandGrid2(a=1:1e2, b=1:1e2, c=1:1e2, d=1:1e2, e=1:1e2, f=1:1e2)
as.data.frame(nxt())
#   a b c d e f
# 1 1 1 1 1 1 1
nxt(sample(1e2^6, size=7))
#      a  b  c  d  e  f
# 2   69 61  7  7 49 92
# 21  72 28 55 40 62 29
# 3   88 32 53 46 18 65
# 4   88 33 31 89 66 74
# 5   57 75 31 93 70 66
# 6  100 86 79 42 78 46
# 7   55 41 25 73 47 94

感谢 alexis_laz 对 cumprod、Map 和指数计算的改进！

Answer 2

另一种方法，不知何故，看起来有效..：

exp_gr = function(..., index)
{
    args = list(...)
    ns = lengths(args)
    offs = cumprod(c(1L, ns))
    n = offs[length(offs)]

    stopifnot(index <= n)

    i = (index[[1L]] - 1L) %% offs[-1L] %/% offs[-length(offs)] 

    return(do.call(data.frame, 
           setNames(Map("[[", args, i + 1L), 
                    paste("Var", seq_along(args), sep = ""))))
}

在上面的函数中，...是expand.grid的参数，index是递增的组合数。例如：

expand.grid(1:3, 10:12, 21:24, letters[2:5])[c(5, 22, 24, 35, 51, 120, 144), ]
#    Var1 Var2 Var3 Var4
#5      2   11   21    b
#22     1   11   23    b
#24     3   11   23    b
#35     2   12   24    b
#51     3   11   22    c
#120    3   10   22    e
#144    3   12   24    e
do.call(rbind, lapply(c(5, 22, 24, 35, 51, 120, 144), 
                      function(i) exp_gr(1:3, 10:12, 21:24, letters[2:5], index = i)))
#  Var1 Var2 Var3 Var4
#1    2   11   21    b
#2    1   11   23    b
#3    3   11   23    b
#4    2   12   24    b
#5    3   11   22    c
#6    3   10   22    e
#7    3   12   24    e

在大型结构上：

expand.grid(1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2)
#Error in rep.int(rep.int(seq_len(nx), rep.int(rep.fac, nx)), orep) : 
#  invalid 'times' value
#In addition: Warning message:
#In rep.int(rep.int(seq_len(nx), rep.int(rep.fac, nx)), orep) :
#  NAs introduced by coercion to integer range
exp_gr(1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, index = 1)
#  Var1 Var2 Var3 Var4 Var5 Var6
#1    1    1    1    1    1    1
exp_gr(1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, index = 1e3 + 487)
#  Var1 Var2 Var3 Var4 Var5 Var6
#1   87   15    1    1    1    1
exp_gr(1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, index = 1e2 ^ 6)
#  Var1 Var2 Var3 Var4 Var5 Var6
#1  100  100  100  100  100  100
exp_gr(1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, 1:1e2, index = 1e11 + 154)
#  Var1 Var2 Var3 Var4 Var5 Var6
#1   54    2    1    1    1   11

与此类似的方法是构造一个 "class" 来存储 ... 参数以在 expand.grid 上使用并定义一个 [ 方法来计算适当的需要时组合索引。使用 %% 和 %/% 似乎是有效的，不过，我想使用这些运算符进行迭代会比需要的慢。

Python 的 R 的 xrange 替代方案或如何懒惰地循环遍历大型数据集？

Python's xrange alternative for R OR how to loop over large dataset lazilly?

r

infinite

lazy-evaluation