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

Question

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

Я запускаю R на EC2 на экземпляре m1.large с 64-битной 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'

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

Answer 1

Вот функция, которую я написал в 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 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")

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

EDIT

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

В первом приближении каждый алгоритм обменивает память на скорость.

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

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

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