Обрезка отсортированного набора

Question

У меня есть SortedSet (в частности, TreeSet), содержащий обновления. Обновление - это что-то вроде коммита SVN, сообщения на стене Facebook, нового билета Trac и т. Д. Я храню их в SortedSet, потому что:

• Сортировка: обновления должны быть отсортированы по дате, по убыванию.
• Set: При получении последних обновлений из источника обновлений я обычно получаю обновления, которые уже есть в наборе.

Теперь, через некоторое время, набор станет действительно огромным, поэтому я бы хотел удалить из него все, кроме первых 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 () должен делегировать свой вызов, только если размер набора полезной нагрузки меньше, чем предопределенный предел.Вот как работает FixedSizeSortedMap фреймворка коллекции Джакарты, так что вы можете просто использовать его.

Answer 4

Вот метод рабочего решения для Java с учетом TreeSet результатов и переменной 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
}

Answer 5

Мой собственный обходной путь:

        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);