R,data.table:查找列表的所有组合,排除与自身配对的每个元素

Question

我想有效地找到列表的所有组合,不包括每个元素与其自身的组合.例如,使用A,B,C,D列表查找除AA,BB,CC,DD之外的所有组合.

我可以使用这段代码看起来效率低下:

x <- c("A","B","C","D")
dt <- CJ(x,x)
dt <- dt[!V1==V2]

问题是第三行的运行时间大约是第二行的4倍.因此,对于像我的真实数据这样的大型列表,第2行和第3行可能需要很长时间.

我在Windows 7上使用data.table 1.9.6,R 3.2.2和R Studio.

非常感谢.

Answer 1

嗯,这是一个改进:

n = 1e4; x = seq(n)

# combn (variant of @Psidom's answer)
system.time({
  cn = transpose(combn(x, 2, simplify=FALSE))
  r  = rbind( setDT(cn), rev(cn) )
})
# takes forever, so i cut it off

# op's code
system.time({
  r0 = CJ(x,x)[V1 != V2]
})
#    user  system elapsed 
#    1.69    0.63    1.50 

# use indices in the final step
system.time({
  r1 = CJ(x,x)[-seq(1L, .N, by=length(x)+1L)]
})
#    user  system elapsed 
#    1.17    0.42    0.96 

还有一些:

# build it manually
system.time({
  xlen = length(x)
  r2 = data.table(rep(x, each = xlen), V2 = x)[-seq(1L, .N, by=xlen+1L)]
})
#    user  system elapsed 
#    3.03    0.60    2.79 

# ... or ...
system.time({
  xlen = length(x)
  r2 = data.table(rep(x, each = xlen-1L), rep.int(x, xlen)[-seq(1L, xlen^2, by=xlen+1L)])
})    
#    user  system elapsed 
#    2.79    0.25    3.07 

# build it manually special for the case of two cols
system.time({
  r3 = setDT(list(x))[, .(V2 = x), by=V1][ -seq(1L, .N, by=length(x)+1L) ]
})
#    user  system elapsed 
#    0.92    0.25    0.86 

# ... or ...
system.time({
  r4 = setDT(list(x))[, .(V2 = x[-.GRP]), by=V1]
})
#    user  system elapsed 
#    0.85    0.32    1.19

# verify
identical(r0, r1) # TRUE
identical(setkey(r0, NULL), r2) # TRUE
identical(setkey(r0, NULL), r3) # TRUE
identical(setkey(r0, NULL), r4) # TRUE

也许你可以通过用Rcpp编写自己的CJ来做得更好.值得注意的是整数(而不是字符)的一切都更快:

x = rep(LETTERS, 5e2)
system.time(CJ(x,x))
#    user  system elapsed 
#    7.06    1.81    6.61 


x = rep(1:26, 5e2)
system.time(CJ(x,x))
#    user  system elapsed 
#    3.39    0.88    2.95 

因此,如果x是字符向量,最好seq_along(x)用于组合任务,然后映射回字符值,就像x[V1]之后一样.