Реализация горизонтального запроса или эффективной границы

Ответ 1

Эта проблема называется "skyline query" администраторами баз данных (они могут иметь другие алгоритмы) и "эффективной границей" экономистов. Построение данных может дать понять, что мы ищем.

n <- 40
d <- data.frame(
  x = rnorm(n),
  y = rnorm(n)
)
# We want the "extreme" points in the following plot
par(mar=c(1,1,1,1))
plot(d, axes=FALSE, xlab="", ylab="")
for(i in 1:n) {
  polygon( c(-10,d$x[i],d$x[i],-10), c(-10,-10,d$y[i],d$y[i]), 
  col=rgb(.9,.9,.9,.2))
}

Алгоритм выглядит следующим образом: сортировка точек вдоль первой координаты, сохраняйте каждое наблюдение, если оно не хуже последнего сохраненного.

d <- d[ order(d$x, decreasing=TRUE), ]
result <- d[1,]
for(i in seq_len(nrow(d))[-1] ) {
  if( d$y[i] > result$y[nrow(result)] ) {
    result <- rbind(result, d[i,])  # inefficient
  } 
}
points(result, cex=3, pch=15)

Ответ 2

Изменить (2015-03-02):. Для более эффективного решения см. Patrick Roocks rPref, пакет для "Предпочтения базы данных и вычисления в режиме Skyline" (также в приведенном ниже ответе). Чтобы показать, что он находит то же решение, что и мой код здесь, я приложил пример, используя его, к моему первоначальному ответу здесь.

Повторение Vincent Zoonekynd просветительского ответа, здесь алгоритм, который полностью векторизован и, вероятно, более эффективен:

set.seed(100)
d <- data.frame(x = rnorm(100), y = rnorm(100))

D   <- d[order(d$x, d$y, decreasing=TRUE), ]
res <- D[which(!duplicated(cummax(D$y))), ]
#             x         y
# 64  2.5819589 0.7946803
# 20  2.3102968 1.6151907
# 95 -0.5302965 1.8952759
# 80 -2.0744048 2.1686003


# And then, if you would prefer the rows to be in 
# their original order, just do:
d[sort(as.numeric(rownames(res))), ]
#            x         y
# 20  2.3102968 1.6151907
# 64  2.5819589 0.7946803
# 80 -2.0744048 2.1686003
# 95 -0.5302965 1.8952759

Или, используя пакет rPref:

library(rPref)
psel(d, high(x) | high(y))
#             x         y
# 20  2.3102968 1.6151907
# 64  2.5819589 0.7946803
# 80 -2.0744048 2.1686003
# 95 -0.5302965 1.8952759

Ответ 3

Вот решение sqldf, где DF - это кадр данных данных:

library(sqldf)
sqldf("select * from DF a
 where not exists (
   select * from DF b
   where b.Col1 >= a.Col1 and b.Col2 >  a.Col2  
      or b.Col1 >  a.Col1 and b.Col2 >= a.Col2
 )"
)

Ответ 4

Этот вопрос довольно старый, но между тем есть новое решение. Надеюсь, здесь хорошо сделать саморекламу: я разработал пакет rPref, который делает эффективное вычисление Skyline из-за алгоритмов С++. С установленным пакетом rPref запрос из вопроса может быть выполнен через (предполагается, что df - это имя набора данных):

library(rPref)
psel(df, high(Col1) | high(Col2))

Это удаляет только те кортежи, где некоторые другие кортежи лучше в обоих измерениях.

Если требуется, чтобы другой кортеж был строго лучше всего в одном измерении (и лучше или равном в другом измерении), вместо этого используйте high(Col1) * high(Col2).

Ответ 5

В одной строке:

d <- matrix(c(2, 3, 4, 7, 5, 6), nrow=3, byrow=TRUE)
d[!apply(d,1,max)<max(apply(d,1,min)),]

     [,1] [,2]
[1,]    4    7
[2,]    5    6

Изменить: В свете вашей точности в ответе jbaums, здесь, как проверить оба столбца отдельно.

d <- matrix(c(2, 3, 3, 7, 5, 6, 4, 8), nrow=4, byrow=TRUE)
d[apply(d,1,min)>min(apply(d,1,max)) ,]

     [,1] [,2]
[1,]    5    6
[2,]    4    8

Ответ 6

d <- matrix(c(2, 3, 4, 7, 5, 6), nrow=3, byrow=TRUE)
d2 <- sapply(d[, 1], function(x) x < d[, 1]) & 
      sapply(d[, 2], function(x) x < d[, 2])
d2 <- apply(d2, 2, any)
result <- d[!d2, ]