newPropertiesFile.keySet().parallelStream() .filter(value -> oldPropertiesFile.keySet().parallelStream() .filter(entry -> oldPropertiesFile.get(entry).toString().equals(newPropertiesFile.get(value).toString())) .filter(values -> !values.equals(value)).count() > 0) .collect(Collectors.toMap(entryKey -> (String) entryKey, entryKey -> newPropertiesFile.get(entryKey).toString()));例如，我有mapA = {(1,'a'),(2,'b'),(3,'c')}并mapB = {(5,'a'),(6,'d'),(7,'c')} 比較兩個映射的 valueList，值'a'和'c'出現mapA在mapB它們的鍵是5和7resp。因此我需要 o/p:5,7我已經完成了上述操作并獲得了所需的輸出。但是 O(n^2) 的復雜度太高了。有什么優化方法嗎？一個更簡化的例子：mapA.keySet().parallelStream() .filter(v->mapB.keySet().parallelStream() .filter(e->mapB.get(v).equals(mapA.get(v))) .filter(v->!v.equals(v)).count()>0) .forEach(System.out::println);
1 回答
Smart貓小萌
TA貢獻1911條經驗 獲得超7個贊
讓我們總結一下這方面的一些變化，因為最好的解決方案只有在閱讀其他答案和評論后才會出現。
這個問題的簡化問題是這樣的。給定兩張地圖：
Map<Integer, String> mapA = Map.of(1, "a", 2, "b", 3, "c")
Map<Integer, String> mapB = Map.of(5, "a", 6, "d", 7, "c")
mapB找到對應于兩個映射中出現的值的鍵。這個問題的解決方案是這樣的（為清楚起見進行了編輯）：
Set<Integer> result = mapB.keySet().stream()
.filter(keyB -> mapA.keySet().stream()
.filter(keyA -> mapA.get(keyA).equals(mapB.get(keyB)))
.count() > 0)
.collect(toSet());
從本質上講，這就像兩個嵌套循環，循環遍歷每個映射的鍵。內層循環獲取每個鍵對應的值并計算匹配次數。如果至少有一個匹配項，則密鑰將通過過濾器傳遞到結果。
OP 對此并不滿意，并要求進行改進，尤其是在算法復雜性方面。如評論中所述，真正的問題可能有 15,000 個地圖條目。該算法的復雜度為 O(n^2)，并且隨著映射數量的增加，它的性能確實開始明顯下降。有一些可以改進的小方法，例如使用anyMatch而不是filterand ，但是鑒于Eritrean 的回答count > 0中提出的替代方案，這些不是必需的：
Set<Integer> result = mapB.entrySet().stream()
.filter(entry -> mapA.values().contains(entry.getValue()))
.map(Map.Entry::getKey)
.collect(toSet());
這更好，因為它使用containsmapAvalues()視圖上的操作，替換了先前解決方案的內部流。但是，地圖的值未編入索引，因此contains()對地圖的值進行操作的唯一方法是（可能）搜索每個條目。這比以前好一些，如果找到匹配項，contains()可以立即返回；但如果未找到匹配項，則必須搜索地圖的所有值。因此，平均而言，這種變化仍然在 O(n^2) 時間內運行。
緩解這種情況的一種方法是將 mapA 的值拉入HashSet. 這會將檢查從線性時間減少contains()到恒定時間，將整體復雜度從 O(n^2) 降低到 O(n)。那看起來像這樣：
Set<String> aValues = new HashSet<>(mapA.values());
Set<Integer> result = mapB.entrySet().stream()
.filter(entry -> aValues.contains(entry.getValue()))
.map(Map.Entry::getKey)
.collect(toSet());
這是一個很大的改進，但事實證明根本沒有必要使用流?；氐絾栴}陳述，它有一個子句“...兩個映射中都出現的值”。這實質上是在值集合上進行集合交集。在 Java 中進行交集的方法是使用retainAll方法。也就是說，給定兩個集合x和y，doingx.retainAll(y)將只保留x那些也出現在 中的元素y，并刪除其他元素。這本質上是一個集合的交叉點。為此，retainAll通常必須contains重復調用y，因此確保操作快速是個好主意——就像使用HashSet.
好的，如果我們將值集合相交，這會為我們提供值——但我們需要鍵。特別是，我們想要 mapB 的鍵。我們該怎么做？
事實證明，values()地圖的視圖支持刪除——確實retainAll如此——如果從中刪除了一個值，則會從底層地圖中刪除相應的條目。在這種情況下，我們可以從 mapB（或副本）開始，獲取其values()視圖，調用retainAll我們之前加載到HashSet. 這在 mapB 中僅留下與 mapA 具有共同值的條目。由于我們對鍵而不是條目感興趣，所以我們只獲取視圖keySet()。該代碼如下所示：
Set<String> aValues = new HashSet<>(mapA.values());
Map<Integer, String> mapBcopy = new HashMap<>(mapB);
mapBcopy.values().retainAll(aValues);
Set<Integer> result = mapBcopy.keySet();
這演示了如何在集合視圖上使用集合批量操作比使用流更簡單地完成某些任務。
添加回答
舉報
0/150
提交
取消