Implementación de listas intrusivas para Java?

Question

¿Hay alguna (s) clase (s) de lista de doble enlace intrusivo (bien implementadas) disponibles para Java? ¿O debería hacer lo mío? Boost lo tiene para C++: http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.

La lista intrusiva es un contenedor que tiene (en este caso) punteros siguiente y anterior dentro del elemento, por lo que las operaciones de lista típicas como reemplazar y eliminar pueden dirigirse directamente a la clase primaria en lugar de la clase contenedora. Existen ciertas situaciones en las que la lista intrusiva es la mejor solución.

Intento dar un ejemplo apropiado. Supongamos que he vinculado listas L list1 y L list2 propiedad de diferentes tipos de clases X1 e Y2.

clase Q (que no tiene nada que ver o no tiene acceso fácil a las interfaces de x1 e Y2) debe hacer i) reemplazar, ii) eliminar operación para el elemento e, que existe siempre en alguna parte, en lista1 xor list2 dependiendo del estado del tiempo de ejecución, pero esa información no se almacena directamente en ninguna parte.

Con la lista intrusiva Q solo puede almacenar la referencia a un elemento e miembro elemento e y siempre señala el lugar correcto.

De lo contrario, tiene que elegir entre varias soluciones claramente más complejas, una u otra. - Clase de contenedor para el elemento ey métodos adicionales para completar las operaciones iy ii. No.

Básicamente, la pregunta no es sobre el rendimiento sino la complejidad arquitectónica. Esto también puede entenderse como un tipo de situación de objeto compartido donde la solución IL evita la necesidad de actualización para cada cliente Lx y Q.

Tenga en cuenta que NO es necesario que necesite compatibilidad con otros contenedores estándar. Solo una implementación lsit intrusiva genérica con operaciones de iteración, adición, eliminación y búsqueda utilizadas con clase de elementos desconocidos.

Gracias.

Answer 1

No conozco ninguna implementación existente (y no, no considero que las colecciones Java normales sean intrusivas).

Eso es probablemente porque la única de las principales ventajas de una lista de este tipo tendría en Java sería la rápida remove() llamada cuando ya tiene el elemento que se retira a mano (y no tiene un Iterator en esa posición). El elemento no-copiar-el-elemento no es un argumento válido en Java, ya que las implementaciones Java List solo manejan referencias de todos modos (y nunca copian el objeto completo).

Pero se puede escribir fácilmente una de propósito general List aplicación que es intrusiva mediante la creación de la interfaz necesaria:

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 
} 

Su clase elemento podría tener este aspecto:

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

¿Has echado un vistazo al Deque class? Según el javadoc, "Una colección lineal que admite la inserción y eliminación de elementos en ambos extremos. El nombre deque es la abreviatura de" cola de doble final "y generalmente se pronuncia" cubierta ". Se implementa por ArrayDeque, LinkedBlockingDeque y LinkedList.

Answer 3

La semántica de Java es intrusiva por diseño, usan referencias y no se copian. Básicamente, solo quieres encontrar la mejor implementación de listas enlazadas que java tiene, LinkedList o lo que sea, y será intrusivo.

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

Aquí está la salida, observe cómo cambiando cambié el valor en la lista.

FOO 
BAZ 
ZILCH 
BAZ 

Answer 4

si se mira al código SDK se verá que LinkedList es, de hecho, una lista de una entrada de clase privada que contiene los elementos siguientes y anteriores. Por lo tanto, si incluye MyClass en esta lista, un elemento de la lista será una Entrada con su objeto y los enlaces para los elementos siguientes y anteriores de la lista.

Entonces, creo que es intrusivo ...

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 5

¿Hay alguna (bien implementado) intrusiva clase doble lista enlazada (s) disponibles para Java?

No creo que encuentre una.

Mi comprensión de "intrusivo" es que el objeto de aplicación para ser almacenada en la estructura de datos necesita directamente incluir ("entrometerse") los próximos punteros/PREV dentro del objeto de aplicación.

Esto está en contraste con el enfoque de "envoltura de puntero" donde el nodo de estructura de datos contiene un puntero al objeto de aplicación, por lo que no requiere modificación del objeto de aplicación. El enfoque intrusivo tiene a number of benefits, que incluye evitar la doble desreferenciación (una para el nodo y una para el puntero del nodo al objeto de la aplicación) común al enfoque de "envoltura del puntero".

No creo que encuentre una biblioteca de estructura de datos intrusiva para Java. Java carece de plantillas similares a C++ ni de herencia múltiple, y no admite fácilmente la copia por valor de un objeto completo. Debido a esto, no creo que exista una manera de agregar genéricamente los campos de instancia next/prev a un objeto Java.

Por ejemplo, dado el objeto de aplicación:

class Foo { 
    int bar; 
} 

alguna manera Tienes que ser capaz de añadir campos NEXT/PREV y métodos de gestión de listas a la misma o un derivado de la misma:

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

Una forma de agregar estos campos al proporcionar una clase base con estos campos para que se extiendan estas clases de aplicaciones, este es el enfoque de Boost. Sin embargo, este enfoque es muy limitante en un lenguaje de herencia única como Java.

Las interfaces de Java a menudo son la respuesta de Java a la herencia múltiple, p. una interfaz para requerir los métodos getNext() y getPrev() de clases de aplicación. Sin embargo, si necesita estructuras de datos intrusivas por motivos de rendimiento, acceder a los campos next/prev a través de un método puede afectar negativamente esos objetivos.

Los genéricos de Java tampoco amplían las clases de la manera necesaria.

¿O debería hacer yo solo?

Si su una vez para un caso específico para una necesidad evaluado cuidadosamente, Seguro - liar. Si intentas rodar uno genérico para uso general, no estoy seguro de que valga la pena.

Un enfoque muy bruto sería extender la clase de aplicación personalizada para agregar los campos necesarios:

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

y utilizar reutilización-n-pegar cortar añadir los métodos de gestión de listas.Sin embargo, recomendaría encarecidamente no utilizando este enfoque.

Soapbox

Usted no indica por qué necesita una estructura de datos intrusivo. Quizás tenga razones válidas para necesitarlo, pero es difícil imaginarlo. Java depende en gran medida del uso de punteros de objetos y tratar de evitarlos de esta manera sería difícil.

respetuosamente sugerimos que considere:

• ¿Estás tratando de optimizar prematuramente,
• ¿Desea agregar una complejidad innecesaria para poco beneficio
• si la velocidad y la gestión de memoria es lo más importante, está usando la derecha ¿idioma?

Answer 6

¿Qué espera ganar usando una lista intrusiva? Estoy en apuros para pensar cuáles serían las ventajas. De acuerdo, hay una eficiencia trivial que tiene un solo objeto en lugar de dos para cada nodo. Pero el precio de esto es una gran pérdida de flexibilidad y fiabilidad. Por ejemplo, ahora no puede tener el mismo objeto en dos listas al mismo tiempo. ¿Qué sucede si un llamante recupera una instancia de un miembro de la lista e intenta cambiar uno de los punteros? ¿Cómo llama un usuario un nodo y no actualiza los punteros? Etc.

Dave Ray señala que con una lista intrusiva puede eliminar un nodo en tiempo constante porque ya tiene los punteros y no necesita volver a encontrar el elemento. Es cierto, pero eso supone que ha guardado un identificador para el nodo en alguna parte y ahora está volviendo a él. Con la clase Java LinkedList, la única forma de acceder a los elementos es recorrer la lista con un iterador o buscar un objeto en particular. Si recorre con un Iterador, el Iterator.remove se eliminará en un tiempo constante. Por lo tanto, solo si busca, encuentra y luego decide eliminar, paga esta penalización. Creo que sería una mejora en la implementación de LinkedList si almacenan en caché un puntero al último objeto encontrado para mejorar el rendimiento precisamente en este punto. Mi suposición es que no lo hicieron porque haría que la eliminación no fuera determinista: podría tener el mismo objeto en la lista varias veces, ya sea literalmente la misma instancia o dos objetos que se comparan por igual, y el contrato en eliminar actualmente dice que siempre elimina la primera ocurrencia. Si hubiera un puntero en caché, sería difícil decir si fue el primero, el segundo o el 42º.

Oh, para responder realmente a su pregunta: No, no estoy al tanto de una implementación de código abierto. Pero si necesitaba mi propio sabor de una lista vinculada, creo que solo voy a hacer mi propia versión. Presumiblemente, si el Java estándar no satisface sus necesidades, eso debe significar que tiene alguna necesidad bastante especializada. En cuyo caso, la búsqueda de una implementación estándar que satisfaga su necesidad especializada parece ser un problema, y ​​seguramente podría implementarla en ¿qué? ¿Un día o dos de trabajo? Probablemente dediques más tiempo a buscar un producto adecuado de lo que necesitarías para hacerlo. Probablemente ya hayas dedicado más tiempo a leer las respuestas a esta publicación de lo que te hubiera llevado escribirla.