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] 

問題は、3行目はセカンドラインとして実行するために約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]のような文字値。