Создание очень большой матрицы строковых комбинаций с использованием пакета combn () и bigmemory

Question

У меня есть вектор X из 1344 уникальных строк. Я хочу генерировать матрицу, которая дает мне все возможные группы из трех значений, независимо от порядка, и экспортировать ее в CSV.

Я запускаю R на EC2 на экземпляре M1.large W 64Bit Ubuntu. При использовании Combn (x, 3) я получаю ошибку в памяти:

Error: cannot allocate vector of size 9.0 Gb

Размер полученной матрицы составляет C1344,3 = 403 716 544 строк и три столбца, что является транспонированием результата функции compn ().

Я подумал об использовании пакета BigMemory для создания File Backed.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'

Есть ли способ объединить эти две функции вместе, чтобы получить то, что мне нужно? Есть ли другие способы достижения этого? Спасибо.

Answer 1

Сначала вы можете найти все двухсторонние комбинации, а затем просто объединить их со 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")

Это не так общее, как ответ Джошуа, хотя это специально для вашего дела. Я предполагаю, что это быстрее -снова, для этого конкретного случая, но я не проходил сравнение. Функция работает на моем компьютере, используя практически более 50 МБ (примерно оценено) при применении к вашему x.

РЕДАКТИРОВАТЬ

На сходе: если это для имитационных целей, мне трудно поверить, что любому научному приложению требуется более 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" 

Answer 2

Вот функция, которую я написал в 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 и добавить результаты в файл. Это может занять некоторое время, но это, по крайней мере, выполнимо (см. Ответ Дирка). Вам также может понадобиться сделать это в нескольких петлях, так как вектор 1:403716544 Не вписывается в память на моей машине.

Или вы можете просто перенести код R в C / C ++ и выполнить цикл / написание там, так как это будет много Быстрее.

Answer 3

При первом приближении, каждый Алгоритм торгуется с хранения для скорости.

Вы попали в границу, пытаясь предварительно разобрать свою полностью перечисленную комбинированную матрицу. Так что, может быть, вам следует стараться не предварительно переоценить эту матрицу, а попробовать, скажем,

1. Если вы думаете, что вам нужны комбинации, вычислите их где -нибудь еще и храните в простом DB (или, черт возьми, плоский файл) и посмотрите - 9 ГБ сохранили

2. Воспользуйтесь открытым исходным кодом, прочитайте код combn() и изменить его в клиент-сервер Thingy: получил звонок с номером индекса Не, это зацикнет и вернет Nth вход. Не эффективно, но, возможно, легче достижимый.