修剪一个排序的集合

Question

我有一个 SortedSet （特别是 TreeSet）包含更新。更新类似于SVN提交，Facebook Wall Post，New Trac票等。我将其存储在一个 SortedSet 因为：

• 排序：更新需要按日期进行排序，下降。
• 集合：从更新源获取最新更新时，我通常会收到集合中已经存在的更新。

现在，一段时间后，该集合将变得非常巨大，因此我想删除除了集合中的第一个X项目（因为无论如何都不会显示其他X项目）。我该怎么做，因为它不是 List?

Answer 1

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

Answer 2

这里的解决方案应取决于您将来是否需要“额外”数据的事实。如果您需要基于其他列表的解决方案，则可以。如果没有，我建议以下内容：

创建自己的排序集，该集合扩展Java.util.SortedSet并覆盖其add（）方法。此方法在一定限制后不应执行任何操作。另外，您可以创建保留有效负载集的“包装器”集，并委派除add（）以外的所有方法。 ADD（）方法仅在有效负载集的大小小于预定义的限制时才应委派其呼叫。这就是方法 固定SizeSortedMap 雅加达收集框架的作品，因此您可以使用它。

Answer 3

公认的答案并非真正有效 o（ln n） 因为它使用删除函数。这是一个更好的 pollLast() 是 o（1） 大小是 o（1）. 。复杂性仅受修剪大小的影响。

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

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的工作解决方案方法，给定一棵树 结果, 和变量 尺寸 指定结果集的大小：

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
}