0

我一直在使用这种方法从 Map 中获取前 100 个元素。有谁知道番石榴是如何实现这些的？

    Ordering<String> valueComparator = 
       Ordering.natural().onResultOf(
         Functions.forMap(WordCounts)).compound(Ordering.natural());

    ImmutableSortedMap<String, Integer> SortedWordCounts = 
      ImmutableSortedMap.copyOf(WordCounts, 
        Collections.reverseOrder(valueComparator));
    Map<String, Integer> TopWordCounts = 
    SortedWordCounts.headMap(SortedWordCounts.keySet().asList().
         get(100));

我在这里没有看到太多细节 http://guava-libraries.googlecode.com/svn/trunk/gwt-javadoc/com/google/common/collect/ImmutableSortedMap.html

我正在尝试考虑这是否效率低下以及是否应该使用像http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm这样的前 k 算法 要运行这样的算法，我必须将映射到一个数组，然后可能又回到一个映射，这让我觉得这可能不值得。

4

1 回答 1

6

所以，如果你用 Guava 存储计数，你真的应该使用Multiset. 如果你这样做了，那么你可以使用方便的方法Multisets.copyHighestCountFirst来获得一个从最高到最低计数顺序的多重集。

要获得这样的前 100 个元素，您可以编写

Multisets.copyHighestCountFirst(multiset).elementSet().asList().subList(0, 100);

它会在一行中返回ImmutableList前 100 个元素中的一个。

如果您想使用更高级的选择算法，Guava 已经将其实现为Ordering.greatestOfand Ordering.leastOf。这些使用您引用的选择算法的花哨变体，不需要将集合的 O(n) 副本复制到一个大数组中，但它仍然以线性时间运行。

如果你既需要元素又需要计数，你真的不应该尝试将 anImmutableSortedMap或类似的东西与查找元素的比较器一起使用；你应该复制到一个新的Multiset. 如果效率是我的首要任务，我会这样写：

Ordering<Multiset.Entry<E>> highestCountFirst = 
  new Ordering<Multiset.Entry<E>>() {
    @Override public int compare(Multiset.Entry<E> e1, Multiset.Entry<E> e2) {
      return Ints.compare(e1.getCount(), e2.getCount());
    }
  };
ImmutableMultiset.Builder<E> top100Builder = ImmutableMultiset.builder();
for (Multiset.Entry<E> topEntry : 
       highestCountFirst.greatestOf(multiset.entrySet(), 100)) {
  top100Builder.addCopies(topEntry.getElement(), topEntry.getCount());
}
return top100Builder.build();
于 2013-07-25T19:29:15.780 回答