Комбинаторный итератор, например expand.grid

Есть ли быстрый способ перебора комбинаций, подобных тем, которые возвращают expand.grid или CJ (data.table). Когда комбинаций достаточно, они становятся слишком большими, чтобы поместиться в памяти. В библиотеке itertools2 есть iproduct (порт itertools Python), но он очень медленный (по крайней мере, так, как я его использую, как показано ниже). Есть ли другие варианты?

Вот пример, в котором идея состоит в том, чтобы применить функцию к каждой комбинации строк из двух data.frames (предыдущий пост).

library(data.table)  # CJ
library(itertools2)  # iproduct iterator
library(doParallel)

## Dimensions of two data
dim1 <- 10
dim2 <- 100
df1 <- data.frame(a = 1:dim1, b = 1:dim1)
df2 <- data.frame(x= 1:dim2, y = 1:dim2, z = 1:dim2)

## function to apply to combinations
f <- function(...) sum(...)

## Too big to expand with bigger dimensions (ie, 1e6, 1e5) -> errors
## test <- expand.grid(seq.int(dim1), seq.int(dim2))
## test <- CJ(indx1 = seq.int(dim1), indx2 = seq.int(dim2))
## Error: cannot allocate vector of size 3.7 Gb

## Create an iterator over the cartesian product of the two dims
it <- iproduct(x=seq.int(dim1), y=seq.int(dim2))

## Setup the parallel backend
cl <- makeCluster(4)
registerDoParallel(cl)

## Run
res <- foreach(i=it, .combine=c, .packages=c("itertools2")) %dopar% {
  f(df1[i$x, ], df2[i$y, ])
}
stopCluster(cl)

## Expand.grid results (different ordering)
expgrid <- expand.grid(x=seq(dim1), y=seq(dim2))
test <- apply(expgrid, 1, function(i) f(df1[i[["x"]],], df2[i[["y"]],]))

all.equal(sort(test), sort(res))  # TRUE

r parallel-processing iterator combinations
person Rorschach    schedule 06.07.2015    source источник
comment
Я подозреваю, что вы пытаетесь обратиться к более общему случаю, но rowSums здесь очевидный первый шаг: rs1 <- rowSums(df1); rs2 <- rowSums(df2); res2 <- outer(rs1,rs2,"+") Чтобы проверить ... sum(res-c(t(res2))) # 0 Я не думаю, что распараллеливание очень полезно, когда каждая задача очень мала.   -  person Frank    schedule 06.07.2015
comment
@Frank да, это всего лишь простой пример, я бы хотел передать группы индексов ядрам, чтобы каждый мог обрабатываться как кусок.   -  person Rorschach    schedule 06.07.2015
comment
Я бы разделил самый маленький data.frame на куски таким образом, чтобы результат expand.grid самого большого data.frame и фрагмента другого был управляемым. Затем я перебирал все куски.   -  person nicola    schedule 06.07.2015

Ответы (1)


arrow_upward
2
arrow_downward

Я думаю, вы получите лучшую производительность, если дадите каждому из воркеров кусок одного из фреймов данных, попросите их выполнить вычисления, а затем объедините результаты. Это приводит к более эффективным вычислениям и сокращению использования памяти рабочими.

Вот пример, в котором используется функция isplitRow из пакета itertools:

library(doParallel)
library(itertools)
dim1 <- 10
dim2 <- 100
df1 <- data.frame(a = 1:dim1, b = 1:dim1)
df2 <- data.frame(x= 1:dim2, y = 1:dim2, z = 1:dim2)
f <- function(...) sum(...)

nw <- 4
cl <- makeCluster(nw)
registerDoParallel(cl)

res <- foreach(d2=isplitRows(df2, chunks=nw), .combine=c) %dopar% {
  expgrid <- expand.grid(x=seq(dim1), y=seq(nrow(d2)))
  apply(expgrid, 1, function(i) f(df1[i[["x"]],], d2[i[["y"]],]))
}

Я разделил df2, потому что в нем больше строк, но вы можете выбрать любой из них.

person Steve Weston    schedule 07.07.2015