Generando una grande matrice di combinazioni di stringhe utilizzando combn () e il pacchetto bigmemory

Question

Ho un vettore x di 1.344 stringhe univoche. Voglio generare una matrice che mi dà tutti i possibili gruppi di tre valori, indipendentemente dall'ordine, e l'esportazione che in un file CSV.

Sono in esecuzione R su EC2 su un'istanza m1.large w Ubuntu a 64bit. Quando si utilizza combn (x, 3) ottengo un errore di memoria:

Error: cannot allocate vector of size 9.0 Gb

La dimensione della matrice risultante è C1344,3 = 403,716,544 righe e tre colonne -. Che è la trasposta del risultato della funzione combn ()

Ho pensato di utilizzare il pacchetto bigmemory per creare un file di backup big.matrix in modo da poter poi assegnare i risultati della funzione combn (). Posso creare una grande matrice di preassegnate:

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

Ma quando cerco di assegnare i valori test <- combn(x, 3) ho ancora lo stesso: Error: cannot allocate vector of size 9.0 Gb

Ho anche cercato di costringere il risultato di combn(x,3) ma credo che perché la funzione combn () restituisce un errore, la funzione big.matrix non funziona neanche.

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'

C'è un modo per combinare queste due funzioni insieme per ottenere quello che mi serve? Ci sono altri modi per raggiungere tale obiettivo? Grazie.

Answer 1

Si potrebbe prima trovare tutte le combinazioni a 2 vie, e poi basta combinarle con il valore 3d, risparmiando loro ogni volta. Questo richiede un sacco meno 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")

Questo non è così generale, come la risposta di Joshua, però, è specifico per il vostro caso. Credo che sia più veloce -nuovamente, per questo particolare caso-, ma non ho fatto il paragone. Funzione lavora sul mio computer utilizzando poco più di 50 Mb (circa stimato), quando applicato al tuo x.

Modifica

Su un sidenote: Se questo è per la simulazione, trovo difficile credere che ogni applicazione scientifica ha bisogno di oltre 400 milioni di simulazioni. Si potrebbe chiedere la risposta corretta alla domanda sbagliata qui ...

prova di concetto:

ho cambiato la linea di scrittura da parte tt[[i]]<-out, tt <- list() aggiunto prima del ciclo e ritorno (tt) dopo di esso. Poi:

> 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

Ecco una funzione che ho scritto in R, che attualmente trova la sua (quali no) casa nel LSPM pacchetto. Si dà il numero totale di elementi n, il numero di elementi da selezionare r, e l'indice della combinazione che si desidera i; restituisce i valori in 1:n corrispondente alla combinazione 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)
}

Permette di generare ogni combinazione in base al valore dell'indice lessicografico:

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

Quindi, non vi resta che un ciclo su 1: 403.716.544 e aggiungere i risultati in un file. Si può prendere un po ', ma è almeno possibile (vedi risposta di Dirk). Potrebbe anche essere necessario farlo in diversi cicli, dal momento che il vettore 1:403716544 non entra in memoria sulla mia macchina.

Oppure si può semplicemente porta il codice R per C / C ++ e fare il loop / scrittura lì, dal momento che sarebbe stato molto più veloce.

Answer 3

In prima approssimazione, tutti compravendite algoritmo da sistemi di storage per la velocità.

Hai colpito un confine cercando di preallocare tua matrice combinazione completamente enumerato. Così forse si dovrebbe cercare di non preallocare questa matrice, ma da provare, per esempio,

1. Se pensi di aver bisogno le combinazioni, calcolare da qualche altra parte e memorizzarli in un semplice db (o, diamine, flat file) e guardare in alto - 9 GB salvato

2. Approfittate di open source, leggere il codice a combn() e modificarlo in un client-server thingy: data una chiamata con numero di indice N , è si ciclo e restituire il ennesimo di ingresso. Non è efficiente, ma forse più facilmente fattibile .