我目前正在周遊兩個非常大的Peak Objects清單,方法是覆寫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 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比對,rname隻是一個字元串.然後,如果一個峰的高度比另一個峰高9倍,則将該峰追加到有趣的峰清單中.
解決方法:
贊賞的是,如果兩個清單是按最大值和名稱排序的,則可以簡單地沿兩個清單進行一次線性傳遞,并比較各個項目.如果兩個清單實際上完全相等,那麼您将永遠不會從兩個不相等的清單中找到一對.
List p1;
List 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),并且兩種方法都可以忽略不計) .
标簽：performance,java
來源： https://codeday.me/bug/20191025/1927037.html