从Google Collections中查找Multiset中的前N个元素？

Question

一个Google Collections Multiset是一组带有计数的元素（即可能出现多次的元素）。

我经常需要进行以下操作:

1. 制作直方图 (完全等同于 Multiset)。
2. 从直方图中获取计数最高的前 N 个元素。

例如：前十个 URL (按提及次数排序)，前十个标签 (按应用次数排序)，...

针对 Google Collections Multiset，有什么经典方法可以实现第二点操作吗？

这里有一篇相关的博客文章，但那段代码不完全符合我的需求。首先，它返回了所有元素，而非仅返回前 N 个元素。其次，它会复制一份 Multiset (是否可以避免复制？)。第三，通常我需要一种确定性排序方式，即在计数相同时进行比较。其他注意事项：该方法不是静态的等等。

- dfrankow

Answer 1

我编写了基本满足您要求的功能的方法，但它们执行复制且缺少确定性的决定逻辑。它们目前是Google内部使用，但我们可能在某个时候开源它们。这个Guava 问题包含方法签名。

它们的算法类似于博客文章: 对条目列表进行排序。使用更好的选择算法会更快，但更复杂。

编辑: 自Guava 11以来，这已被实现。

- Jared Levy

---

如何使用它来获取前N个元素？ - Alexey Grigorev

Answer 2

为了让人们有另一种评论角度，我将发布一个略微修改过的博客文章版本：

package com.blueshiftlab.twitterstream.summarytools;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multiset;
import com.google.common.collect.Ordering;
import com.google.common.collect.Multiset.Entry;

public class Multisets {
    // Don't construct one
    private Multisets() {
    }

    public static <T> ImmutableList<Entry<T>> sortedByCount(Multiset<T> multiset) {
        Ordering<Multiset.Entry<T>> countComp = new Ordering<Multiset.Entry<T>>() {
            public int compare(Multiset.Entry<T> e1, Multiset.Entry<T> e2) {
                return e2.getCount() - e1.getCount();
            }
        };
        return countComp.immutableSortedCopy(multiset.entrySet());
    }

    public static <T> ImmutableList<Entry<T>> topByCount(Multiset<T> multiset,
            int max) {
        ImmutableList<Entry<T>> sortedByCount = sortedByCount(multiset);
        if (sortedByCount.size() > max) {
            sortedByCount = sortedByCount.subList(0, max);
        }

        return sortedByCount;
    }
}

- dfrankow

---

如果我理解正确的话，这个解决方案每次想要检索前N个元素时都会复制并排序整个集合。我不确定你的要求是什么，但堆排序解决方案在时间和空间上都比这个更好，所以我不确定有什么好处。 - danben

你在优化速度，而我则希望自己编写的代码行数最少。 - dfrankow

我明白了 - 从你的帖子中并不清楚，特别是你问了如何避免复制。 - danben

小心，你的比较器正在按计数降序排序。 - nimcap

好的观点。这是有意设计的，但没有明确指出。“top N”通常意味着降序排序。 - dfrankow

@dfrankow: 我知道，但如果我调用sortedByCount()，我会期望它是相反的方式 :) - nimcap