Java LinkedHashSet удаляет некоторые элементы с конца

Я работаю над проблемой, где я должен хранить элементы с требованиями No Duplication и Поддержание порядка. Я решил пойти с LinkedHashSet Так как он выполнил оба моих требования.

Допустим, у меня есть этот код:

 LinkedHashSet hs = new LinkedHashSet();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  if(hs.contains("D")){
       //do something to remove elements added after"D" i-e remove "E", "C" and "F"
       //maybe hs.removeAll(Collection<?>c) ??
   }

Может кто-нибудь, пожалуйста, направьте меня с логикой, чтобы удалить эти элементы?

Я использую неправильную структуру данных? Если так, то что будет лучшей альтернативой?

Источник

5 ответов

Решение

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

Я использовал Graphs, эта библиотека очень пригодилась: http://jgrapht.org/

То, что я делаю, это добавление всех элементов в виде вершин к DirectedGraph также создавая ребра между ними (ребра помогли мне решить еще одну не связанную проблему). И когда пришло время удалять элементы, я использую рекурсивную функцию со следующим псевдокодом:

removeElements(element) {

tempEdge = graph.getOutgoingEdgeFrom(element)
if(tempEdge !=null)
   return;
tempVertex = graph.getTargetVertex(tempEdge)
removeElements(tempVertex)
graph.remove(tempVertex)

}

Я согласен, что граф DS не подходит для такого рода проблем, но в моих условиях это прекрасно работает... Ура!

Источник

Я думаю, что вам может понадобиться использовать итератор для удаления, если вы используете LinkedHashSet. То есть найдите элемент, затем продолжайте удалять, пока не дойдете до хвоста. Это будет O(n), но даже если вы напишите свой собственный LinkedHashSet (с двусвязным списком и хэш-набором), у вас будет доступ к необработанной структуре ссылок, так что вы сможете сократить связанный список в O(1), но вы все равно нужно удалить все элементы, которые вы только что вырезали из связанного списка, из HashSet, где снова возникнет стоимость O (n).

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

Источник

Вы можете написать свою собственную версию ArrayList, которая не допускает дублирования, переопределив add() а также addAll(), Насколько мне известно, не существует "обычной" сторонней версии такой, которая меня всегда удивляла. Кто-нибудь знает об этом?

Тогда удалить код довольно просто (не нужно использовать ListIterator)

int idx = this.indexOf("D");
if (idx >= 0) {
  for (int goInReverse = this.size()-1; goInReverse > idx; goInReverse--)
    this.remove(goInReverse);
}

Тем не менее, это все еще O(N), потому что вы перебираете все элементы списка.

Источник

Основная проблема здесь заключается в том, что вам необходимо поддерживать две структуры данных: одну "карту", ​​представляющую отображение ключ / значение, и "список" другую, представляющую порядок вставки.

Существуют организации "карта" и "список", которые предлагают быстрое удаление элементов после заданной точки; например, упорядоченные деревья различных видов, а также списки на основе массива и цепочки (по модулю стоимости определения точки).

Однако кажется невозможным удалить N элементов из двух структур данных лучше, чем O(N), Вы должны посетить все удаляемые элементы, чтобы удалить их из второй структуры данных. (На самом деле, я подозреваю, что это можно доказать математически...)

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

Область, где возможно улучшить производительность (с помощью пользовательского класса коллекции!), Заключается в том, чтобы избежать явного использования итератора. Используя итератор и стандартный API итератора, стоимость O(N) на общее количество элементов в структуре данных. Вы могли бы сделать это O(N) на количество удаленных элементов... если узлы ввода хеша также имели следующие / предыдущие ссылки для последовательности.

Источник

Последний элемент можно получить или удалить с помощьюgetLast()иremoveLast()методы, которые добавляются вLinkedHashSetв Java 21 как часть улучшения секвенированных коллекций . Это можно совместить сwhileцикл для удаления элементов из конца набора до тех пор, пока не встретится нужный элемент.

      if (hs.contains("D")) {
    while (!"D".equals(hs.getLast())) {
        hs.removeLast();
    }
}
Источник
Другие вопросы по тегам