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