7

我有一个包含 1,344 个唯一字符串的向量 x。我想生成一个矩阵，它为我提供所有可能的三个值组，无论顺序如何，并将其导出到 csv。

我在带有 64 位 Ubuntu 的 m1.large 实例上的 EC2 上运行 R。使用 combn(x, 3) 时出现内存不足错误：

Error: cannot allocate vector of size 9.0 Gb

结果矩阵的大小为 C1344,3 = 403,716,544 行和三列 - 这是 combn() 函数结果的转置。

我想使用 bigmemory 包创建一个支持 big.matrix 的文件，这样我就可以分配 combn() 函数的结果。我可以创建一个预先分配的大矩阵：

library(bigmemory)
x <- as.character(1:1344)
combos <- 403716544
test <- filebacked.big.matrix(nrow = combos, ncol = 3, 
        init = 0, backingfile = "test.matrix")

但是当我尝试分配值时，test <- combn(x, 3)我仍然得到相同的结果：Error: cannot allocate vector of size 9.0 Gb

我什至尝试强制执行结果，combn(x,3)但我认为因为 combn() 函数返回错误，所以 big.matrix 函数也不起作用。

test <- as.big.matrix(matrix(combn(x, 3)), backingfile = "abc")
Error: cannot allocate vector of size 9.0 Gb
Error in as.big.matrix(matrix(combn(x, 3)), backingfile = "abc") : 
  error in evaluating the argument 'x' in selecting a method for function 'as.big.matrix'

有没有办法将这两个功能结合在一起以获得我需要的东西？有没有其他方法可以实现这一目标？谢谢。

4

3 回答 3

5

这是我用 R 编写的一个函数，它目前在LSPM包中找到它的（未导出的）主页。你给它项目的总数n，要选择的项目的数量r，以及你想要的组合的索引i；它返回1:n与组合对应的值i。

".combinadic" <- function(n, r, i) {

  # http://msdn.microsoft.com/en-us/library/aa289166(VS.71).aspx
  # http://en.wikipedia.org/wiki/Combinadic

  if(i < 1 | i > choose(n,r)) stop("'i' must be 0 < i <= n!/(n-r)!")

  largestV <- function(n, r, i) {
    #v <- n-1
    v <- n                                  # Adjusted for one-based indexing
    #while(choose(v,r) > i) v <- v-1
    while(choose(v,r) >= i) v <- v-1        # Adjusted for one-based indexing
    return(v)
  }

  res <- rep(NA,r)
  for(j in 1:r) {
    res[j] <- largestV(n,r,i)
    i <- i-choose(res[j],r)
    n <- res[j]
    r <- r-1
  }
  res <- res + 1
  return(res)
}

它允许您根据字典索引的值生成每个组合：

> .combinadic(1344, 3, 1)
[1] 3 2 1
> .combinadic(1344, 3, 2)
[1] 4 2 1
> .combinadic(1344, 3, 403716544)
[1] 1344 1343 1342

因此，您只需要遍历 1:403716544 并将结果附加到文件中。这可能需要一段时间，但至少是可行的（参见 Dirk 的回答）。您可能还需要在多个循环中执行此操作，因为该向量1:403716544不适合我机器上的内存。

或者您可以将 R 代码移植到 C/C++ 并在那里进行循环/编写，因为它会快得多。

于 2010-12-20T22:10:28.823 回答
3

您可以先找到所有 2 路组合，然后将它们与 3d 值组合，同时每次都保存它们。这需要更少的内存：

combn.mod <- function(x,fname){
  tmp <- combn(x,2,simplify=F)
  n <- length(x)
  for ( i in x[-c(n,n-1)]){
    # Drop all combinations that contain value i
    id <- which(!unlist(lapply(tmp,function(t) i %in% t)))
    tmp <- tmp[id]
    # add i to all other combinations and write to file
    out <- do.call(rbind,lapply(tmp,c,i))
    write(t(out),file=fname,ncolumns=3,append=T,sep=",")
  }
}

combn.mod(x,"F:/Tmp/Test.txt")

不过，这不像约书亚的回答那么笼统，它专门针对您的情况。我想它更快 - 再次，对于这种特殊情况 - 但我没有进行比较。当应用于您的 x.

编辑

附带说明：如果这是出于模拟目的，我很难相信任何科学应用程序都需要 400+ 百万次模拟运行。您可能会在这里问错误问题的正确答案...

概念证明：

我将写入行更改为tt[[i]]<-out，在循环之前添加tt <- list()，在循环之后添加 return(tt) 。然后：

> do.call(rbind,combn.mod(letters[1:5]))
      [,1] [,2] [,3]
 [1,] "b"  "c"  "a" 
 [2,] "b"  "d"  "a" 
 [3,] "b"  "e"  "a" 
 [4,] "c"  "d"  "a" 
 [5,] "c"  "e"  "a" 
 [6,] "d"  "e"  "a" 
 [7,] "c"  "d"  "b" 
 [8,] "c"  "e"  "b" 
 [9,] "d"  "e"  "b" 
[10,] "d"  "e"  "c"
于 2010-12-20T23:03:37.040 回答
1

在第一个近似值上，每个算法都会牺牲存储来换取速度。

您在尝试预先分配完全枚举的组合矩阵时遇到了问题。所以也许你不应该尝试预先分配这个矩阵，而是尝试说，

  1. 如果您认为需要这些组合，请在其他地方计算它们并将它们存储在一个简单的数据库（或者，哎呀，平面文件）中并查找它们——节省了 9 GB

  2. 利用开源，阅读代码combn()并将其修改为客户端-服务器事物：给定索引号为N的调用，它将循环并返回第N 个条目。效率不高，但可能更容易可行。

于 2010-12-20T21:44:22.380 回答