R，data.table：找到排除與其自身配對的每個元素的列表的所有組合

Question

我想高效地找到列表的所有組合，但不包括每個元素的組合。例如，用A，B，C，D的列表查找除A-A，B-B，C-C，D-D以外的所有組合。

我能在什麼似乎是使用此代碼的低效的方式做到這一點：

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

的問題是，第三行需要約4倍，只要作爲第二線運行。因此，對於像我的真實數據這樣的大型列表，第2行和第3行可能需要很長時間。

我使用data.table 1.9.6，R 3.2.2，和R工作室在Windows 7

非常感謝。

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 

也許你可以做一個小通過編寫自己的CJ與RCPP更好。這也可能是值得注意的是，一切都以整數（而不是字符）速度快：

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]。