什么是最坏的情况大哦使用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

回答

相关问题