Сортировка с разрывом связей, минимизирующая разрыв логического поля

Позволять D быть data.frame, с D$x содержащие действительные числа и D$y содержащий логические, среди других полей.

Проблема заключается в сортировке строк D чтобы D$x является неубывающим, при этом разрывая связи таким образом, чтобы свести к минимуму количество разрывов в результате D$y,

Есть ли простой быстрый способ сделать это в R?

Дополнительная информация

На языке, подобном C I, сначала нужно отсортировать по x, а затем последовательно передать результат с помощью 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.

РЕДАКТИРОВАТЬ: Мы можем предположить, что данные таковы, что плотность разрывов в результате будет низким: скажем, менее 1 разрыв на 1000 строк.

Источник

3 ответа

Решение

Гораздо более быстрое решение, чем последовательная итерация (если разрывов мало):

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) является оптимальным, а другой обычно тоже, в зависимости от данных.

Источник

Это не даст вам идеальных результатов, если есть оптимальная перестановка y, но в противном случае будет работать

D[order(D$x, D$y), ]
Источник

Решение грубой силы:

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 нет способа сделать это быстрее?

Источник
Другие вопросы по тегам