Сортировка списка с самого начала

Question

У меня есть список объектов, которые потребуют много добавлений / удалений. Я хочу, чтобы список сортировался по определенной функции.

Прямо сейчас, каждый раз, когда я добавляю новый объект, я делаю:

list.add(obj1);
Collections.sort(list1, comparator);

Удаление объекта не «отменяет сортировку» списка, поэтому мне нужно сделать это только для операции добавления.

Однако Collections.sort - это O (> N), что не очень быстро.

Существует ли какая-либо структура в java, которая позволяет мне сохранять отсортированный список с самого начала?

Забыл упомянуть

Я пытался использовать TreeSet. Это позволяет мне передать компаратор, который будет использоваться для сортировки, но который также будет использоваться для удаления элементов, а это не то, что я хочу. Я хочу, чтобы он был отсортирован, но функция удаления идентична списку.

Answer 1

Если Alencar предлагает, используйте Collections.binarySearch(yourList, key, comparator), чтобы найти правильную позицию вставки. Это намного быстрее, чем поиск по всему списку, так как binarySearch требует только log2 (размер списка) запросов, чтобы найти правильную позицию вставки.

Итак, если ваш код вставки был

void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
  int pos=0;
  ListIterator<T> it=list.listIterator();
  while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
  if (pos < it.previousIndex()) it.previous();
  it.add(value);
}

... и более быстрая версия будет ...

void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
  int pos = Collections.binarySearch(list, value, comparator);
  if (pos < 0) {
     pos = -pos -1; // returns negatives if not found; see javadoc
  }
  list.insert(value, pos);
}

Обратите внимание, что различие может быть не таким значительным, потому что вставка в несвязанный список требует смещения элементов вверх. Таким образом, если базовый список представляет собой ArrayList, при копировании в среднем половины элементов на одно место вправо, чтобы освободить место для нового элемента, получается O(n) дополнительное время на копию. И если список связан, вам все равно нужно заплатить штраф O(n), но на этот раз для выполнения бинарного поиска - в этом случае, вероятно, было бы лучше использовать первую версию.

Обратите внимание, что в первой версии используется ListIterator на тот случай, если вы решите использовать связанные списки. Для ArrayLists было бы проще использовать list.get(pos) и list.add(pos, value), но это очень плохая идея в контексте итерации связанных списков.

Answer 2

Не можете ли вы добавить объект в «правильном» месте? уже отсортировано?

Вы сказали, что каждый раз, когда вы добавляете новый объект, вы сортируете список / коллекцию.

Возможно, вы можете использовать двоичный поиск, чтобы найти точный индекс, который вам нужен, чтобы вставить новое значение, или использовать свой компаратор для поиска.