Guava Sets.intersection плохая производительность

Question

У меня возникла странная проблема в производстве сегодня. Хотя я люблю Гуаву, я столкнулся с прецедентом, в котором Sets.intersection() Guava играл довольно плохо. Я написал пример кода:

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() (например).