Matriz o lista en Java. ¿Cual es mas rápido?

Tengo que mantener miles de cadenas en la memoria para acceder en serie en Java. ¿Debo guardarlos en una matriz o debería usar algún tipo de lista?

Como las matrices mantienen todos los datos en un bloque contiguo de memoria (a diferencia de las Listas), ¿el uso de una matriz para almacenar miles de cadenas causaría problemas?

Respuesta: El consenso común es que la diferencia de rendimiento es menor. La interfaz de lista proporciona más flexibilidad.

Sugiero que use un generador de perfiles para probar cuál es más rápido.

Mi opinión personal es que deberías usar Lists.

Trabajo en una gran base de código y un grupo anterior de desarrolladores usa matrices en todas partes . Hizo el código muy inflexible. Después de cambiar grandes porciones de ella a listas, notamos que no hay diferencia en la velocidad.

La forma de Java es que debe considerar qué abstracción de datos se ajusta mejor a sus necesidades. Recuerde que en Java una Lista es un resumen, no un tipo de datos concretos. Debe declarar las cadenas como una lista, y luego inicializarlo usando la implementación de ArrayList.

List strings = new ArrayList(); 

Esta separación del tipo abstracto de datos y la implementación específica es uno de los aspectos clave de la progtwigción orientada a objetos.

Una ArrayList implementa el Tipo de datos abstracto de la lista usando una matriz como su implementación subyacente. La velocidad de acceso es virtualmente idéntica a una matriz, con las ventajas adicionales de poder sumr y restar elementos a una Lista (aunque esta es una operación O (n) con una Lista de Arrays) y que si decides cambiar la implementación subyacente más adelante usted puede. Por ejemplo, si se da cuenta de que necesita acceso sincronizado, puede cambiar la implementación a un Vector sin reescribir todo su código.

De hecho, ArrayList fue diseñado específicamente para reemplazar la construcción de matriz de bajo nivel en la mayoría de los contextos. Si Java se estaba diseñando hoy, es completamente posible que las matrices se hubieran dejado por completo a favor de la construcción ArrayList.

Como las matrices mantienen todos los datos en un bloque contiguo de memoria (a diferencia de las Listas), ¿el uso de una matriz para almacenar miles de cadenas causaría problemas?

En Java, todas las colecciones almacenan solo referencias a objetos, no a los objetos mismos. Ambas matrices y ArrayList almacenarán unos pocos miles de referencias en una matriz contigua, por lo que son esencialmente idénticas. Puede considerar que un bloque contiguo de unos pocos miles de referencias de 32 bits siempre estará disponible en el hardware moderno. Esto no garantiza que no se quede sin memoria por completo, por supuesto, solo que el bloque contiguo de requisitos de memoria no es difícil de cumplir.

Debería preferir los tipos generics sobre las matrices. Como lo mencionaron otros, los arreglos son inflexibles y no tienen el poder expresivo de los tipos generics. (Sin embargo, admiten la comprobación de tipo de tiempo de ejecución, pero eso se mezcla mal con tipos generics).

Pero, como siempre, al optimizar siempre debe seguir estos pasos:

  • No optimices hasta que tengas una versión de código agradable, limpia y funcional . Cambiar a tipos generics bien podría estar motivado en este paso ya.
  • Cuando tenga una versión que sea agradable y limpia, decida si es lo suficientemente rápida.
  • Si no es lo suficientemente rápido, mida su rendimiento . Este paso es importante por dos razones. Si no mide, no (1) sabrá el impacto de las optimizaciones que realice y (2) sabrá dónde optimizar.
  • Optimiza la parte más caliente de tu código.
  • Medir de nuevo. Esto es tan importante como medir antes. Si la optimización no mejora las cosas, inviértala . Recuerde, el código sin la optimización fue limpio, agradable y funcional.

Aunque las respuestas que proponen usar ArrayList sí tienen sentido en la mayoría de los escenarios, la pregunta real sobre el rendimiento relativo no ha sido realmente respondida.

Hay algunas cosas que puedes hacer con una matriz:

  • crearlo
  • establecer un elemento
  • obtener un artículo
  • clonar / copiar

Conclusión general

Aunque las operaciones get y set son algo más lentas en una ArrayList (respectivamente 1 y 3 nanosegundos por llamada en mi máquina), hay muy poca sobrecarga de uso de una ArrayList frente a una matriz para cualquier uso no intensivo. Sin embargo, hay algunas cosas a tener en cuenta:

  • cambiar el tamaño de las operaciones en una lista (cuando se llama a list.add(...) ) es costoso y uno debe tratar de establecer la capacidad inicial en un nivel adecuado cuando sea posible (tenga en cuenta que el mismo problema surge cuando se usa una matriz)
  • cuando se trata de primitivas, las matrices pueden ser significativamente más rápidas ya que le permitirán evitar muchas conversiones de boxeo / desempaquetado
  • una aplicación que solo obtiene / establece valores en una ArrayList (¡no es muy común!) podría ver una ganancia de rendimiento de más del 25% al ​​cambiar a una matriz

Resultados detallados

Aquí están los resultados que midí para esas tres operaciones usando la biblioteca de benchmarking jmh (tiempos en nanosegundos) con JDK 7 en una máquina de escritorio x86 estándar. Tenga en cuenta que ArrayList nunca se redimensiona en las pruebas para garantizar que los resultados sean comparables. Código de referencia disponible aquí .

Array / ArrayList Creation

Ejecuté 4 pruebas, ejecutando las siguientes afirmaciones:

  • createArray1: Integer[] array = new Integer[1];
  • createList1: List list = new ArrayList<> (1);
  • createArray10000: Integer[] array = new Integer[10000];
  • createList10000: List list = new ArrayList<> (10000);

Resultados (en nanosegundos por llamada, 95% de confianza):

 apgaArrayVsList.CreateArray1 [10.933, 11.097] apgaArrayVsList.CreateList1 [10.799, 11.046] apgaArrayVsList.CreateArray10000 [394.899, 404.034] apgaArrayVsList.CreateList10000 [396.706, 401.266] 

Conclusión: no hay diferencia notable .

obtener operaciones

Ejecuté 2 pruebas, ejecutando las siguientes afirmaciones:

  • getList: return list.get(0);
  • getArray: return array[0];

Resultados (en nanosegundos por llamada, 95% de confianza):

 apgaArrayVsList.getArray [2.958, 2.984] apgaArrayVsList.getList [3.841, 3.874] 

Conclusión: obtener un array es aproximadamente un 25% más rápido que obtener un ArrayList, aunque la diferencia es del orden de un nanosegundo.

establecer operaciones

Ejecuté 2 pruebas, ejecutando las siguientes afirmaciones:

  • setList: list.set(0, value);
  • setArray: array[0] = value;

Resultados (en nanosegundos por llamada):

 apgaArrayVsList.setArray [4.201, 4.236] apgaArrayVsList.setList [6.783, 6.877] 

Conclusión: establecer operaciones en matrices es aproximadamente un 40% más rápido que en listas, pero, en cuanto a get, cada operación de conjunto tarda unos pocos nanosegundos, por lo que para que la diferencia llegue a 1 segundo, uno tendría que establecer elementos en la lista / array cientos de millones de veces!

clon / copia

El constructor de copia de ArrayList delega en Arrays.copyOf por lo que el rendimiento es idéntico al de la matriz (copiar una matriz mediante clone , Arrays.copyOf o System.arrayCopy no hace diferencia de rendimiento en cuanto al rendimiento ).

Supongo que el póster original proviene de un fondo C ++ / STL que está causando cierta confusión. En C ++ std::list es una lista doblemente vinculada.

En Java [java.util.]List es una interfaz libre de implementación (clase abstracta pura en términos de C ++). List puede ser una lista doblemente vinculada: se proporciona java.util.LinkedList . Sin embargo, 99 de cada 100 veces cuando desea crear una nueva List , desea usar java.util.ArrayList lugar, que es el equivalente aproximado de C ++ std::vector . Existen otras implementaciones estándar, como las devueltas por java.util.Collections.emptyList() y java.util.Arrays.asList() .

Desde el punto de vista del rendimiento, hay un impacto muy pequeño por tener que pasar por una interfaz y un objeto adicional, sin embargo, el tiempo de ejecución en línea significa que esto rara vez tiene algún significado. Recuerde también que String suele ser un objeto más una matriz. Entonces, para cada entrada, probablemente tenga otros dos objetos. En C ++ std::vector , aunque copiando por valor sin un puntero como tal, las matrices de caracteres formarán un objeto para la cadena (y por lo general no se compartirán).

Si este código en particular es realmente sensible al rendimiento, puede crear una sola matriz char[] (o incluso byte[] ) para todos los caracteres de todas las cadenas, y luego una matriz de desplazamientos. IIRC, así es como se implementa javac.

Bueno, en primer lugar, vale la pena aclarar ¿se refiere a “lista” en el sentido clásico de comp estructura de datos de ciencia (es decir, una lista vinculada) o te refieres a java.util.List? Si te refieres a java.util.List, es una interfaz. Si desea utilizar una matriz, simplemente utilice la implementación de ArrayList y obtendrá un comportamiento y semántica similares a los de una matriz. Problema resuelto.

Si se refiere a una matriz frente a una lista vinculada, es un argumento ligeramente diferente para el cual volvemos a Big O (aquí hay una explicación sencilla en inglés si este es un término desconocido.

Formación;

  • Acceso aleatorio: O (1);
  • Insertar: O (n);
  • Eliminar: O (n).

Lista enlazada:

  • Acceso aleatorio: O (n);
  • Insertar: O (1);
  • Eliminar: O (1).

Así que eliges el que mejor se adapte a cómo cambias el tamaño de tu matriz. Si cambia el tamaño, inserta y borra mucho, entonces tal vez una lista vinculada sea una mejor opción. Lo mismo ocurre si el acceso aleatorio es raro. Usted menciona el acceso en serie. Si principalmente haces acceso en serie con muy poca modificación, entonces probablemente no importe cuál elijas.

Las listas vinculadas tienen una sobrecarga ligeramente mayor ya que, como usted dice, se trata de bloques de memoria potencialmente no contiguos y (efectivamente) indicadores para el siguiente elemento. Probablemente no sea un factor importante a menos que estés lidiando con millones de entradas.

Escribí un pequeño punto de referencia para comparar ArrayLists con matrices. En mi computadora portátil antigua, el tiempo para atravesar una lista de arrays de 5000 elementos, 1000 veces, fue aproximadamente 10 milisegundos más lento que el código de matriz equivalente.

Entonces, si no hace más que repetir la lista, y lo está haciendo mucho, entonces tal vez valga la pena la optimización. De lo contrario, usaría la Lista, porque lo hará más fácil cuando necesite optimizar el código.

nb Me di cuenta de que usar for String s: stringsList era aproximadamente un 50% más lento que usar un for-loop antiguo para acceder a la lista. Ve figura … Aquí están las dos funciones que cronometré; el conjunto y la lista se llenaron con 5000 cadenas aleatorias (diferentes).

 private static void readArray(String[] strings) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < strings.length; i++) { totalchars += strings[i].length(); } } } private static void readArrayList(List stringsList) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < stringsList.size(); i++) { totalchars += stringsList.get(i).length(); } } } 

Estoy de acuerdo en que en la mayoría de los casos debe elegir la flexibilidad y elegancia de ArrayLists en las matrices, y en la mayoría de los casos, el impacto en el rendimiento del progtwig será insignificante.

Sin embargo, si realiza iteraciones constantes y pesadas con pocos cambios estructurales (no agrega ni elimina) para, por ejemplo, renderizado de gráficos de software o una máquina virtual personalizada, mis pruebas de evaluación comparativa de acceso secuencial muestran que las ArrayLists son 1.5 veces más lentas que las matrices en mi sistema (Java 1.6 en mi iMac de un año).

Cierto código:

 import java.util.*; public class ArrayVsArrayList { static public void main( String[] args ) { String[] array = new String[300]; ArrayList list = new ArrayList(300); for (int i=0; i<300; ++i) { if (Math.random() > 0.5) { array[i] = "abc"; } else { array[i] = "xyz"; } list.add( array[i] ); } int iterations = 100000000; long start_ms; int sum; start_ms = System.currentTimeMillis(); sum = 0; for (int i=0; i 

No, porque técnicamente, la matriz solo almacena la referencia a las cadenas. Las cadenas se asignan en una ubicación diferente. Para mil artículos, diría que una lista sería mejor, es más lenta, pero ofrece más flexibilidad y es más fácil de usar, especialmente si va a redimensionarlos.

Si tiene miles, considere usar un trie. Un trie es una estructura arborescente que combina los prefijos comunes de la cadena almacenada.

Por ejemplo, si las cadenas fueran

 intern international internationalize internet internets 

El trie almacenaría:

 intern -> \0 international -> \0 -> ize\0 net ->\0 ->s\0 

Las cadenas requieren 57 caracteres (incluido el terminador nulo, ‘\ 0’) para el almacenamiento, más el tamaño del objeto String que los contenga. (En verdad, probablemente deberíamos redondear todos los tamaños hasta múltiplos de 16, pero …) Llámalo 57 + 5 = 62 bytes, aproximadamente.

El trie requiere 29 (incluido el terminador nulo, ‘\ 0’) para el almacenamiento, más el tamaño de los nodos trie, que son una referencia a una matriz y una lista de nodos secundarios.

Para este ejemplo, probablemente salga igual; para miles, probablemente salga menos siempre que tenga prefijos comunes.

Ahora, cuando uses el trie en otro código, tendrás que convertir a String, probablemente usando un StringBuffer como intermediario. Si muchas de las cadenas están en uso a la vez como Strings, fuera del trie, es una pérdida.

Pero si solo usa unos pocos en el momento, por ejemplo, para buscar cosas en un diccionario, el trie puede ahorrarle mucho espacio. Definitivamente menos espacio que almacenarlos en un HashSet.

Usted dice que los está accediendo “en serie”; si eso significa secuencialmente en orden alfabético, el trie también le da obviamente orden alfabético de forma gratuita, si lo itera primero en profundidad.

ACTUALIZAR:

Como Mark notó, no hay una diferencia significativa después del calentamiento de JVM (varios pases de prueba). Comprobado con una matriz re-creada o incluso un nuevo pase comenzando con una nueva fila de matriz. Con gran probabilidad esto indica que la matriz simple con acceso a índice no debe usarse a favor de las colecciones.

Sin embargo, primero 1-2 pases de matriz simple es 2-3 veces más rápido.

POSTE ORIGINAL:

Demasiadas palabras para el tema demasiado simple de verificar. Sin ningún tipo de matriz de preguntas es mucho más rápido que cualquier contenedor de clase . Corro en esta pregunta buscando alternativas para mi sección de desempeño crítico. Aquí está el código prototipo que construí para verificar la situación real:

 import java.util.List; import java.util.Arrays; public class IterationTest { private static final long MAX_ITERATIONS = 1000000000; public static void main(String [] args) { Integer [] array = {1, 5, 3, 5}; List list = Arrays.asList(array); long start = System.currentTimeMillis(); int test_sum = 0; for (int i = 0; i < MAX_ITERATIONS; ++i) { // for (int e : array) { for (int e : list) { test_sum += e; } } long stop = System.currentTimeMillis(); long ms = (stop - start); System.out.println("Time: " + ms); } } 

Y aquí está la respuesta:

Basado en una matriz (la línea 16 está activa):

 Time: 7064 

Según la lista (la línea 17 está activa):

 Time: 20950 

¿Algún comentario más sobre "más rápido"? Esto es bastante comprendido. La pregunta es cuando aproximadamente 3 veces más rápido es mejor para usted que la flexibilidad de la Lista. Pero esta es otra pregunta. Por cierto, también verifiqué esto basado en ArrayList construido manualmente. Casi el mismo resultado.

Dado que ya hay muchas buenas respuestas aquí, me gustaría ofrecerle otra información de vista práctica, que es la comparación del rendimiento de inserción e iteración: matriz primitiva vs Lista enlazada en Java.

Esta es una verificación de rendimiento simple real.
Entonces, el resultado dependerá del rendimiento de la máquina.

El código fuente utilizado para esto está a continuación:

 import java.util.Iterator; import java.util.LinkedList; public class Array_vs_LinkedList { private final static int MAX_SIZE = 40000000; public static void main(String[] args) { LinkedList lList = new LinkedList(); /* insertion performance check */ long startTime = System.currentTimeMillis(); for (int i=0; i 

El resultado del rendimiento está a continuación:

enter image description here

Recuerde que una ArrayList encapsula una matriz, por lo que hay poca diferencia en comparación con el uso de una matriz primitiva (excepto por el hecho de que una lista es mucho más fácil de trabajar en Java).

Casi la única vez que tiene sentido preferir una matriz a una ArrayList es cuando está almacenando primitivas, es decir, byte, int, etc. y necesita la eficiencia de espacio particular que obtiene mediante el uso de matrices primitivas.

La elección de Array vs. List no es tan importante (considerando el rendimiento) en el caso de almacenar objetos de cadena. Porque tanto la matriz como la lista almacenarán referencias de objetos de cadena, no los objetos reales.

  1. Si el número de cadenas es casi constante, utiliza una matriz (o ArrayList). Pero si el número varía demasiado, será mejor que uses LinkedList.
  2. Si hay (o habrá) una necesidad de agregar o eliminar elementos en el medio, entonces ciertamente debe usar LinkedList.

Si sabes de antemano qué tan grande es la información, entonces una matriz será más rápida.

Una lista es más flexible. Puede usar una ArrayList respaldada por una matriz.

la lista es más lenta que las matrices.Si necesita matrices de uso eficiente.Si necesita una lista de uso flexible.

Si puedes vivir con un tamaño fijo, las matrices serán más rápidas y necesitarán menos memoria.

Si necesita la flexibilidad de la interfaz de la Lista para agregar y eliminar elementos, la pregunta sigue siendo qué implementación debe elegir. A menudo ArrayList se recomienda y se usa para cualquier caso, pero también ArrayList tiene sus problemas de rendimiento si los elementos al principio o en el medio de la lista deben ser eliminados o insertados.

Por lo tanto, es posible que desee echarle un vistazo a http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list que presenta GapList. Esta nueva implementación de listas combina las fortalezas de ArrayList y LinkedList, lo que resulta en un muy buen rendimiento para casi todas las operaciones.

Dependiendo de la implementación. es posible que una matriz de tipos primitivos sea más pequeña y más eficiente que ArrayList. Esto se debe a que la matriz almacenará los valores directamente en un bloque contiguo de memoria, mientras que la implementación más simple de ArrayList almacenará los punteros a cada valor. Especialmente en una plataforma de 64 bits, esto puede marcar una gran diferencia.

Por supuesto, es posible que la implementación de jvm tenga un caso especial para esta situación, en cuyo caso el rendimiento será el mismo.

La lista es la forma preferida en Java 1.5 y más allá ya que puede usar generics. Las matrices no pueden tener generics. Además, las matrices tienen una longitud predefinida, que no puede crecer dinámicamente. Inicializar una matriz con un tamaño grande no es una buena idea. ArrayList es la forma de declarar una matriz con generics y puede crecer dinámicamente. Pero si eliminar e insertar se usa con más frecuencia, entonces la lista vinculada es la estructura de datos más rápida que se utilizará.

Las matrices recomendadas en todas partes pueden usarse en lugar de en la lista, especialmente en caso de que, si sabe, el recuento de elementos y el tamaño no cambien.

Consulte las mejores prácticas de Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

Por supuesto, si necesita agregar y eliminar objetos de la colección muchas veces listas de fácil uso.

ArrayList almacena sus elementos en una matriz Object[] y utiliza el método toArray tipo para toArray , que es mucho más rápido (la barra azul) que el tipeado. Esto es seguro, ya que la matriz sin tipo está envuelta en el tipo genérico ArrayList que comprueba el comstackdor.

enter image description here

Este gráfico muestra un punto de referencia con n = 5 en Java 7. Sin embargo, la imagen no cambia mucho con más elementos u otra máquina virtual. La sobrecarga de la CPU puede no parecer drástica, pero se sum. Lo más probable es que los consumidores de una matriz tengan que convertirla en una colección para hacer algo con ella, luego convertir el resultado a una matriz para alimentarlo a otro método de interfaz, etc. Usar una simple ArrayList lugar de una matriz mejora el rendimiento, sin agregar mucha huella. ArrayList agrega una sobrecarga constante de 32 bytes a la matriz envuelta. Por ejemplo, una array con diez objetos requiere 104 bytes, una ArrayList 136 bytes.

Esta operación se realiza en tiempo constante, por lo que es mucho más rápido que cualquiera de los anteriores (barra amarilla). Esto no es lo mismo que una copia defensiva. Una colección no modificable cambiará cuando cambien sus datos internos. Si esto sucede, los clientes pueden ejecutar una ConcurrentModificationException mientras iteran sobre los elementos. Se puede considerar un mal diseño que una interfaz proporcione métodos que generen una UnsupportedOperationException en tiempo de ejecución. Sin embargo, al menos para uso interno, este método puede ser una alternativa de alto rendimiento a una copia defensiva, algo que no es posible con las matrices.

Ninguna de las respuestas tenía información que me interesaba: análisis repetitivo de la misma matriz muchas veces. Tuve que crear una prueba de JMH para esto.

Resultados (Java 1.8.0_66 x32, iterating plain array es al menos 5 veces más rápido que ArrayList):

 Benchmark Mode Cnt Score Error Units MyBenchmark.testArrayForGet avgt 10 8.121 ? 0.233 ms/op MyBenchmark.testListForGet avgt 10 37.416 ? 0.094 ms/op MyBenchmark.testListForEach avgt 10 75.674 ? 1.897 ms/op 

Prueba

 package my.jmh.test; import java.util.ArrayList; import java.util.List; import java.util.concurrent.TimeUnit; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Measurement; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OutputTimeUnit; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.annotations.Warmup; @State(Scope.Benchmark) @Fork(1) @Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS) @Measurement(iterations = 10) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) public class MyBenchmark { public final static int ARR_SIZE = 100; public final static int ITER_COUNT = 100000; String arr[] = new String[ARR_SIZE]; List list = new ArrayList<>(ARR_SIZE); public MyBenchmark() { for( int i = 0; i < ARR_SIZE; i++ ) { list.add(null); } } @Benchmark public void testListForEach() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( String str : list ) { if( str != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testListForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( list.get(j) != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testArrayForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( arr[j] != null ) count++; } } if( count > 0 ) System.out.print(count); } } 

“Thousands” is not a large number. A few thousand paragraph-length strings are on the order of a couple of megabytes in size. If all you want to do is access these serially, use an immutable singly-linked List .

Don’t get into the trap of optimizing without proper benchmarking. As others have suggested use a profiler before making any assumption.

The different data structures that you have enumerated have different purposes. A list is very efficient at inserting elements in the beginning and at the end but suffers a lot when accessing random elements. An array has fixed storage but provides fast random access. Finally an ArrayList improves the interface to an array by allowing it to grow. Normally the data structure to be used should be dictated by how the data stored will be access or added.

About memory consumption. You seem to be mixing some things. An array will only give you a continuous chunk of memory for the type of data that you have. Don’t forget that java has a fixed data types: boolean, char, int, long, float and Object (this include all objects, even an array is an Object). It means that if you declare an array of String strings [1000] or MyObject myObjects [1000] you only get a 1000 memory boxes big enough to store the location (references or pointers) of the objects. You don’t get a 1000 memory boxes big enough to fit the size of the objects. Don’t forget that your objects are first created with “new”. This is when the memory allocation is done and later a reference (their memory address) is stored in the array. The object doesn’t get copied into the array only it’s reference.

I don’t think it makes a real difference for Strings. What is contiguous in an array of strings is the references to the strings, the strings themselves are stored at random places in memory.

Arrays vs. Lists can make a difference for primitive types, not for objects. IF you know in advance the number of elements, and don’t need flexibility, an array of millions of integers or doubles will be more efficient in memory and marginally in speed than a list, because indeed they will be stored contiguously and accessed instantly. That’s why Java still uses arrays of chars for strings, arrays of ints for image data, etc.

Array is faster – all memory is pre-allocated in advance.

A lot of microbenchmarks given here have found numbers of a few nanoseconds for things like array/ArrayList reads. This is quite reasonable if everything is in your L1 cache.

A higher level cache or main memory access can have order of magnitude times of something like 10nS-100nS, vs more like 1nS for L1 cache. Accessing an ArrayList has an extra memory indirection, and in a real application you could pay this cost anything from almost never to every time, depending on what your code is doing between accesses. And, of course, if you have a lot of small ArrayLists this might add to your memory use and make it more likely you’ll have cache misses.

The original poster appears to be using just one and accessing a lot of contents in a short time, so it should be no great hardship. But it might be different for other people, and you should watch out when interpreting microbenchmarks.

Java Strings, however, are appallingly wasteful, especially if you store lots of small ones (just look at them with a memory analyzer, it seems to be > 60 bytes for a string of a few characters). An array of strings has an indirection to the String object, and another from the String object to a char[] which contains the string itself. If anything’s going to blow your L1 cache it’s this, combined with thousands or tens of thousands of Strings. So, if you’re serious – really serious – about scraping out as much performance as possible then you could look at doing it differently. You could, say, hold two arrays, a char[] with all the strings in it, one after another, and an int[] with offsets to the starts. This will be a PITA to do anything with, and you almost certainly don’t need it. And if you do, you’ve chosen the wrong language.

I came here to get a better feeling for the performance impact of using lists over arrays. I had to adapt code here for my scenario: array/list of ~1000 ints using mostly getters, meaning array[j] vs. list.get(j)

Taking the best of 7 to be unscientific about it (first few with list where 2.5x slower) I get this:

 array Integer[] best 643ms iterator ArrayList best 1014ms iterator array Integer[] best 635ms getter ArrayList best 891ms getter (strange though) 

– so, very roughly 30% faster with array

The second reason for posting now is that no-one mentions the impact if you do math/matrix/simulation/optimization code with nested loops.

Say you have three nested levels and the inner loop is twice as slow you are looking at 8 times performance hit. Something that would run in a day now takes a week.

*EDIT Quite shocked here, for kicks I tried declaring int[1000] rather than Integer[1000]

 array int[] best 299ms iterator array int[] best 296ms getter 

Using Integer[] vs. int[] represents a double performance hit, ListArray with iterator is 3x slower than int[]. Really thought Java’s list implementations were similar to native arrays…

Code for reference (call multiple times):

  public static void testArray() { final long MAX_ITERATIONS = 1000000; final int MAX_LENGTH = 1000; Random r = new Random(); //Integer[] array = new Integer[MAX_LENGTH]; int[] array = new int[MAX_LENGTH]; List list = new ArrayList() {{ for (int i = 0; i < MAX_LENGTH; ++i) { int val = r.nextInt(); add(val); array[i] = val; } }}; long start = System.currentTimeMillis(); int test_sum = 0; for (int i = 0; i < MAX_ITERATIONS; ++i) { // for (int e : array) // for (int e : list) for (int j = 0; j < MAX_LENGTH; ++j) { int e = array[j]; // int e = list.get(j); test_sum += e; } } long stop = System.currentTimeMillis(); long ms = (stop - start); System.out.println("Time: " + ms); } 

It depends on how you have to access it.

After storing, if you mainly want to do search operation, with little or no insert/delete, then go for Array (as search is done in O(1) in arrays, whereas add/delete may need re-ordering of the elements).

After storing, if your main purpose is to add/delete strings, with little or no search operation, then go for List.

ArrayList internally uses array object to add(or store) the elements. In other words, ArrayList is backed by Array data -structure.The array of ArrayList is resizable (or dynamic).

Array is faster than Array because ArrayList internally use array. if we can directly add elements in Array and indirectly add element in Array through ArrayList always directly mechanism is faster than indirectly mechanism.

There are two overloaded add() methods in ArrayList class:
1. add(Object) : adds object to the end of the list.
2. add(int index , Object ) : inserts the specified object at the specified position in the list.

How the size of ArrayList grows dynamically?

 public boolean add(E e) { ensureCapacity(size+1); elementData[size++] = e; return true; } 

Important point to note from above code is that we are checking the capacity of the ArrayList , before adding the element. ensureCapacity() determines what is the current size of occupied elements and what is the maximum size of the array. If size of the filled elements (including the new element to be added to the ArrayList class) is greater than the maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So what happens internally is new Array is created with capacity

Till Java 6

 int newCapacity = (oldCapacity * 3)/2 + 1; 

(Update) From Java 7

  int newCapacity = oldCapacity + (oldCapacity >> 1); 

also, data from the old array is copied into the new array.

Having overhead methods in ArrayList that’s why Array is faster than ArrayList .