2

他のフィールドの中でも特に、実数を含み、ブール値を含むdata.frameDとします。D$xD$y

問題は、結果の不連続の数を最小限に抑える方法でタイを壊しながら、減少しないDように の行をソートすることです。D$xD$y

Rでこれを達成するための簡単で速い方法はありますか?

詳しくは

CI のような言語では、最初に x で並べ替え、次に 2 状態 FSM を使用して結果を順次渡し、不連続性を可能な限り解決します。しかし、R では、何千もの行を順次処理する場合、反復処理によって不要なオーバーヘッドが発生することが予想されます。

正しい結果の例:

D$x  D$y
1    FALSE
1    FALSE
1    TRUE
1    TRUE
1.2  TRUE
1.5  TRUE
1.5  FALSE

間違った結果の例:

D$x  D$y
1    TRUE
1    FALSE
1    TRUE
1    FALSE
1.2  TRUE
1.5  FALSE
1.5  TRUE

この例では、正しい結果には 2 つの不連続点があり、間違った結果には 6 つの不連続点があります。

編集: データは、結果の不連続の密度が低くなるようなものであると想定できます: たとえば、1000 行あたりの不連続は 1 つ未満です。

4

3 に答える 3

0

ブルート フォース ソリューション:

sortForMaxContY <- function(D,initialY){
    n <- nrow(D)

    D <- D[order(D$x),]

    x <- c(D$x,Inf)
    whichT <- c(which(D$y),n+1)
    whichF <- c(which(!D$y),n+1)

    finalOrder <- rep(0,n) # allocate space
    lastY <- initialY
    iT <- 1
    iF <- 1
    for(i in 1:n){
        wT <- whichT[iT]
        wF <- whichF[iF]
        chooseT <- sign(x[wF]-x[wT])+lastY-0.5>0
        w <- ifelse(chooseT, wT, wF)
        finalOrder[i] <- w
        lastY <- D$y[w]
        iT <- iT + chooseT
        iF <- iF + !chooseT
    }

    return(D[finalOrder,])
}

sortForMaxContY(D,T)データによっては、とsortForMaxContY(D,F)のどちらかが最適であり、通常はもう一方も最適です。

Rにはこれをより速く行う方法はありませんか?

于 2013-11-07T12:39:09.170 に答える
0

逐次反復よりもはるかに高速なソリューション (不連続がまばらな場合):

sortForMaxContY <- function(D,initialY){
    n <- nrow(D)
    D <- D[order(D$x),]

    xChanges <- D$x[-1]!=D$x[-n]
    isLastOfXVal <- c(xChanges,T)
    rankOfXVal <- cumsum(c(T,xChanges))

    oldFinalYs <- NA
    finalYs <- D$y[isLastOfXVal]
    while(!identical(finalYs,oldFinalYs)){
        finalYOfPrecedingXVal <- c(initialY,finalYs)[rankOfXVal]
        oldFinalYs <- finalYs
        D <- D[order(D$x,xor(finalYOfPrecedingXVal,D$y)),]
        finalYs <- D$y[isLastOfXVal]
    }
    return(D)
}

sortForMaxContY(D,T)データによっては、とsortForMaxContY(D,F)のどちらかが最適であり、通常はもう一方も最適です。

于 2013-11-07T17:54:20.337 に答える