Generación de un muy grande matriz de combinaciones de cadena usando Combn () y el paquete de bigmemory

Question

Tengo un vector x de 1.344 cadenas únicas. Quiero generar una matriz que me da todos los posibles grupos de tres valores, sin importar el orden, y la exportación de que a un csv.

Estoy corriendo R en EC2 en una instancia m1.large w Ubuntu de 64 bits. Cuando se utiliza Combn (x, 3) consigo un error de falta de memoria:

Error: cannot allocate vector of size 9.0 Gb

El tamaño de la matriz resultante es C1344,3 = 403,716,544 filas y tres columnas -. Que es la transpuesta del resultado de la función Combn ()

I pensó en utilizar el paquete bigmemory para crear un archivo de copia de seguridad big.matrix por lo que puede asignar a los resultados de la función Combn (). Puedo crear una matriz grande preasignado:

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

Pero cuando intento para asignar los valores test <- combn(x, 3) sigo teniendo el mismo: Error: cannot allocate vector of size 9.0 Gb

Yo incluso intentado coaccionar el resultado de combn(x,3) pero creo que debido a que la función Combn () devuelve un error, la función big.matrix no funciona bien.

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'

¿Hay una manera de combinar estas dos funciones juntas para conseguir lo que necesito? ¿Hay otras maneras de lograr esto? Gracias.

Answer 1

En primer lugar, podría encontrar todas las combinaciones de 2 vías, y luego simplemente combinarlos con el valor 3D mientras ahorrando cada vez. Esto toma mucho menos memoria:

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")

Esto no es tan general como la respuesta de Josué sin embargo, es específicamente para su caso. Creo que es más rápido -de nuevo, en este caso- en particular, pero no hice la comparación. La función es eficaz en el ordenador utilizando poco más de 50 Mb (estimados aproximadamente) cuando se aplica a la x.

editar

En una nota: Si esto es para fines de simulación, se me hace difícil creer que cualquier aplicación científica necesita más de 400 millones de corridas de simulación. Se puede preguntar la respuesta correcta a la pregunta equivocada aquí ...

Prueba de concepto:

Me cambió la línea de escritura por tt[[i]]<-out, tt <- list() añadido antes del bucle y de retorno (tt) después de ella. A continuación:

> 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" 

Answer 2

Esta es una función que he escrito en R, que en la actualidad encuentra su casa (dejados de exportar) en el LSPM paquete. Se le da el número total de elementos n, el número de elementos para seleccionar r, y el índice de la combinación que desea i; devuelve los valores en 1:n correspondiente a la combinació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)
}

Se le permite generar cada combinación basada en el valor del índice lexicográfico:

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

Por lo que sólo necesita para recorrer de 1: 403 716 544 y anexar los resultados en un archivo. Se puede tomar un tiempo, pero es al menos posible (véase la respuesta de Dirk). También puede ser necesario hacerlo en varios bucles, ya que el vector de 1:403716544 no cabe en la memoria en mi máquina.

o usted podría aportar el código R para C / C ++ y hacer el bucle / escribir allí, ya que sería mucho más rápido.

Answer 3

En una primera aproximación, todos oficios algoritmo ubicados en almacenamientos para la velocidad.

Se han alcanzado un límite tratando de asignar previamente a su matriz de combinación totalmente enumerado. Así que tal vez debería tratar de no asignar previamente esta matriz sino tratar, por ejemplo,

1. Si usted piensa que necesita las combinaciones, calcular en otro lugar y almacenarlos en un simple db (o, diablos, archivos planos) y mirar hacia arriba - 9 GB salvado

2. Tome ventaja de código abierto, leer el código de combn() y modificarlo en un cliente-servidor cosita: dada una llamada con número de índice N , se se bucle y devolver el enésima ingreso. No es eficiente, pero posiblemente más fácilmente factible .