Java集合性能问题

5

我创建了一个方法,它接受两个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;

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


2
只是一条小评论,与你的问题无关:target 和 des 有相似的意思。既然你正在将非空字符串从 target 复制到 dest,也许可以将其重命名为 src? - Miserable Variable
6个回答

7
我认为:删除它!这是重复的“代码”,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
      }
    }
  }
}

如果所有的源元素都在目标中,则对于每个源元素,调用一次contains()。如果除了最后一个源元素之外的所有源元素都在dest中(最坏情况),则会调用contains()(2n-1)次(其中n=源集合的大小)。 但是,带有额外测试的contains()测试总数始终等于或大于没有额外测试的相同代码。
编辑2 假设我们有以下集合:
source = {"", "a", "b", "c", "c"}
dest = {"a", "b"}

首先,containsAll测试失败了,因为源中的空字符串不在目标中(这是你代码中的一个小设计缺陷;))。然后,您创建了一个临时集合,它将是{"a", "b", "c"}(忽略了空字符串和第二个“c”)。最后,您将所有内容添加到目标中,并假设目标是一个简单的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);
}

假设我们移除Set,只创建一个接受Collection<T>的副本,那么在添加之前检查相等性是否可行? - Shervin Asgari

3
containsAll()方法无法解决当targetdest拥有更多元素的情况:
target: [a,b,c,d]
dest: [a,b,c]
target.containsAll(dest)为真,因此dest为[a,b,c],但实际应该是[a,b,c,d]。
我认为以下代码更加优雅:
Set<String> uniqueSet = new LinkedHashSet<String>(target.size());
uniqueSet.addAll(target);
if(uniqueSet.contains(""))
    uniqueSet.remove("");

dest.addAll(uniqueSet);

同意... 我甚至会跳过对contains的调用。 - Sean Owen
谢谢,我没有想到。实际上,目标很可能拥有比目的地更多的元素。 - Shervin Asgari

2

如果很重要的话,您可以进行基准测试。我认为调用containsAll()可能没有什么帮助,但这可能取决于两个集合有多少相同的内容。

不过,这段代码非常混乱。它试图将新的项添加到dest中?那么为什么要首先清除它呢?只需将新的uniqueSet返回给调用者,而不必费心处理。而且您的containsAll()检查是否颠倒了?


很有可能这些集合具有相同的内容,并且至少被调用了10次。 - Shervin Asgari

1

这段代码阅读起来很困难,而且效率不高。参数“dest”很令人困惑:它被作为参数传递,然后被清空,最后把结果添加到其中。那么作为参数的意义何在呢?为什么不简单地返回一个新集合呢?我唯一能看到的好处就是调用者可以确定集合类型。这是必要的吗?

我认为,可以将这段代码更清晰并且可能更高效地重写如下:

public static Set<String> createSet(Collection<String> source) {
    Set<String> destination = new HashSet<String>(source) {
        private static final long serialVersionUID = 1L;

        public boolean add(String o) {
            if ("".equals(o)) {
                return false;
            }
            return super.add(o);
        }
    }; 
    return destination;
}

另一种方法是创建自己的集合类型:

public class NonEmptyStringSet extends HashSet<String> {
    private static final long serialVersionUID = 1L;

    public NonEmptyStringSet() {
        super();
    }

    public NonEmptyStringSet(Collection<String> source) {
        super(source);
    }

    public boolean add(String o) {
        if ("".equals(o)) {
            return false;
        }
        return super.add(o);
    }
}

使用方法:

createSet(source);
new NonEmptyStringSet(source);

返回集合更高效,因为您不必先创建临时集合,然后将所有内容添加到目标集合中。

NonEmptyStringSet类型的好处是您可以继续添加字符串并仍然进行空字符串检查。

编辑1:

删除“if(src.containsAll(dest))return;”代码会在使用source == dest调用该方法时引入“错误”。结果是源将为空。例如:

Collection<String> source = new ArrayList<String>();
source.add("abc");
copyStringCollectionAndRemoveDuplicates(source, source);
System.out.println(source);

编辑2:

我进行了一个小基准测试,结果显示我的实现比你初始实现的简化版本快大约30%。对于你的初始实现,这个基准测试是最优情况,因为目标集合为空,所以不必清除它。此外,请注意我的实现使用 HashSet 而不是 LinkedHashSet,这使得我的实现速度更快。

基准测试代码:

public class SimpleBenchmark {
public static void main(String[] args) {
    Collection<String> source = Arrays.asList("abc", "def", "", "def", "", 
            "jsfldsjdlf", "jlkdsf", "dsfjljka", "sdfa", "abc", "dsljkf", "dsjfl", 
            "js52fldsjdlf", "jladsf", "dsfjdfgljka", "sdf123a", "adfgbc", "dslj452kf", "dsjfafl", 
            "js21ldsjdlf", "jlkdsvbxf", "dsfjljk342a", "sdfdsa", "abxc", "dsljkfsf", "dsjflasd4" );

    int runCount = 1000000;
    long start1 = System.currentTimeMillis();
    for (int i = 0; i < runCount; i++) {
        copyStringCollectionAndRemoveDuplicates(source, new ArrayList<String>());
    }
    long time1 = (System.currentTimeMillis() - start1);
    System.out.println("Time 1: " + time1);


    long start2 = System.currentTimeMillis();
    for (int i = 0; i < runCount; i++) {
        new NonEmptyStringSet(source);
    }
    long time2 = (System.currentTimeMillis() - start2);
    System.out.println("Time 2: " + time2);

    long difference = time1 - time2;
    double percentage = (double)time2 / (double) time1;

    System.out.println("Difference: " + difference + " percentage: " + percentage);
}

public static class NonEmptyStringSet extends HashSet<String> {
    private static final long serialVersionUID = 1L;

    public NonEmptyStringSet() {
    }

    public NonEmptyStringSet(Collection<String> source) {
        super(source);
    }

    @Override
    public boolean add(String o) {
        if ("".equals(o)) {
            return false;
        }
        return super.add(o);
    }
}

public static void copyStringCollectionAndRemoveDuplicates(
        Collection<String> src, Collection<String> dest) {
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size());
    for (String f : src)
        if (!"".equals(f))
            uniqueSet.add(f);

    dest.addAll(uniqueSet);
}
}

1
  1. 参数名太过混乱。 desttarget 的意思几乎相同。最好选择像 destsource 这样的名称。这将使事情更加清晰,即使对你来说也是如此。

  2. 我有一种感觉(不确定是否正确),你使用了错误的集合 API。接口 Collection 并没有说明其元素的唯一性,但你却添加了这个特性。

  3. 修改作为参数传递的集合并不是最好的想法(但通常情况下取决于具体情况)。在一般情况下,可变性是有害且不必要的。此外,如果传递的集合是不可修改/不可变的,那该怎么办呢?最好返回新的集合,然后再修改传入的集合。

  4. Collection 接口有 addAllremoveAllretainAll 方法。你先尝试过它们吗?你对以下代码进行了性能测试吗:

    Collection<String> result = new HashSet<String> (dest);
    result.addAll (target);
    

    或者

    target.removeAll (dest);
    dest.addAll (target);
    

0

我并不是很清楚为什么你想要这个方法,但是假设它是有价值的,我会按照以下方式实现:

public static void copyStringCollectionAndRemoveDuplicates(
        Collection<String> src, Collection<String> dest) {
    if (src == dest) {
         throw new IllegalArgumentException("src == dest");
    }
    dest.clear();
    if (dest instanceof Set) {
        dest.addAll(src);
        dest.remove("");
    } else if (src instance of Set) {
        for (String s : src) {
            if (!"".equals(s)) {
                dest.add(s);
            }
        }
    } else {
        HashSet<String> tmp = new HashSet<String>(src);
        tmp.remove("");
        dest.addAll(tmp);
    }
}

备注:

  1. 在所有情况下,此方法不会保留src参数中元素的顺序,但方法签名表明这是无关紧要的。
  2. 我故意没有检查null。如果提供了null作为参数,则存在错误,并且正确的做法是允许抛出NullPointerException
  3. 尝试将集合复制到其自身也是一个错误。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接