最下位ペアシーケンシャル結合データテーブル

Question

私は2つの列を持つセットを持っています。行は値の対（a、b）です。

require(data.table)   
dt<-data.table(a=c(1,11,11,2,7,5,6), b = c(2,9,8,6,5,3,3)) 

各値のペアに最低の番号を割り当てたいとします。 しかし、値の1つが新しい行に再び現れる場合は、新しいペアと再度比較し、履歴の最低値を選択する必要があります。

res.dt<-data.table(a=c(1,11,11,2,7,5,6), b = c(2,9,8,6,5,3,3), res=c(1,9,8,1,5,3,1))   

    a b res 
1: 1 2 1 
2: 11 9 9 
3: 11 8 8 
4: 2 6 1 
5: 7 5 5 
6: 5 3 3 
7: 6 3 1 

Answer 1

は異なる問題を述べる：各行Iために、我々は反復列の最小値J < = とresを更新する必要がI（a_iを結果は、このいずれかでなければなりません、b_i）と（a_j、b_j）は空ではない交差を有する。私たちは、data.tableでnon-equi joins（V> = 1.9.8）で効率的にこれを行うことができます

が、この機能は、単一の要素の比較（>、>=、==、<=、または<）を可能にするので、私たちは、交差点を見つける必要があります（a_i、a_j）、（a_i、b_j）、（b_i、a_j）、（b_i、b_j）を別々に比較することにより、

dt[, `:=`(idx=.I, res=pmin(a,b), prev_res=NA)] 

while (dt[, !identical(res, prev_res)]) { 
    dt[, prev_res:= res] 

    # Use non-equi joins to update 'res' for intersecting pairs downstream 
    dt[dt[, .(i.a=a, i.res=res, i=.I)], on=.(a==i.a, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.a=a, i.res=res, i=.I)], on=.(b==i.a, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.b=b, i.res=res, i=.I)], on=.(a==i.b, idx > i), res:= pmin(res, i.res)] 

    dt[dt[, .(i.b=b, i.res=res, i=.I)], on=.(b==i.b, idx > i), res:= pmin(res, i.res)] 

} 

結果：

> dt[, .(a,b,res)] 
#  a b res 
# 1: 1 2 1 
# 2: 11 9 9 
# 3: 11 8 8 
# 4: 2 6 1 
# 5: 7 5 5 
# 6: 5 3 3 
# 7: 6 3 1 

（。これらのペアの少なくとも一方が同一の要素が含まれている場合は、交差点があります）これは、反復全体の歴史を占め、その結果が収束したときに我々が停止することができますを行います