1

有没有一种有效的方法可以从排序的多重集（TreeMultiset）中获取 n 个较高的条目？

为了说明我的意思，我发布了我效率低下的解决方案：

public SortedMultiset<DataTuple> headMultiset(int upperBound, BoundType boundType){
    int i=0;
    DataTuple act= this.coreData.firstEntry().getElement();
    Iterator<DataTuple> itr = this.coreData.iterator();
    while(i<=upperBound){
        act = itr.next();
        i+=this.coreData.count(act);
    }
    return headMultiset(act, boundType);
}

在这个例子中，DataSet 可以看作是 Object，而 this.coreData 是下属的 TreeMultiset。

我对这个话题真的很陌生，所以各种评论将不胜感激。

4

2 回答 2

1

我不是 100% 确定您正在寻找什么结果。举个例子：假设多重集的内容为 [5 xa, 3 xb, 7 xc, 2 xd, 5 xe]。（如在 Multiset.toString() 中，我正在编写“count x object”来表示对象的出现次数。）如果我正确理解了问题，如果 n 为 5，那么您想要的结果是 [5 xa]，对吗？

（也不清楚您是否希望结果多重集的大小为“round”。例如：如果在上述多重集中 n 为 6，您想要 [5 xa, 1 xb]、[5 xa] 还是 [5 xa, 3 xb] ?)

目前，我假设你想要四舍五入，也就是说，你会期望 [5 xa, 3 xb]。那么你的答案就不是那么遥远了，虽然我认为它写的有点错误。我会这样写：

public <E> SortedMultiset<E> takeElements(SortedMultiset<E> multiset, int n) {
    if (n == 0) { return ImmutableSortedMultiset.of(); }
    Iterator<Multiset.Entry<E>> iterator = multiset.entrySet().iterator();
    E cutoff = null;
    for (int count = 0; count < n && iterator.hasNext(); ) {
        Multiset.Entry<E> entry = iterator.next();
        count += entry.getCount();
        cutoff = entry.getElement();
    }
    if (count < n) { return multiset; }
    // cutoff is not null, since the loop must iterate at least once
    return multiset.headMultiset(cutoff, BoundType.CLOSED);
}
于 2011-12-03T00:08:58.047 回答
0

实际上，使用 HashMap 的解决方案似乎具有可接受的性能。我通过以下方式构建了哈希映射：

public NavigableMap<Integer, E> BuildHashMap (SortedMultiset<E> multiset){
    NavigableMap<Integer, E>  ret = new TreeMap<Integer, E>();
    int n = 0;
    for (Entry<E> e : multiset.entrySet()) {
        ret.put(n, e.getElement());
        n += e.getCount();
    }
    return ret;
}

并使用.floorEntry(n).getValue().

但是elementSet().asList()，我实际上正在寻找的功能。

于 2011-12-03T17:06:35.330 回答