使用Combn（）和BigMemory软件包生成非常大的字符串组合矩阵

StackOverflow https://stackoverflow.com/questions/4493287

  •  12-10-2019
  •  | 
  •  

题

我的矢量X为1,344个独特的字符串。我想生成一个矩阵，该矩阵为我提供三个可能的三个值组，无论秩序如何，并将其导出到CSV。

我正在M1上的EC2上运行R。large实例W 64bit Ubuntu。使用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'

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

有帮助吗？

解决方案

您可以首先找到所有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上时，功能在我的计算机上使用几乎不超过50 MB（大致估计）。

编辑

在旁注上：如果这是出于模拟的目的，我发现很难相信任何科学应用都需要400百万个模拟运行。您可能在这里问正确的答案...

概念证明：

我通过 tt[[i]]<-out, ， 添加 tt <- list() 在循环之前，然后返回（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"

其他提示

这是我在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 ++并在此处进行循环 /写作，因为它将是 很多 快点。

在第一个近似中， 每一个 算法将存储的速度交易。

您已经遇到了一个试图预列出您的完全枚举组合矩阵的边界。因此，也许您应该尽量不要预先分配此矩阵，而要尝试，例如

  1. 如果您认为需要组合，请将它们计算在其他地方，然后将它们存储在简单的db（或，heck，flat File）中，然后查找它们 - 保存了9 GB

  2. 利用开源，将代码读取到 combn() 并将其修改为 客户端服务器 东西：给有索引号码的电话 n, ，它将循环并返回 nth 入口。效率不高，但可能更容易 可行的.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top