metodos example ejemplo java arrays performance list containers

example - Array o lista en Java. ¿Cual es mas rápido?



arraylist string java (30)

ArrayList utiliza internamente el objeto de matriz para agregar (o almacenar) los elementos. En otras palabras, ArrayList está respaldado por Array data -structure. La matriz de ArrayList es redimensionable (o dinámica).

La matriz es más rápida que la matriz porque ArrayList utiliza internamente la matriz. Si podemos agregar elementos directamente en Array e indirectamente agregar elementos en Array a través de ArrayList, el mecanismo siempre directamente es más rápido que el mecanismo indirecto

Hay dos métodos add () sobrecargados en la clase ArrayList:
1 add(Object).: agrega un objeto al final de la lista.
2 add(int index , Object ).: inserta el objeto especificado en la posición especificada en la lista.

¿Cómo crece dinámicamente el tamaño de ArrayList?

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

El punto importante a tener en cuenta del código anterior es que estamos verificando la capacidad de ArrayList, antes de agregar el elemento. garantizarCapacidad () determina cuál es el tamaño actual de los elementos ocupados y cuál es el tamaño máximo de la matriz. Si el tamaño de los elementos rellenos (incluido el nuevo elemento que se agregará a la clase ArrayList) es mayor que el tamaño máximo de la matriz, aumente el tamaño de la matriz. Pero el tamaño de la matriz no se puede aumentar dinámicamente. Entonces, lo que sucede internamente es que la nueva matriz se crea con capacidad.

Hasta Java 6

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

(Actualización) Desde Java 7

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

Además, los datos de la matriz anterior se copian en la nueva matriz.

Tener métodos generales en ArrayList es por eso que Array es más rápido que ArrayList.

Tengo que mantener miles de cadenas en la memoria para poder acceder a ellas en serie en Java. ¿Debo almacenarlos en una matriz o debo usar algún tipo de lista?

Ya que los arreglos mantienen todos los datos en una porción contigua de memoria (a diferencia de las listas), ¿el uso de un arreglo para almacenar miles de cadenas causaría problemas?

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

"Miles" no es un número grande. Unos pocos miles de cadenas de longitud de párrafo son del orden de un par de megabytes de tamaño. Si todo lo que desea hacer es acceder a estos en serie, use una Lista inmutable de enlaces individuales .

ACTUALIZAR:

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

Aún así, primero 1-2 pasos de matriz simple es 2-3 veces más rápido.

POSTE ORIGINAL:

Demasiadas palabras para el tema demasiado fácil de comprobar. Sin ninguna pregunta, la matriz es varias veces más rápida que cualquier contenedor de clase . Me ocupo de esta pregunta en busca de alternativas para mi sección de rendimiento 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<Integer> 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 la matriz (la línea 16 está activa):

Time: 7064

Basado en la lista (la línea 17 está activa):

Time: 20950

¿Algún comentario más sobre ''más rápido''? Esto es bastante entendido. La pregunta es cuándo es 3 veces más rápido para usted que la flexibilidad de la Lista. Pero esta es otra pregunta. Por cierto, también verifiqué esto en base a ArrayList construido manualmente. Casi el mismo resultado.

Arreglos recomendados en todos los lugares donde puede usarlos en lugar de en la lista, especialmente en caso de que sepa que el conteo y el tamaño de los artículos no cambiarían.

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, las listas de uso fácil.

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

Hay algunas cosas que puedes hacer con una matriz:

  • crearlo
  • establecer un elemento
  • obtener un articulo
  • clonar / copiar

Conclusión general

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

  • las operaciones de cambio de tamaño en una lista (cuando se llama list.add(...) ) son costosas y se debe intentar establecer la capacidad inicial en un nivel adecuado cuando sea posible (tenga en cuenta que surge el mismo problema al usar una matriz)
  • cuando se trata de primitivas, las matrices pueden ser significativamente más rápidas, ya que 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 medí para esas tres operaciones utilizando la biblioteca de evaluación comparativa jmh (tiempos en nanosegundos) con JDK 7 en una máquina de escritorio x86 estándar. Tenga en cuenta que ArrayList nunca cambia de tamaño en las pruebas para asegurarse de que los resultados son comparables. Código de referencia disponible aquí .

Creación de Array / ArrayList

Corrí 4 pruebas, ejecutando las siguientes afirmaciones:

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

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

a.p.g.a.ArrayVsList.CreateArray1 [10.933, 11.097] a.p.g.a.ArrayVsList.CreateList1 [10.799, 11.046] a.p.g.a.ArrayVsList.CreateArray10000 [394.899, 404.034] a.p.g.a.ArrayVsList.CreateList10000 [396.706, 401.266]

Conclusión: no hay diferencia notable .

obtener operaciones

Corrí 2 pruebas, ejecutando las siguientes afirmaciones:

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

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

a.p.g.a.ArrayVsList.getArray [2.958, 2.984] a.p.g.a.ArrayVsList.getList [3.841, 3.874]

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

establecer operaciones

Corrí 2 pruebas, ejecutando las siguientes afirmaciones:

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

Resultados (en nanosegundos por llamada):

a.p.g.a.ArrayVsList.setArray [4.201, 4.236] a.p.g.a.ArrayVsList.setList [6.783, 6.877]

Conclusión: las operaciones de configuración en arrays son aproximadamente un 40% más rápidas que en las listas, pero, en cuanto a obtener, cada operación de configuración toma unos pocos nanosegundos, por lo que para que la diferencia llegue a 1 segundo, se deben configurar elementos en la lista / matriz. de millones de veces!

clonar / copiar

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

Bueno, en primer lugar, vale la pena aclarar qué quiere decir "lista" en el sentido clásico de las estructuras de datos comp sci (es decir, una lista enlazada) o quiere decir java.util.List? Si te refieres a java.util.List, es una interfaz. Si desea usar una matriz, solo use la implementación ArrayList y obtendrá un comportamiento y una semántica parecidos a una matriz. Problema resuelto.

Si te refieres a una matriz frente a una lista vinculada, es un argumento ligeramente diferente por el que volvemos a Big O (aquí hay una explicación en inglés simple 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 elige la que mejor se adapte a la forma en que redimensionas tu matriz. Si cambia el tamaño, inserta y elimina mucho, quizás una lista enlazada sea una mejor opción. Lo mismo vale si el acceso aleatorio es raro. Usted menciona el acceso serie. Si está haciendo principalmente el acceso en serie con muy poca modificación, entonces probablemente no importa cuál elija.

Las listas enlazadas tienen una sobrecarga ligeramente mayor, ya que, como usted dice, está tratando con bloques de memoria potencialmente no contiguos y con punteros (de manera efectiva) al siguiente elemento. Probablemente ese no sea un factor importante a menos que estés tratando con millones de entradas.

Como ya hay muchas respuestas buenas aquí, me gustaría brindarle otra información de vista práctica, que es la comparación de rendimiento de la inserción y la iteración: matriz primitiva frente a lista enlazada en Java.

Esta es la comprobación de rendimiento real simple.
Por lo tanto, el resultado dependerá del rendimiento de la máquina.

El código fuente utilizado para esto está abajo:

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<MAX_SIZE; i++) { lList.add(i); } long stopTime = System.currentTimeMillis(); long elapsedTime = stopTime - startTime; System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); int[] arr = new int[MAX_SIZE]; startTime = System.currentTimeMillis(); for(int i=0; i<MAX_SIZE; i++){ arr[i] = i; } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); /* iteration performance check */ startTime = System.currentTimeMillis(); Iterator itr = lList.iterator(); while(itr.hasNext()) { itr.next(); // System.out.println("Linked list running : " + itr.next()); } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); startTime = System.currentTimeMillis(); int t = 0; for (int i=0; i < MAX_SIZE; i++) { t = arr[i]; // System.out.println("array running : " + i); } stopTime = System.currentTimeMillis(); elapsedTime = stopTime - startTime; System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond."); } }

Resultado de rendimiento es a continuación:

Deberías preferir los tipos genéricos sobre los arrays. Como lo mencionaron otros, los arreglos son inflexibles y no tienen el poder expresivo de los tipos genéricos. (Sin embargo, sí admiten la comprobación de tipo en tiempo de ejecución, pero eso se mezcla mal con los tipos genéricos).

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

  • No optimice hasta que tenga una versión agradable, limpia y de trabajo de su código. El cambio a tipos genéricos podría estar muy motivado ya en este paso.
  • 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 mejoró las cosas, revertirla . Recuerde, el código sin la optimización fue limpio, agradable y funcional.

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 de memoria contiguo, 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 hacer 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.

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

Entonces, si no está haciendo nada más que iterar 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 for String s: stringsList que el uso for String s: stringsList era aproximadamente un 50% más lento que el uso de un bucle for de estilo antiguo para acceder a la lista. Vaya figura ... Aquí están las dos funciones que cronometré; la matriz y la lista se rellenaron 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<String> 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 la elegancia de las ArrayLists sobre las matrices, y en la mayoría de los casos, el impacto en el rendimiento del programa será insignificante.

Sin embargo, si está realizando una iteración pesada y constante con un pequeño cambio estructural (sin agregados ni eliminados) para, por ejemplo, la representación 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.5x más lentas que las matrices en mi sistema (Java 1.6 en mi iMac de un año).

Algún código:

import java.util.*; public class ArrayVsArrayList { static public void main( String[] args ) { String[] array = new String[300]; ArrayList<String> list = new ArrayList<String>(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<iterations; ++i) { for (int j=0; j<300; ++j) sum += array[j].length(); } System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" ); // Prints ~13,500 ms on my system start_ms = System.currentTimeMillis(); sum = 0; for (int i=0; i<iterations; ++i) { for (int j=0; j<300; ++j) sum += list.get(j).length(); } System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" ); // Prints ~20,800 ms on my system - about 1.5x slower than direct array access } }

La elección de la matriz frente a la lista no es tan importante (considerando el rendimiento) en el caso de almacenar objetos de cadena. Debido a que 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, use una matriz (o ArrayList). Pero si el número varía demasiado, será mejor que uses LinkedList.
  2. Si hay (o habrá) la necesidad de agregar o eliminar elementos en el medio, entonces ciertamente tiene que usar LinkedList.

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

List<String> strings = new ArrayList<String>();

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

Un ArrayList implementa el tipo de datos abstractos de lista utilizando una matriz como su implementación subyacente. La velocidad de acceso es prácticamente idéntica a una matriz, con las ventajas adicionales de poder agregar y restar elementos a una lista (aunque esta es una operación O (n) con una ArrayList) y eso si decide cambiar la implementación subyacente más adelante usted puede. Por ejemplo, si se da cuenta de que necesita un acceso sincronizado, puede cambiar la implementación a un Vector sin tener que volver a escribir todo el código.

De hecho, ArrayList se diseñó específicamente para reemplazar la construcción de matriz de bajo nivel en la mayoría de los contextos. Si Java se estuviera diseñando hoy, es completamente posible que los arreglos se hayan omitido totalmente a favor de la construcción ArrayList.

Ya que los arreglos mantienen todos los datos en una porción contigua de memoria (a diferencia de las listas), ¿el uso de un arreglo para almacenar miles de cadenas causaría problemas?

En Java, todas las colecciones almacenan solo referencias a objetos, no a los objetos en sí. 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 quedará sin memoria, por supuesto, solo que el bloque de requisitos de memoria contiguos no es difícil de cumplir.

La lista es la forma preferida en java 1.5 y posteriores, ya que puede usar genéricos. Las matrices no pueden tener genéricos. 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 manera de declarar una matriz con genéricos y puede crecer dinámicamente. Pero si eliminar e insertar se usa con más frecuencia, la lista enlazada es la estructura de datos más rápida que se usará.

Le sugiero que use un perfilador para probar que es más rápido.

Mi opinión personal es que debes usar listas.

Trabajo en una base de código grande y un grupo anterior de desarrolladores usó matrices en todas partes . Hizo el código muy inflexible. Después de cambiar grandes porciones de él a Listas, no notamos ninguna diferencia en la velocidad.

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

Resultados (Java 1.8.0_66 x32, la iteración de una matriz plana es al menos 5 veces más rápida 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<String> 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); } }

No entre en la trampa de la optimización sin una evaluación comparativa adecuada. Como otros han sugerido, use un perfilador antes de hacer cualquier suposición.

Las diferentes estructuras de datos que ha enumerado tienen diferentes propósitos. Una lista es muy eficiente para insertar elementos al principio y al final, pero sufre mucho al acceder a elementos aleatorios. Una matriz tiene almacenamiento fijo pero proporciona acceso aleatorio rápido. Finalmente, un ArrayList mejora la interfaz a una matriz al permitir que crezca. Normalmente, la estructura de datos que se utilizará debe ser dictada por la forma en que los datos almacenados serán accesados ​​o agregados.

Sobre el consumo de memoria.Pareces estar mezclando algunas cosas. Una matriz solo le dará una porción continua de memoria para el tipo de datos que tiene. No olvide que java tiene tipos de datos fijos: boolean, char, int, long, float y Object (esto incluye todos los objetos, incluso una matriz es un Object). Significa que si declara una matriz de cadenas de cadenas [1000] o MyObject myObjects [1000], solo obtiene 1000 cajas de memoria lo suficientemente grandes para almacenar la ubicación (referencias o punteros) de los objetos. No obtienes 1000 cajas de memoria lo suficientemente grandes para ajustarse al tamaño de los objetos. No olvides que tus objetos se crean primero con "nuevo". Esto es cuando la asignación de memoria se realiza y luego se almacena una referencia (su dirección de memoria) en la matriz. El objeto no se copia en la matriz solo su referencia.

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 cambiar su tamaño.

Recuerde que un 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 es mucho más fácil trabajar con una Lista en Java).

La mayor parte del tiempo que tiene sentido preferir una matriz a una ArrayList es cuando almacena primitivas, es decir, bytes, int, etc. y necesita la eficiencia de espacio particular que obtiene al usar matrices primitivas.

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 utiliza 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 eliminarse o insertarse.

Por lo tanto, puede querer echar un vistazo a http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list que introduce GapList. Esta nueva implementación de lista combina las fortalezas de ArrayList y LinkedList, lo que da como resultado un rendimiento muy bueno para casi todas las operaciones.

Si sabe de antemano cuán grandes son los datos, entonces una matriz será más rápida.

Una lista es más flexible. Puede utilizar un ArrayList que está respaldado por una matriz.

Si tienes miles, considera usar un trie. Un trie es una estructura en forma de árbol que combina los prefijos comunes de la cadena almacenada.

Por ejemplo, si las cuerdas 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 las contiene. (En realidad, probablemente deberíamos redondear todos los tamaños hasta múltiplos de 16, pero ...) Llámelo 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 trie secundarios.

Para este ejemplo, probablemente salga lo mismo; para miles, probablemente saldrá menos mientras tengas prefijos comunes.

Ahora, cuando use el trie en otro código, tendrá que convertir a String, probablemente usando un StringBuffer como intermediario. Si muchas de las cadenas se utilizan al mismo tiempo como cadenas, fuera del trío, es una pérdida.

Pero si solo está usando unos pocos a la vez, 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 está accediendo a ellos "en serie": si eso significa secuencialmente y alfabéticamente, el trie también obviamente le da orden alfabético gratis, si lo itera primero en profundidad.

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 enlazada.

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 con doble java.util.LinkedList se proporciona java.util.LinkedList . Sin embargo, 99 veces de cada 100 cuando desea crear una nueva List , desea usar java.util.ArrayList , que es el equivalente aproximado de C ++ std::vector . Hay 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 al tener que pasar por una interfaz y un objeto adicional, sin embargo, el tiempo de ejecución significa que esto rara vez tiene importancia. También recuerda que las String son típicamente un objeto más una matriz. Así que para cada entrada, probablemente tengas otros dos objetos. En C ++ std::vector<std::string> , aunque se copia por valor sin un puntero como tal, las matrices de caracteres formarán un objeto para la cadena (y generalmente no se compartirán).

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

la lista es más lenta que las matrices. Si necesita eficiencia, utilice matrices. Si necesita flexibilidad, utilice la lista.

ArrayList almacena sus elementos en una matriz Object[] y utiliza el método toArray tipo que es mucho más rápido (la barra azul) que el escrito. Esto es seguro contra tipos, ya que la matriz sin tipo se ajusta en el tipo genérico ArrayList<T> que el compilador comprueba.

Este cuadro muestra una 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 suma. Lo más probable es que los consumidores de una matriz tengan que convertirla en una colección para poder hacer algo con ella, y luego convertir el resultado de nuevo en una matriz para alimentarlo en otro método de interfaz, etc. Usar una ArrayList simple en lugar de una matriz mejora el rendimiento. sin añadir mucha huella. ArrayList agrega una sobrecarga constante de 32 bytes a la matriz envuelta. Por ejemplo, una array con diez objetos requiere 104 bytes, un ArrayList 136 bytes.

Esta operación se realiza en tiempo constante, por lo que es mucho más rápida que cualquiera de las 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 mal diseño que una interfaz proporcione métodos que arrojen 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 matrices.

Depende de cómo tengas que acceder.

Después del almacenamiento, si principalmente desea realizar una operación de búsqueda, con poco o nada de insertar / eliminar, vaya a Array (ya que la búsqueda se realiza en O (1) en los arreglos, mientras que agregar / eliminar puede necesitar reordenar los elementos) .

Después del almacenamiento, si su objetivo principal es agregar / eliminar cadenas, con poca o ninguna operación de búsqueda, vaya a Lista.

La matriz es más rápida: toda la memoria se asigna previamente de antemano.

Muchos de los microbenchmarks aquí encontrados han encontrado números de unos pocos nanosegundos para cosas como las lecturas array / ArrayList. Esto es bastante razonable si todo está en su caché L1.

Un caché de nivel superior o el acceso a la memoria principal pueden tener un orden de magnitud de tiempo de 10nS-100nS, en comparación con 1nS para el caché L1. El acceso a un ArrayList tiene una indirección de memoria adicional y, en una aplicación real, puede pagar este costo desde casi siempre hasta el momento, dependiendo de lo que haga su código entre accesos. Y, por supuesto, si tiene un montón de ArrayLists pequeñas, esto podría agregarse al uso de la memoria y hacer que sea más probable que tenga faltas de caché.

El póster original parece estar usando solo uno y accediendo a una gran cantidad de contenidos en poco tiempo, por lo que no debería ser una gran dificultad. Pero podría ser diferente para otras personas, y debe tener cuidado al interpretar las microbenchmark.

Sin embargo, las cadenas Java son terriblemente inútiles, especialmente si almacenas muchas pequeñas (solo con un analizador de memoria, parece ser> 60 bytes para una cadena de pocos caracteres). Una matriz de cadenas tiene una dirección indirecta al objeto String y otra desde el objeto String a un char [] que contiene la cadena en sí. Si algo va a hacer explotar tu caché L1 es esto, combinado con miles o decenas de miles de cuerdas. Por lo tanto, si usted es serio, realmente serio, acerca de obtener el mayor rendimiento posible, entonces podría hacerlo de manera diferente. Podría, digamos, mantener dos matrices, una char [] con todas las cadenas, una tras otra, y una int [] con desplazamientos a los inicios. Será un PITA para hacer cualquier cosa, y es casi seguro que no lo necesitas. Y si lo haces, tuHe elegido el lenguaje equivocado.

No creo que haga una diferencia real para Strings. Lo que es contiguo en una matriz de cadenas es las referencias a las cadenas, las cadenas se almacenan en lugares aleatorios en la memoria.

Arrays vs. Lists puede hacer una diferencia para los tipos primitivos, no para los objetos. Si conoce de antemano el número de elementos y no necesita flexibilidad, una matriz de millones de enteros o dobles será más eficiente en memoria y marginalmente en velocidad que en una lista, porque de hecho se almacenarán de forma contigua y se accederá al instante. Es por eso que Java todavía usa matrices de caracteres para cadenas, matrices de caracteres para datos de imagen, etc.

Vine aquí para tener una mejor idea del impacto en el rendimiento del uso de listas sobre matrices. Tuve que adaptar el código aquí para mi escenario: matriz / lista de ~ 1000 ints usando mayormente getters, lo que significa matriz [j] vs.

Tomando lo mejor de 7 para no ser científico al respecto (los primeros pocos con una lista donde es 2.5x más lento), obtengo esto:

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

- Entonces, muy aproximadamente un 30% más rápido con la matriz.

La segunda razón para publicar ahora es que nadie menciona el impacto si haces código de matemáticas / matriz / simulación / optimización con bucles anidados .

Digamos que tiene tres niveles anidados y que el bucle interno es dos veces más lento que lo que está viendo en 8 veces el impacto de rendimiento. Algo que correría en un día ahora toma una semana.

* EDITAR Muy impactado aquí, para patadas intenté declarar int [1000] en lugar de Integer [1000]

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

Usar Integer [] frente a int [] representa un doble acierto en el rendimiento, ListArray con iterador es 3 veces más lento que int []. Realmente pensé que las implementaciones de la lista de Java eran similares a las matrices nativas ...

Código de referencia (llamar varias veces):

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<Integer> list = new ArrayList<Integer>() {{ 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); }