修剪已排序的集合

Question

我有一个包含更新的 SortedSet （特别是 TreeSet）。更新类似于 SVN 提交、Facebook 墙贴、新 Trac 票证等。我将这些存储在 SortedSet 中，因为：

• 排序：更新需要按日期降序排序。
• 设置：当从更新源获取最新更新时，我通常会收到该集中已有的更新。

现在，过了一段时间，集合将变得非常巨大，所以我想从集合中删除除前 X 个项目之外的所有内容（因为其他项目无论如何都不会显示）。由于它不是 List，我该如何执行此操作？

Answer 1

While(mySet.size() > limit) {
  mySet.remove(mySet.last());
}

Answer 2

接受的答案并不是真正有效的O(ln n)，因为它使用了删除函数。
这是一个更好的方法，因为 pollLast() 的时间复杂度为 O(1)，大​​小为 O(1)。复杂性只会受到修剪尺寸的影响。

While(mySet.size() > limit) {
  mySet.pollLast();
}

Answer 3

这里的解决方案应该取决于您将来是否需要“额外”数据。如果您需要基于附加列表的解决方案也可以。如果没有，我建议如下：

创建您自己的排序集，扩展 java.util.SortedSet 并覆盖其 add() 方法。此方法在一定限制后不应执行任何操作。或者，您可以创建“包装器”集来保存有效负载集并委托除 add() 之外的所有方法。仅当有效负载集的大小小于预定义的限制时，add() 方法才应委托其调用。
这就是 jakarta 集合框架的 FixedSizeSortedMap 的工作原理，因此您可以使用它。

Answer 4

我自己的解决方法是：

        List<Update> trimmed = new ArrayList<Update>(20);
        int i = 0;
        for (Update u : updates) {
            trimmed.add(u);
            i++;
            if (i > 20) break;
        }
        updates = new TreeSet<Update>(trimmed);

Answer 5

下面是 Java 的一个可行的解决方案方法，给定一个 TreeSet results 和一个指定结果集大小的变量 size：

void setLimit(Set<T> resutls, int size) {
    List<T> items = new ArrayList<T>();
    items.addAll(resutls);
    resutls.clear();
    int trim = size>items.size() ? items.size() : size;
    resutls.addAll(items.subList(0,trim));
    // return results; // optionally, if required
}