Java 集合性能问题

Question

我创建了一个需要两个 Collection<String> 的方法作为输入并将一个复制到另一个。

但是，我不确定是否应该在开始复制之前检查集合是否包含相同的元素，或者我是否应该不顾一切地进行复制。这是方法:

 /**
  * Copies from one collection to the other. Does not allow empty string. 
  * Removes duplicates.
  * Clears the too Collection first
  * @param src
  * @param dest
  */
 public static void copyStringCollectionAndRemoveDuplicates(Collection<String> src, Collection<String> dest) {
  if(src == null || dest == null)
   return;

  //Is this faster to do? Or should I just comment this block out
  if(src.containsAll(dest))
   return;

  dest.clear();
  Set<String> uniqueSet = new LinkedHashSet<String>(src.size());
  for(String f : src) 
   if(!"".equals(f)) 
    uniqueSet.add(f);

  dest.addAll(uniqueSet);
 }

也许删除

会更快

if(src.containsAll(dest))
    return;

因为这个方法无论如何都会遍历整个集合。

Answer 1

我会说:删除它!它是重复的“代码”，Set 正在执行相同的“contains()”操作，因此无需在此处对其进行预处理。除非你有一个巨大的输入集合和一个出色的 O(1) 测试 containsAll() ;-)

Set 足够快。它具有基于输入大小的 O(n) 复杂度(每个字符串一个 contains() 和(可能)一个 add() 操作)，如果 target.containsAll() 测试失败，则 contains() 执行两次对于每个字符串 -> 性能较差。

编辑

一些伪代码来可视化我的答案

void copy(source, dest) {
  bool:containsAll = true;
  foreach(String s in source) {  // iteration 1
    if (not s in dest) {         // contains() test
       containsAll=false
       break
    }
  }
  if (not containsAll) {
    foreach(String s in source) { // iteration 2
      if (not s in dest) {        // contains() test
        add s to dest
      }
    }
  }
}

如果所有源元素都在 dest 中，则对每个源元素调用一次 contains()。如果除最后一个源元素之外的所有元素都在 dest 中(最坏情况)，则 contains() 被调用 (2n-1) 次(n=源集合的大小)。但是带有额外测试的 contains() 测试的总数总是等于或大于没有额外测试的相同代码。

编辑 2假设我们有以下集合:

source = {"", "a", "b", "c", "c"}
dest = {"a", "b"}

首先，containsAll 测试失败，因为源中的空字符串不在目标中(这是代码中的一个小设计缺陷；))。然后创建一个临时集，它将是 {"a", "b", "c"}(空字符串和第二个“c”被忽略)。最后，您将所有内容添加到 dest 并假设 dest 是一个简单的 ArrayList，结果是 {"a", "b", "a", "b", "c"}。这是意图吗？一个更短的选择:

void copy(Collection<String> in, Collection<String> out) {
  Set<String> unique = new HashSet<String>(in);
  in.remove("");
  out.addAll(unique);
}