我有一个包含两列的data.table。“活动,小组”最多可能有20行,或少至1行。这些事件中的每一个都被分为给定的组。data.table已按组排序。
例如:
Events group
a 1
b 2
c 2
d 2
e 3
f 3
我需要做的是:-对于每个组,计算其事件的所有排列。-计算该排列的所有交叉组合。-稍后,对于每个“组合”,我将进一步计算其他值。
在我的示例中,我将获得此排列(按行显示)
a
b c d
b d c
c b d
c d b
d b c
d c b
e f
f e
最后是行的这种交叉组合:
a b c d e f
a b d c e f
a c b d e f
a c d b e f
a d b c e f
a d c b e f
a b c d f e
a b d c f e
a c b d f e
a c d b f e
a d b c f e
a d c b f e
我实现的方式是:
library(data.table)
library(arrangements)
myDT <- data.table(ll=letters[1:6], gr=c(1,2,2,2,3,3)) #simple example
dos <- function(x,y) {
temp <- expand.grid(1:nrow(x),1:nrow(y))
cbind(x[temp[,1],], y[temp[,2],])
}
fun2 <- function(z) Reduce(dos,z)
permu <- function(xx ) { # alternative to compute the permutations
if (length(xx)==1) {
matrix(xx)
} else if (length(xx)==2) {
rbind(c(xx[1], xx[2]),c(xx[2], xx[1]))
} else {
permutations(xx)
} }
f1 <- function(x) {fun2(tapply(myDT$ll,myDT$gr, permutations))}
f2 <- function(x) {fun2(myDT[,.(.(permutations(ll))),by=gr]$V1)}
f3 <- function(x) {fun2(myDT[,.(.(permu(ll))),by=gr]$V1)}
第一种方法使用tapply。第二种方法尝试以data.table的方式进行计算。第三种方法试图使小组计算更快。我正在使用“安排”包中的排列,因为它很快。随意使用任何软件包(例如RcppAlgos)或编写自己的算法。我不介意输出是否是矩阵,data.table,列表,是否已转置,是否使用其他容器或是否以其他方式排序。
myDT <- data.table(ll=letters[1:6], gr=c(1,2,2,2,3,3))
f1() 982.05us 1.88KB 501ms
f2() 2.38ms 52.27KB 501ms
f3() 1.83ms 52.27KB 501ms
为了进行基准测试,我们可以使用更大的示例。
myDT <- data.table(ll=letters[1:15], gr=rep(1:5, times=rep(5:1))) # larger example
min median mem_alloc gc total_time
f1() 381.5ms 911ms 22.3MB 1.82s
f2() 123.5ms 185ms 22.3MB 580.22ms
f3() 99.3ms 130ms 22.3MB 505.05ms
我该如何更快地完成? (也可以使用更少的内存)如果我尝试使用data.table(ll = letters [1:21],gr = rep(1:6,times = rep(6:1))完成此操作,则需要3分钟以上的时间,因为我真正的问题,我需要执行一百万次计算。
迟早您将遇到内存不足的问题,并且使用data.table(ll=letters[1:21], gr=rep(1:6, times=rep(6:1)))
,您将生成24,883,200行(prod(factorial(DT[, .N, gr]$N))
)。
无论如何,如果必须绝对生成所有排列,这是一个选择:
library(data.table)
library(RcppAlgos)
DT <- data.table(ll=letters[1:6], gr=c(1,2,2,2,3,3))
DT <- data.table(ll=letters[1:21], gr=rep(1:6, times=rep(6:1)))
#prod(factorial(DT[, .N, gr]$N))
CJ.dt_1 <- function(...) {
Reduce(f=function(x, y) cbind(x[rep(1:nrow(x), times=nrow(y)),], y[rep(1:nrow(y), each=nrow(x)),]),
x=list(...))
} #CJ.dt_1
system.time(
ans <- do.call(CJ.dt_1, DT[, .(.(RcppAlgos::permuteGeneral(ll, .N))), gr]$V1)
)
# user system elapsed
# 16.49 4.63 21.15