Cons'ing una lista en Java

Question

decir que tengo un java.util.List list y quiero crear un nuevo List mediante la adición de un elemento e al principio de list (es decir, quiero contrase y list). Por ejemplo, si list es

[1,2,3,4] 

y e es 5, entonces cons(e,list) habrá

[5,1,2,3,4] 

Está bien que los elementos de list y cons(e,list) para ser compartido, pero list no debe ser modificado.

¿Cuál es la forma más simple y/o más eficiente de implementar cons? Está bien que el resultado sea inmodificable. El uso de la Biblioteca de colecciones de Google está permitido.

¿Qué pasa si list es un com.google.common.collect.ImmutableList?

Answer 1

¿Podría usar un CompositeCollection?

public Collection cons(Collection c1, Collection c2) 
{ 
    CompositeCollection cons = new CompositeCollection(); 
    cons.addComposited(c1); 
    cons.addComposited(c2); 
    return cons; 
} 

Esto no se verían afectados por si o no uno de los parámetros es inmutable y aún con el respaldo de las colecciones originales C1 y C2.

Si necesita un List que probablemente hacer lo siguiente:

public List cons(Collection c1, Collection c2) 
{ 
    ArrayList cons = new ArrayList(c1.size() + c2.size()); 
    cons.addAll(c1); 
    cons.addAll(c2); 
    return cons; 
} 

Answer 2

public static<T> List<T> cons(List<T> list, T t) { 
    ArrayList<T> result = new ArrayList<T>(list); 
    result.add(0, t); 
    return result; 
} 

editada en respuesta a los comentarios: Dado que la pregunta hecha por "la forma más sencilla y/o eficiente de poner en práctica los contras , "Fui con" el más simple ". No me sorprendería saber que hay formas más eficientes. Poner el elemento antes de la lista es otro enfoque válido, y la asignación inicial del tamaño correcto probablemente mejore el rendimiento. La optimización prematura es la fuente de todos los males.

Answer 3

Clojure proporciona ese tipo de cosas de Lisp-y. Si bien la mayoría de la gente piensa en utilizar Clojure para el idioma (como yo), las bibliotecas de Clojure son todas código de Java real, y puede utilizar las estructuras de datos de Java como si fuera una biblioteca especial, si así lo desea. De esa forma tendrías la capacidad de hacer contras y demás, y obtendrás la inmutabilidad que usa Clojure. Las cadenas de datos Clojure también implementan los tipos Java equivalentes.

Solo un pensamiento desde una dirección diferente.

Answer 4

Voy a arrojar mis 2 centavos, y luego veo si alguien encuentra algo más elegante. En el caso general:

<E> List<E> cons(E e, List<E> list) { 
    List<E> res = Lists.newArrayListWithCapacity(list.size() + 1); 
    res.add(e); 
    res.addAll(list); 
    return res; 
} 

Con una ImmutableList (no sé qué tan eficiente es esto):

<E> ImmutableList<E> cons(E e, ImmutableList<E> list) { 
    return ImmutableList.<E>builder() 
         .add(e) 
         .addAll(list) 
         .build(); 
} 

Answer 5

Sin duda, un LinkedList sería la forma más eficiente de la inserción de un elemento a la cabeza de ¿una lista?

sólo tiene que utilizar la clase LinkedList que viene con Java

Answer 6

Debido a que usted menciona la función cons, asumiré que usted está acercando a este problema con el modelo conceptual de las listas enlazadas compuestas de células cons. Específicamente, supongo que está pensando en cada lista que tiene un car (el primer elemento) y un cdr (la sublista que contiene todos los elementos siguientes).

Java admite listas enlazadas como java.util.LinkedList. Estos son buenos para el recorrido lineal y pueden tener elementos insertados de manera muy eficiente. Estos son más similares a las listas vinculadas que mencioné anteriormente.

Java también ofrece java.util.ArrayList. Las listas de este tipo son buenas para el acceso aleatorio, pero pueden ser lentas al insertar elementos. De hecho, son más lentos al insertar un elemento al principio de la lista. Debido a que ArrayList s se implementan como arreglos entre bastidores, cada elemento debe copiarse una posición hacia adelante en la lista para dejar espacio para el nuevo primer elemento. Ahora, si también necesita una matriz más grande, ArrayList asignará una nueva matriz, copiará todos los elementos, y así sucesivamente.

(de ImmutableList Google se cita como "acceso aleatorio", por lo que es probable que más similar a este último.)

Si va a utilizar el método de cons menudo, le recomiendo usar con listas enlazadas. Una operación cons básicamente agrega un elemento al principio de una lista. Esto tiene poco sentido con estructuras lineales como arreglos. Recomiendo el uso de listas de matrices por este motivo: que están conceptualmente mal para el trabajo.

Para el muy exigente: porque una nueva lista se volvió cada vez cons se llama, la copia debe ocurrir si la lista es una LinkedList o un ArrayList. Sin embargo, todo el principal de una operación cons es que está operando en una lista vinculada.

public <E> LinkedList<E> cons(E car, List<E> cdr) { 
    LinkedList<E> destination = new LinkedList<E>(cdr); 
    destination.addFirst(car); 
    return destination; 
} 

Tenga en cuenta que el código anterior fue escrito después de leer las respuestas anteriores, por lo que me disculpo por cualquier plagio accidental. Avíseme si lo ve y lo reconoceré correctamente.

Suponiendo que estés satisfecho con el retorno de una LinkedList, puede utilizar ImmutableList como el cdr en este ejemplo.

Answer 7

Otra variación si solo tiene Iterable.

public static <E> List<E> cons(E e, Iterable<E> iter) { 
    List<E> list = new ArrayList<E>(); 
    list.add(e); 
    for(E e2: iter) list.add(e2); 
    return list; 
} 

public static <E> List<E> cons(Iterable<E>... iters) { 
    List<E> list = new ArrayList<E>(); 
    for(Iterable<E> iter: iters) for(E e1: iter1) list.add(e1); 
    return list; 
} 

Answer 8

creo que la respuesta que está buscando realmente es la siguiente:

http://functionaljava.googlecode.com/svn/artifacts/2.20/javadoc/fj/data/List.html

El método se llama aun cons.

No tengo experiencia con esta biblioteca. Apenas lo escuché el otro día. ¡Espero que sea bueno!

Answer 9

Una solución eficiente sería crear su propia implementación de listas, delegando perezosamente. Si no se puede modificar, no sería demasiado problema.Si se crea a través de un método de fábrica, incluso podría usar una de dos implementaciones subyacentes diferentes dependiendo de si el argumento List implementa RandomAccess o no.

Para el caso más simple (no he comprobado para ver si esta compila, no hay comprobaciones de sanidad, etc.):

class ConsList<E> extends AbstractList<E> 
{ 
    private final E first; 
    private final List<E> rest; 

    ConsList(E first, List<E> rest) 
    { 
     this.first = first; 
     this.rest = rest; 
    } 

    public int get(int index) 
    { 
     return (index == 0) ? first : rest.get(index - 1); 
    } 

    public int size() 
    { 
     return rest.size() + 1; 
    } 
} 

Estoy seguro de que algunos de los otros métodos podrían ser más eficiente, y el caso secuencial se mejoraría extendiendo AbstractSequentialList en su lugar.

Answer 10

Esto no es muy conocido, pero la API del compilador Java Sun contiene una implementación inmutable de la Lista que devuelve nuevas Listas inmutables usando métodos como append() y prepend(). Para usarlo, es necesario tools.jar en la ruta de clase, y esta declaración de importación: Código

import com.sun.tools.javac.util.List; 

muestra:

final List<Integer> list = List.of(6, 7); 
System.out.println(list); 

final List<Integer> newList = 
    list.prepend(5)      // this is a new List 
     .prependList(List.of(1, 2, 3, 4)) // and another new List 
     .append(8)      // and another 
     .reverse();      // and yet another 
System.out.println(newList); 

System.out.println(list == newList); 

System.out.println(list.getClass()); 
System.out.println(newList.getClass()); 

Salida:

6,7
8,7,6,5,4,3,2,1
false
com.sun.tools.javac.util.List clase
com.sun.tools.javac.util.List clase

Sé que esto es una API interna y no debe ser usado en la producción, pero es muy divertido (finalmente una colección java que se siente bien).

Nota: Todos los métodos estándar a partir de los mutables Collection y List las interfaces (como add()addAll()) arrojan UnsupportedOperationException, obviamente.

Referencia:

• com.sun.tools.javac.util.List (en DocJar)