从Map中找到前100个元素的最有效方法

Question

我一直在使用这种方法从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算法 运行这样的算法我必须转换映射到数组,然后可能回到地图,这让我觉得它可能不值得.

Answer 1

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

要获得这样的前100个元素,你可以写

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

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

如果你想使用一个更好的选择算法,Guava已经实现了Ordering.greatestOf和Ordering.leastOf.这些使用了你所引用的选择算法的花式裤子变体,它不需要将集合的O(n)副本变成大数组,但它仍然以线性时间运行.

如果你需要元素和计数,你真的不应该尝试使用ImmutableSortedMap比较器来查找元素; 你应该复制到一个新的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();