Навязчивая реализация списка для Java?

Question

Есть ли (хорошо реализованный) навязчивый класс (ы) двойного связанного списка, доступный для Java? Или я должен сделать свой собственный? У Boost это есть для C ++: http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.

Интрузивный список - это контейнер, имеющий (в данном случае) указатели next и prev внутри элемента, поэтому типичные операции над списками, такие как replace и remove, могут быть напрямую направлены в элементарный класс вместо класса контейнера. В некоторых ситуациях наилучшим решением является навязчивый список.

Я пытаюсь привести соответствующий пример. Давайте предположим, что у меня есть связанные списки L list1 и L list2, принадлежащие разным типам классов X1 и Y2.

класс Q (который не имеет ничего общего или не может легко получить доступ к интерфейсам x1 и Y2 в противном случае) должен выполнить i) замену, ii) операцию удаления для элемента e, который всегда существует где-то в списке list xor list2 в зависимости от состояния времени выполнения, но эта информация нигде не хранится напрямую.

С помощью навязчивого списка Q можно просто сохранить ссылку на элемент для элемента-члена e, и он всегда указывает правильное место.

В противном случае вам придется выбрать один из нескольких явно более сложных обходных путей. - класс Wrapper для элемента e и дополнительные методы для выполнения операций i и ii. Нет.

По сути, вопрос все же не в производительности, а в сложности архитектуры. Это также можно понимать как один вид ситуации с общими объектами, когда решение IL избегает необходимости обновления для каждого клиента Lx и Q.

Обратите внимание, что мне НЕ требуется совместимость с другими стандартными контейнерами. Просто общая навязчивая реализация lsit с итерацией, добавлением, удалением и поиском операций, используемых с неизвестным классом элементов.

Спасибо.

Answer 1

Я не знаю ни о каких существующих реализациях (и нет, я не считаю нормальные коллекции Java навязчивыми).

Это, вероятно, потому, что единственное важное преимущество такого списка было бы в Javaбудет быстрым вызовом remove(), когда у вас уже есть элемент, который нужно удалить (и у вас нет Iterator в этой позиции).Элемент not-copying-the-element не является допустимым аргументом в Java, поскольку реализации Java List в любом случае обрабатывают только ссылки (и никогда не копируют весь объект).

Но вы можете легко написать универсальное назначениеList реализация, которая навязчива путем создания необходимого интерфейса:

public interface IntrusiveListElement<E extends<IntrusiveListElement<E>> {
  public void setNext(E next);
  public E getNext();
  public void setPrev(E prev);
  public E getPrev();
}

public class IntrusiveList<E extends IntrusiveListElement<E>> implements List<E> {
  // implement your run-of-the-mill double-linked list here
}

Ваш класс элемента может выглядеть следующим образом:

public class MyBusinessElement implements IntrusiveListElement<MyBusinessElement> {
  private MyBusinessElement prev;
  private MyBusinessElement next;

  public void setNext(MyBusinessElement next) {
    this.next = next;
  }

      public MyBusinessElement getNext() {
    return next;
  }

  public void setPrev(MyBusinessElement prev) {
    this.prev = prev;
  }

  public MyBusinessElement getPrev() {
    return prev;
  }
}

Answer 2

Есть ли (хорошо реализованный) навязчивый класс (ы) двойного связанного списка для Java?

Не знаюдумаю, вы найдете его.

Мое понимание "навязчивый" состоит в том, что объект приложения, который необходимо сохранить в структуре данных, нуждается вдля непосредственного включения («вторжения») следующих / прежних указателей в объект приложения .

Это, в отличие от подхода «обертка указателя», где узел структуры данных содержит указатель наобъект приложения, таким образом, не требующий модификации объекта приложения.Интрузивный подход имеет ряд преимуществ , в том числе устранение двойной разыменования (один раз для узла и один раз для указателя узла на объект приложения), общего для подхода «обертка указателя».

Я не верю, что вы найдете навязчивую библиотеку структур данных для Java.В Java отсутствуют C ++ -подобные шаблоны или множественное наследование, и он не поддерживает копирование по значению всего объекта.Из-за этого я не думаю, что есть способ вообще добавить поля следующего / предыдущего экземпляра к объекту Java.

Например, учитывая объект приложения:

class Foo {
    int bar;
}

как-товам нужно иметь возможность добавлять поля next / prev и методы управления списками к нему или его производным:

class Foo2 {
    int bar;
    Foo2 prev;
    Foo2 next;
}

Один из способов добавить эти поля, предоставив базовый класс с этими полями для этих классов приложений.расширить - это подход Boost.Однако этот подход очень ограничивает язык с одним наследованием, такой как Java.

Интерфейсы Java часто являются ответом Java на множественное наследование, например интерфейс, требующий методы getNext () и getPrev () классов приложений.Однако, если вам нужны навязчивые структуры данных по соображениям производительности, доступ к полям next / prev с помощью метода может отрицательно повлиять на эти цели.

Обобщения Java также не расширяют классы необходимым способом.

Или я должен сделать свой собственный?

Если это один раз для конкретного случая для тщательно оцененной потребности, обязательно - бросьте свой собственный,Если вы пытаетесь накатить универсальный для общего пользования, я не уверен, что оно того стоит.

Один действительно грубый подход заключается в пользовательском расширении класса приложения для добавления необходимых полей:

class Foo3 extends Foo {
    Foo3 prev;
    Foo3 next;
}

и использовании повторного использования cut-n-paste для добавления методов управления списком.Однако я настоятельно рекомендую , а не , используя этот подход.

Мыльница

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

С уважением предлагаю вам подумать:

• пытаетесь ли вы преждевременно оптимизировать,
• добавляете ненужную сложность для небольшого выигрыша
• если скоростьи управление памятью имеет первостепенное значение, вы используете правильный язык?

Answer 3

Если вы посмотрите на код SDK, вы увидите, что LinkedList, по сути, представляет собой список записи частного класса, который содержит следующий и предыдущий элементы.Итак, если вы включите MyClass в этот список, элементом списка будет Entry с вашим объектом и ссылки для следующих и предыдущих элементов списка.

Итак, я думаю, что это навязчиво ...

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;

    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

Answer 4

Что вы надеетесь получить, используя навязчивый список?Мне трудно думать о преимуществах.Хорошо, есть тривиальная эффективность: у вас есть только один объект вместо двух для каждого узла.Но цена этого - большая потеря в гибкости и надежности.Например, теперь вы не можете иметь один и тот же объект в двух списках одновременно.Что произойдет, если вызывающая сторона извлечет экземпляр члена списка и попытается изменить один из указателей сам?Что он, вызывающий, клонирует узел и не может обновить указатели?И т.д.

Дейв Рэй подчеркивает, что с помощью навязчивого списка вы можете удалить узел за постоянное время, потому что у вас уже есть указатели и вам не нужно повторно находить элемент.Верно, но это предполагает, что вы сохранили дескриптор где-то на узле и теперь возвращаетесь к нему.С классом Java LinkedList практически единственный способ получить доступ к элементам - это просмотреть список с помощью итератора или выполнить поиск определенного объекта.Если вы переместитесь через Iterator, Iterator.remove удалится за постоянное время.Так что только если вы ищете, найдете, а затем решите удалить, вы платите этот штраф.Я думаю, что было бы улучшением реализации LinkedList, если бы они кэшировали указатель на последний найденный объект, чтобы улучшить производительность именно на этом этапе.Я предполагаю, что они этого не сделали, потому что это сделало бы удаление недетерминированным: вы можете иметь один и тот же объект в списке несколько раз - либо буквально один и тот же экземпляр, либо два объекта, которые сравниваются - и контракт на удаление в настоящее времяговорит, что всегда удаляет первое вхождение.Если бы был кешированный указатель, было бы трудно сказать, был ли это первый, второй или 42-й.

Да, на самом деле, чтобы ответить на ваш вопрос: Нет, я не знаю о open-sourceреализация там.Но тогда, если бы мне нужен был собственный вид связанного списка, я думаю, я бы просто сделал свой собственный.Предположительно, если стандартная Java не удовлетворяет вашим потребностям, это должно означать, что у вас есть довольно специфические потребности.В этом случае поиск готовой реализации, отвечающей вашим специализированным потребностям, кажется большим трудом, и вы наверняка могли бы реализовать ее в течение одного или двух дней работы?Вероятно, вы бы потратили больше времени на поиск подходящего продукта, чем просто занялись бы этим.Вероятно, вы уже потратили больше времени на чтение ответов на это сообщение, чем на его написание.

Answer 5

Семантика Java навязчива, она использует ссылки и не копирует. По сути, вы просто хотите найти лучшую реализацию связанного списка, которую имеет java, LinkedList или что-то еще, и это будет навязчиво.

import java.util.LinkedList;

public class Foo {

  public static void main(String[] args) {
    String[] i = new String[1];
    i[0] = "FOO";
    String[] j = new String[1];
    j[0] = "BAZ";

    LinkedList<String[]> list = new LinkedList<String[]>();

    list.add(i);
    list.add(j);

    for (String[] x: list) {
      System.out.println(x[0]);
    }

    i[0] = "ZILCH";

    for (String[] x: list) {
      System.out.println(x[0]);
    }
  }
}

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

FOO
BAZ
ZILCH
BAZ

Answer 6

Вы смотрели на класс Deque ?Согласно javadoc, «Линейная коллекция, которая поддерживает вставку и удаление элементов на обоих концах. Название deque является сокращением от« двусторонняя очередь »и обычно произносится как« deck ».»Это реализуется ArrayDeque , LinkedBlockingDeque и LinkedList .