我目前正在處理一項必須優化一些代碼的作業。最慢的方法之一是在列表中查找重復元素的方法。場景中的重復項是這樣工作的：假設您有一個元素列表，每個元素都有兩個 ID，x 和 y。每個 x 值只能與一個 y 值配對，否則將其視為重復值，并且必須將原始值和重復值都添加到列表中。例如，元素列表是 (1,2) (1,2) (1,3) 在這種情況下，重復列表將包含 4 個元素，(1,2)(1,3) 和 (1, 2)( 1,3)，因為它們都具有相同的 x 值，但具有不同的 y 值。(1,2)(1,2) 不會被歸類為重復項，因為 x 和 y 值相同。當前代碼使用嵌套的 for 循環，它檢查兩個元素的 x 值是否相等但 y 值不同，但這很慢。在實際場景中，要素是供腎者與患者相匹配。所以每個捐贈者只能捐贈給一個病人。X 和 Y 是表示患者和捐贈者 ID 的字符串。如果有人知道這樣做的更快方法，將不勝感激:)
3 回答
繁華開滿天機
TA貢獻1816條經驗 獲得超4個贊
你可以試試這個：
Map<Integer, Map<Integer, Long>> mmap = linkTable.stream()
.collect(groupingBy(DonorsToPatientPair::getDonorID,
groupingBy(DonorsToPatientPair::getPatientID, counting())));
變量 mmap 現在包含一個鍵映射到該鍵到頻率的值映射。如果你想得到(d, p)的出現次數，你可以這樣得到：
long freq = mmap.get(d).get(p)
為了處理地圖，您可以使用如下代碼：
for (int donor : mmap.keySet()) {
Map<Integer, Long> patientMap = mmap.get(donor);
if (patientMap.size() < 2) {
continue; // no duplicates
}
// *** your code here ***
}
對于您自己的代碼，您在循環中擁有捐贈者和從患者到其頻率的地圖。剩下的工作應該很容易完成。
GCT1015
TA貢獻1827條經驗 獲得超4個贊
您可以使用 x 值作為排序條件對數組進行排序。然后將數組切成具有相同 x 值的較小數組對。然后，您使用當前的算法僅在較小的塊中本地查找重復項。雖然這仍然有嵌套循環，但它會執行得更快，因為搜索僅限于小數組，當 n 是元素數時，具有兩個嵌套循環的搜索的復雜度為 O(n*n)。
添加回答
舉報
0/150
提交
取消