Список с сопоставимым Vs TreeSet

Question

Вариант 1. Создайте список, который реализует Comparable, и сортируйте его с использованием collection.sort (List l) каждый раз, когда вы добавляете значение.Вариант 2. Создайте TreeSet (который постоянно сортируется).

Какой из них будет быстрее?Я спрашиваю об этом, потому что List предоставляет мне опцию ListIterator, которая мне нужна в моем случае, поскольку она позволяет мне добавлять элемент во время итерации.

Answer 1

Наиболее важные различия:

Criterion       | List with Collections.sort | TreeSet 
----------------+----------------------------+---------
cost of adding  | O(n log n)                 | O(log n)
equal sort keys | permitted                  | eliminated as duplicates
iteration       | bidirectional, can insert  | unidirectional, can not insert

Чтобы вставить элемент при итерации без получения ConcurrentModificationException, вы можете сделать:

for (E e : new ArrayList<E>(collection)) {
    // some other code

    collection.add(anotherE);
}

Answer 2

Collections.sort использует модифицированную сортировку слиянием с nlog (n) временем сортировки. Если вы вызываете метод при каждом добавлении, вы можете получить n ^ 2log (n) время. Принимая во внимание, что вставка в TreeSet гарантируется log (n). Поэтому, если вы вызываете его при каждом добавлении, оно становится n.log (n) . Поэтому я бы предложил вместо этого использовать TreeSet. Но TreeSet не допускает дублирования, так что это может повлиять на ваше решение.

Если вы используете List, то вместо использования Collections.sort вы можете оптимизировать одну вещь; как вы знаете, каждый раз, когда вы вставляете элемент в список, список уже отсортирован, поэтому использование сортировки вставкой здесь даст вам лучшую производительность, поскольку сортировка вставкой работает лучше в таких случаях.

Answer 3

Используйте TreeSet здесь.

Добавление в TreeSet - это операция log(n).Добавление в список является постоянным временем, но сортировка - n log(n).