Использование мультимножества Guava или Collections.frequency()?

Question

Я использовал Multiset, чтобы иметь свободный доступ к частоте элементов, но я понимаю, что есть Collections#frequency(Collection<?>, Object), который делает то же самое для любой коллекции. Какой смысл использовать Multiset? Здесь проблема производительности?

Answer 1

гуавы документация Multiset#count() должен сказать:

Заметим, что для Object.equals (java.lang.Object) основе мультимножеством, это дает тот же результат, как Collections.frequency (java.util .Collection, java.lang.Object) (который предположительно будет работать хуже).

Итак, да, я подозреваю, что это проблема.

Я думаю, что Multiset#count более эффективен, потому что Collections#frequency выполняет итерацию по всей коллекции. Для объекта o, частота которого вы проверяете, он проходит через все элементы e в коллекции и проверяет (o == null ? e == null : o.equals(e)).

Для Multiset (который является интерфейсом), точная реализация count зависит от класса. Например, если это HashMultiset, то он подкрепляется HashMap. Подробнее о том, как это более эффективно, чем повторение всей коллекции, см. В этом ответе: How does a Java HashMap handle different objects with the same hash code?.

Guava code выглядит следующим образом

public int count(@Nullable Object element) { 
    Count frequency = Maps.safeGet(backingMap, element); 
    return (frequency == null) ? 0 : frequency.get(); 
} 

Аналогично, для TreeMultiset, который поддерживает упорядоченность ее элементов и опирается на дерево AVL, count могут быть получены в O (Log (N)) шагов вместо O (n), где n - размер коллекции. Guava code выглядит следующим образом:

public int count(@Nullable Object element) { 
    try { 
     @SuppressWarnings("unchecked") 
      E e = (E) element; 
      AvlNode<E> root = rootReference.get(); 
      if (!range.contains(e) || root == null) { 
       return 0; 
      } 
     return root.count(comparator(), e); 
    } catch (ClassCastException e) { 
      return 0; 
    } catch (NullPointerException e) { 
      return 0; 
    } 
}