在Java中高效地比较两个对象列表

Question

在Java中高效地比较两个对象列表

4

我目前正在查看两个非常大的Peak对象列表，通过重写equals方法并循环遍历这两个列表，比较每个峰值与其他峰值。有没有更有效的方法来完成这个任务？我的列表可以包含约10,000个元素，这意味着最多10000 * 10000次比较。

我的峰值对象的代码：

public class Peak extends Object{

private final SimpleIntegerProperty peakStart;
private final SimpleIntegerProperty peakEnd;
private final SimpleIntegerProperty peakMaxima;
private final SimpleIntegerProperty peakHeight;
private final SimpleIntegerProperty peakWidth;
private final SimpleStringProperty rname;

public Peak(int peakStart, int peakEnd, int peakMaxima, int peakHeight, String rname) {
    this.peakStart = new SimpleIntegerProperty(peakStart);
    this.peakEnd = new SimpleIntegerProperty(peakEnd);
    this.peakMaxima = new SimpleIntegerProperty(peakMaxima);
    this.peakHeight = new SimpleIntegerProperty(peakHeight);
    this.peakWidth = new SimpleIntegerProperty(peakEnd - peakStart);
    this.rname = new SimpleStringProperty(rname);
}

public String getRname() {
    return rname.get();
}

public SimpleStringProperty rnameProperty() {
    return rname;
}

public int getPeakWidth() {
    return peakWidth.get();
}

public int getPeakHeight() {
    return peakHeight.get();
}

public int getPeakStart() {
    return peakStart.get();
}

public int getPeakEnd() {
    return peakEnd.get();
}

public int getPeakMaxima() {
    return peakMaxima.get();
}

@Override
public String toString() {
    return "Peak{" +
            "peakStart= " + peakStart.get() +
            ", peakEnd= " + peakEnd.get() +
            ", peakHeight= " + peakHeight.get() +
            ", rname= " + rname.get() +
            '}';
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    Peak peak = (Peak) o;

    if (!peakMaxima.equals(peak.peakMaxima)) return false;
    return rname.equals(peak.rname);
}

@Override
public int hashCode() {
    int result = peakMaxima.hashCode();
    result = 31 * result + rname.hashCode();
    return result;
}
}

以下是比较对象的循环代码。

 List<Peak> interestingPeaks = new ArrayList<>();

            if(peakListOne != null && peakListTwo != null){
                for(Peak peak : peakListOne){
                    for(Peak peak2 : peakListTwo){
                        if(peak.equals(peak2)){ //number one, check the rnames match
                            if((peak2.getPeakHeight() / peak.getPeakHeight() >= 9) || (peak.getPeakHeight() / peak2.getPeakHeight() >= 9)){
                                    interestingPeaks.add(peak);
                            }
                        }
                    }
                }
            }

            return interestingPeaks;

这段代码主要是匹配最大值的位置和字符串 rname，然后将峰值添加到 interestingPeaks 列表中，如果其中一个峰值的高度是另一个峰值的9倍以上。

- Sam

你尝试使用哈希了吗？ - flx

如果你对列表进行排序，你就可以更加聪明地进行比较。 - Peter Bruins

有一些我们不知道的条件可能会使您的算法更简单或更困难。列表是否可以排序，或者顺序是否重要？单个列表内允许峰值重复吗（也许可以使用HashSet）？有许多算法可以帮助您，但您必须看看可能的方法是否符合您的特定情况。 - mingos

列表在输入时未排序，但它们可以作为方法的一部分进行排序，没有任何理由不这样做。 - Sam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Biegeleisen · Accepted Answer

感谢您。如果这两个列表按最大值和名称排序，您可以简单地沿着这两个列表进行单一线性遍历，并逐个比较项目。如果这两个列表完全相等，则您永远不会找到来自这两个列表的不相等的一对项目。

List<Peak> p1;
List<Peak> p2;

p1.sort((p1, p2) -> {
    int comp = Integer.compare(p1.getPeakMaxima(), p2.getPeakMaxima());
    return comp != 0 ? comp : p1.getRname().compareTo(p2.getRname());
});

// and also sort the second list

现在我们只需要遍历两个列表并检查比较失败的情况即可：

for (int i=0; i < p1.size(); ++i) {
    if (!p1.get(i).equals(p2.get(i))) {
        System.out.println("peaks are not equal");
        break;
    }
}

这将一个 O(N^2) 的操作降低到了一个 O(N*lgN) 的操作，这是同时进行两个排序的代价（最后遍历列表的时间复杂度是 O(N)，但使用任一方法都可以忽略不计）。