什麼是最壞的情況大哦使用list.retainAll

static List<String> common(String[] A, String[] B){ 
    Collection<String> listone = new ArrayList<String>(Arrays.asList(A)); 
    List<String> sorted = new ArrayList<String>(Arrays.asList(B)); 
    sorted.retainAll(listone); 
return sorted; 
}

我已經試過尋找API的源代碼;但我找不到任何的list.retainAll方法。什麼是最壞的情況大哦使用list.retainAll

但是我確信它是O（n）。那是對的嗎？

來源

2015-02-11 Bryce

答案取決於作爲參數retainAll傳入的集合的類型。下面是從Open JDK一個實現：

public boolean retainAll(Collection<?> c) { 
    boolean modified = false; 
    Iterator<E> e = iterator(); 
    while (e.hasNext()) { 
     if (!c.contains(e.next())) { 
      e.remove(); 
      modified = true; 
     } 
    } 
    return modified; 
}

這裏是的情況下的定時時去除是O（1）：

如果c.contains(v)飾面在O（1），然後retainAll是O（N ）。
如果contains是O（Log M），那麼retainAll是O（N * Log M）。
如果contains是O（M），那麼retainAll是O（N * M）。

如果您計劃叫retainAll的大集合，性能是至關重要的，你可能會更好爲構建列表中HashSet被保留。加速可能很重要。

Set<String> temp = new HashSet<String>(b); 
a.retainAll(temp);

注：ArrayList<T>has its own implementation of retainAll，因爲它去不去掉個別元素，改寫元素，它希望保持到列表中的初始部分，然後將所有丟棄的「尾巴」的元素在一次在O（1）。結合上面的HashSet<T>，這將爲您提供一個時間爲O（M + N）和空間爲O（M）的算法。

來源

2015-02-11 01:49:32 dasblinkenlight

對於ArrayList，'e.remove（）'也是線性的。我認爲這取決於「被保留者」的類型以及指定的藏品。最好的情況是線性的，例如'LinkedList' retainee和一個指定的'HashSet'。 – msandiford 2015-02-11 01:53:26

@msandiford感謝您的好評！我添加了更多信息來解釋這一點。 – dasblinkenlight 2015-02-11 02:05:15

@dasblinkenlight：'ArrayList'有它自己的非默認'retainAll'實現，它運行在O（NM）中。 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.retainAll%28java.util.Collection%29 – 2015-02-11 02:14:12

看起來最壞的情況是O(size A * size B)或O(nm)。這是因爲要保留所有在sorted中的每個項目，並將其與listone（使用迭代器）中的每個項目進行比較。

最糟糕的是，如果沒有項目是相似的，那麼會發生這種情況。但是，如果sorted中的所有項目都朝向迭代器的末尾listone，那麼這也將「幾乎」發生。

來源

2015-02-11 01:50:32 Dish

什麼是最壞的情況大哦使用list.retainAll

回答

相關問題