洞察集合removeAll方法

我有一個大小列表〜200k ..我在篩選列表時遇到了一些問題。洞察集合removeAll方法

下面是執行：

public List<> filterList(List<> listToBeFiltered){ 
List<> removeElementsFromList = listToBeFiltered.parallelStream() 
            .filter(//some filtering logic) 
            .collect(Collectors.toList()); 
listToBeFiltered.removeAll(removeElementsFromList); 
return listToBeFiltered; 
}

我面對的代碼的問題是，該方案將在聲明的removeAll時removeElementsFromList接近listToBeFiltered的規模仍然停留。任何洞察/替代解決方案，非常感謝。

來源

2015-10-20 user3704576

的問題是，所述x.removeAll(y)操作O（N×M），其中Ñ是集合x的大小，和米是集合的大小y（即，O（ | x |×| y |））。

removeAll方法基本上是遍歷整個列表中的每個元素y，檢查x中的每個元素是否恰好相等，如果是，則刪除它。如果你一次就能做到這一點，效率會更高。

假設你正在使用Java 8，有一個更有效的方式來做到這一點：

List<Integer> xs = new ArrayList<>(); 
// TODO: initialize xs with a bunch of values 
List<Integer> ys = new ArrayList<>(); 
// TODO: initialize ys with a bunch of values 
Set<Integer> ysSet = new HashSet<>(ys); 
List<Integer> xsPrime = xs.stream() 
    .filter(x -> !ysSet.contains(x)) 
    .collect(Collectors.toList());

爲大小100K的xs和大小66k的ys，使用removeAll花了大約5500ms，而使用以上方法只需要約8ms。由於removeAll的二次複雜性，我預計當您擴展到200k時，差異會更加明顯。

與此相反，以上所使用的過濾器版本複雜性將是O（N + M），因爲它O（米）建立的所有值的HashSet在ys，然後O（n）遍歷所有xs的值以確保新的ysSet中沒有包含任何值。（當然，這是假設一個HashSet查找是O（1）的。）

再回首你的問題，我知道你已經在使用filter ......在這種情況下，我建議只是反轉的過濾邏輯，然後重新傳入的列表的值過濾的值：

public List<> filterList(List<> listToBeFiltered){ 
    List<> filteredList = listToBeFiltered.parallelStream() 
     .filter(/* some inverted filtering logic */) 
     .collect(Collectors.toList()); 
    listToBeFiltered.clear(); 
    listToBeFiltered.addAll(filteredList); 
    return listToBeFiltered; 
}

如果你不需要變異原始列表，那麼你可以直接返回filteredList。（這將是我的首選解決方案呢。）

我只是又跑我的測試，這一次我補充說，使用一個循環，而不是流的另一個版本：

Set<Integer> ysSet = new HashSet<>(ys); 
List<Integer> xsPrime = new ArrayList<>(); 
for (Integer x : xs) { 
    if (!ysSet.contains(x)) { 
     xsPrime.add(x); 
    } 
} 
return xsPrime;

這個版本中完成大約7ms而不是8ms。由於這隻比流版本稍快（特別是考慮到使用removeAll的原始版本慢了3個數量級），我會堅持使用流版本 - 尤其是因爲您可以利用並行性（因爲您已經在做與parallelStream）。

來源

2015-10-20 04:09:24 DaoWen

洞察集合removeAll方法

回答

相關問題