0

このメソッドを使用して、マップからカウントで上位 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 個の要素を 1 行で返します。

より洗練された選択アルゴリズムを使用したい場合、Guava は既にそれをOrdering.greatestOfおよびとして実装していOrdering.leastOfます。これらは、コレクションの O(n) コピーを大きな配列に必要としない、あなたが引用した選択アルゴリズムの派手なバリエーションを使用しますが、それでも線形時間で実行されます。

ImmutableSortedMap要素とカウントの両方が必要な場合は、要素を検索するコンパレータでan またはそのようなものを使用しようとしないでください。新しい にコピーする必要があります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 に答える