番石榴Sets.intersection表现不佳

Question

我今天在制作中遇到了一个奇怪的问题.虽然我喜欢Guava,但我遇到了一个Guava's 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

任何人都可以告诉为什么这不适合我的用例或番石榴是否有错误？

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()(例如).