番石榴Sets.intersection性能差

Question

我今天在生产中遇到了一个奇怪的问题。虽然我喜欢番石榴，但我遇到了一个用例，其中番石榴的Sets.intersection()表现很差。我编写了一个示例代码：

Set<Long> cache = new HashSet<>();
for (long i = 0; i < 1000000; i++) {
    cache.add(i);
}
Set<Long> keys = new HashSet<>();
for (long i = 0; i < 100; i++) {
    keys.add(i);
}
long start = System.currentTimeMillis();
Set<Long> foundKeys = new HashSet<>();
for (Long key : keys) {
    if (cache.contains(key)) {
        foundKeys.add(key);
    }
}
System.out.println("Java search: " + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
SetView<Long> intersection = Sets.intersection(keys, cache);
System.out.println("Guava search: " + (System.currentTimeMillis() - start));

我尝试创建一个类似的生产场景，其中我有一个密钥缓存，我正在寻找缓存中的所有密钥。奇怪的是，番石榴搜索比Java搜索花费的时间要长得多。在运行这个之后，我得到了：

Java search: 0
Guava search: 36

有人能说出为什么这不适合我的用例，或者在番石榴中有bug吗？

Answer 1

事实证明，问题是对SetView.size()的多次调用。由于SetView是两个集合的交集的(活动)视图，因此每次都需要重新计算交集大小。

public static <E> SetView<E> intersection( final Set<E> set1, final Set<?> set2) {
//...
  return new SetView<E>() {
    @Override public Iterator<E> iterator() {
      return Iterators.filter(set1.iterator(), inSet2);
    }
    @Override public int size() {
      return Iterators.size(iterator());
    }
    //...
  };
}

从这里可以看到，在这种情况下，重新计算的意思是在整个视图中迭代，这可能很费时。

因此，解决这个问题的方法要么是确保只调用一次size()并存储该值(如果您知道底层集不会改变)，要么通过ImmutableSet.copyOf()创建一个交集的副本(例如)。