r - R中帕累托前沿的快速计算

Question

所以我试图计算 R 中的帕累托前沿( http://en.wikipedia.org/wiki/Pareto_efficiency )并且能够做到，但是，我无法有效地做到这一点。特别是随着点对数量的增加，计算速度会大大减慢。

所以总的来说，我想要做的是检查所有非支配(或支配)对。现在我一直这样做的方法是找到所有这样的点对 xi > X
和 易 > 是 哪里 (xi, yi) 是一对和 X 和 是 代表所有点 x 和 y .现在，这部分工作非常快并且易于实现，但是，还有多个 的额外可能性。 x 值可能相同但它们会有不同 y 值所以在这种情况下我希望能够识别 x 具有最低值 y 值(反之亦然，对于具有相同 y 值但不同 x 值的点)。

为了说明这一点，这里有一张来自维基百科的图片:



所以基本上我希望能够识别位于红线上的所有点。

这是我的代码确实有效，但对于大型数据集效率很低:

#Example Data that actually runs quickly
x = runif(10000)
y = runif(10000)

pareto = 1:length(x)

for(i in 1:length(x)){
    cond1 = y[i]!=min(y[which(x==x[i])])
    cond2 = x[i]!=min(x[which(y==y[i])])
    for(n in 1:length(x)){
        if((x[i]>x[n]  &  y[i]>y[n]) | (x[i]==x[n] & cond1) | (y[i]==y[n] & cond2)){
            pareto[i] = NA
            break
        }
    }
}
#All points not on the red line should be marks as NA in the pareto variable

减速肯定来自计算点 (x[i]==x[n] & cond1) | (y[i]==y[n] & cond2)但我找不到解决方法或更好的 bool 表达式来捕获我想要的所有内容。非常感谢任何建议!

Answer 1

关注@BrodieG

system.time( {
    d = data.frame(x,y)
    D = d[order(d$x,d$y,decreasing=FALSE),]
    front = D[which(!duplicated(cummin(D$y))),]
} )

   user  system elapsed 
   0.02    0.00    0.02 

这是 0.86/0.02 = 43 倍快!