相关疑难解决方法(0)

给定一个包含一些键值对的数组：

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': 2},
  {'a': 1, 'b': 1, 'c': 1},
  {'a': 1, 'b': 1, 'c': 2},
  {'a': 2, 'b': 1, 'c': 1},
  {'a': 2, 'b': 1, 'c': 2}
]

我想找到这些对的交集。交叉意味着只留下那些可以被其他元素覆盖或唯一的元素。例如， {'a': 1, 'b': 1, 'c': 1}和{'a': 1, 'b': 1, 'c': 2}完全覆盖{'a': 1, 'b': 1}，而{'a': 2, 'b': 2}是唯一的。所以，在

[
  {'a': 1, 'b': 1},
  {'a': 2, 'b': 1},
  {'a': 2, 'b': …

所以我正在尝试计算帕累托前线(http://en.wikipedia.org/wiki/Pareto_efficiency)R并且能够做到,但是,我无法有效地做到这一点.特别是随着点对的数量增加,计算显着减慢.

所以一般来说,我想做的是检查所有非支配(或支配)对.现在,我这样做的方法是找到所有这样的点对,使得x _i > X 和y _i > Y,其中(x _i,y _i)是单对,X和Y表示所有点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) | …