Cuál es la mejor implementación de lista para listas grandes en java

Question

Tengo que crear una lista grande de n elementos (podría ser de hasta 100.000). cada elemento en la lista es un número entero equivalente al índice de la lista. Después de esto, tengo que llamar a Collections.shuffle en esta lista. Mi pregunta es, qué lista de implementación (ya sea colecciones java o colecciones apache) se debe utilizar. Mi intuición es que ArrayList puede usarse aquí. Todos los pensamientos son apreciados. Gracias!

Gracias por las entradas. Creo que me estoy apegando a ArrayList. Actualmente estoy usando el constructor ArrayList con el param inicialCapacity y paso el tamaño de la lista. Entonces, si la lista original es 100000, creo esta nueva lista con ArrayList (100000); Por lo tanto, creo que no tengo la creación de una matriz y hacer una lista como, ya que no habrá ningún cambio de tamaño. Además, la mayoría de las listas de colecciones apache como GrowthList & LazyList no implementan RandomAccess. Esto seguramente ralentizaría la mezcla (según los javadocs). FastArrayList implementa RandomAccess pero apache tiene una nota para esta clase que dice "Esta clase no es multiplataforma. Usarla puede causar fallas inesperadas en algunas arquitecturas".

Answer 1

ArrayList probablemente tiene la menor cantidad de elementos por lista, así que debería ser la mejor opción. Puede ser una opción peor si con frecuencia necesita eliminar elementos en el medio de la lista.

Answer 2

ArrayList<T> probablemente estaría bien, sí, pero ¿qué criterio está utilizando para el "mejor" de todos modos? ¿Y qué tan bueno tiene que ser de todos modos? ¿Cuáles son sus compensaciones entre complejidad y "bondad" en cualquiera que sean esos criterios?

Answer 3

Citado de la javadoc Collections.shuffle:

Este método se ejecuta en tiempo lineal. Si la lista especificada no implementa la interfaz RandomAccess y es grande, esta implementación vuelca la lista especificada en una matriz antes de mezclarla y vuelve a colocar la matriz mezclada en la lista. Esto evita el comportamiento cuadrático que resultaría al mezclar una lista de "acceso secuencial" en su lugar.

Así que si no tiene otras necesidades iría con ArrayList que implementa RandomAccess.

Answer 4

ArrayList será la mejor lista para esto. Como el respaldo de la matriz será muy eficiente para intercambiar elementos utilizados en la mezcla.

Pero si realmente está supervisando el rendimiento, puede considerar usar una lista int [] o personalizada basada en int [] ya que con todas las implementaciones estándar List y List, estará encajonando y desempaquetando enteros.

Esto no será un problema en el sufijo ya que esto solo reordenará los punteros, pero creará 100.000 objetos cuando no sea necesario. Suponiendo que conoce el tamaño de su lista antes de la creación, puede crear fácilmente una nueva clase de lista que envuelva una matriz primitiva. Si se usa como java.util.List, aún tendrá que marcar la devolución de cualquier método get.

Answer 5

Hacer una matriz Integer y luego envolverla con Arrays.asList le proporciona incluso menos gastos generales que un ArrayList normal.

List<Integer> makeList(int size){ 
    if (size < 0) throw new IllegalArgumentException(); 
    Integer[] arr = new Integer[size]; 
    for (int i = 0; i < arr.length; ++i) arr[i] = i; 
    List<Integer> list = Arrays.asList(arr); 
    Collection.shuffle(list); 
    return list; 
} 

Se ahorra una int toda la pena del espacio (... que ciertamente hay absolutamente nada en este contexto), pero sí realizar un menor número de pruebas de alcance que el "verdadero" ArrayList, por lo que el acceso será ligeramente más rápido.Probablemente nada notará, aunque :)

Answer 6

Javolution afirma tener la implementación más rápida de la lista en java. Pero no pude encontrar ninguna implementación aleatoria en esta biblioteca, así que tendrás que hacerlo a mano.

Answer 7

La biblioteca de Google Guava tiene un manejo bastante primitivo, incluyendo un método Ints.asList() que devuelve una lista que puede mezclarse.

El proyecto Guava se encuentra todavía en una etapa preliminar de implementación, aunque el código ha sido cuidadosamente revisado y utilizado en gran medida en Google. Tendrá que recuperar el código de SVN y crear las clases com.google.common.primitive.

Answer 8

También puede utilizar la implementación de la lista basada en archivos mapeados de memoria. En dicha implementación, la lista no está completamente presente en la memoria, pero solo una sección de la enorme lista estará activa en la memoria. Si está llegando a la limitación del espacio de montón (principalmente en jvm de 32 bits) es posible que necesite hacer que la lista elimine datos sin problemas utilizando un archivo mapeado de memoria que será más rápido que la E/S de archivo normal. Una implementación de este tipo se describe en este google code y se explica en este link.

Answer 9

Hay una implementación de lista recientemente inventada llamada GlueList que es muy rápida que ArrayList y LinkedList.