2

让我们D成为一个 data.frame，其中D$x包含实数和D$y布尔值，以及其他字段。

问题是对 的行进行排序，D使其D$x不递减，同时以一种使结果中不连续的数量最小化的方式打破联系D$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

如果 y 有一个最佳的重新排列，这不会给你完美的结果，但否则会起作用

D[order(D$x, D$y), ]
于 2013-11-06T15:37:31.970 回答
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 回答