224 votos

Matriz o Lista en Java. ¿Qué es más rápido?

Tengo que mantener a miles de cadenas en la memoria para ser visitada en serie en Java. ¿Debo almacenar en una matriz o debo de tomar algún tipo de lista?

Desde matrices mantienen todos los datos en un trozo contiguo de memoria (a diferencia de las listas), sería el uso de una matriz para almacenar miles de cuerdas causan problemas?

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

254voto

Fortyrunner Puntos 8072

Le sugiero que use un generador de perfiles para probar que es más rápido.

Mi opinión personal es que se debe utilizar listas.

Yo trabajo en una gran base de código y un grupo anterior de desarrolladores utilizado matrices en todas partes. Esto hizo que el código muy inflexible. Después de cambiar grandes trozos de la misma a las listas que notamos ninguna diferencia en la velocidad.

115voto

cygil Puntos 2076

El Java es que usted debe considerar lo que los datos de abstracción más se adapte a tus necesidades. Recuerda que en Java una Lista es un resumen, no un concreto tipo de datos. Usted debe declarar las cadenas como una Lista y, a continuación, inicie el uso de la ArrayList aplicación.

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

Esta separación de Tipo de Datos Abstracto y de la implementación específica es uno de los aspectos clave de la programación orientada a objetos.

Un ArrayList implementa la Lista Tipo de Datos Abstracto utilizando una matriz como de su implementación subyacente. La velocidad de acceso es prácticamente idéntica a la de una matriz, con las ventajas adicionales de ser capaz de sumar y restar elementos de una Lista (aunque esta es una operación O(n) con un objeto ArrayList) y que si decide cambiar la implementación subyacente más tarde usted puede. Por ejemplo, si usted se da cuenta de que necesita acceso sincronizado, puede cambiar la implementación de un Vector sin tener que reescribir todo el código.

De hecho, el ArrayList fue específicamente diseñado para reemplazar el bajo nivel de la matriz de la construcción en la mayoría de los contextos. Si Java se diseñó el día de hoy, es muy posible que las matrices habría sido dejado de lado por completo en favor de la ArrayList construir.

Puesto que las matrices a mantener todos los datos en una contiguos fragmento de memoria (a diferencia de las Listas), sería el uso de una matriz para almacenar miles de cadenas de causa problemas ?

En Java, todas las colecciones de la tienda sólo las referencias a los objetos, no los objetos en sí. Ambas matrices y ArrayList se va a almacenar un par de miles de referencias en un arreglo contiguo, por lo que son esencialmente idénticas. Se puede considerar que un bloque contiguo de un par de miles de 32 bits referencias siempre va a estar disponible en hardware moderno. Esto no garantiza que no se ejecute fuera de la memoria por completo, por supuesto, que el bloque contiguo de memoria requisito no es difícil de cumplir.

72voto

JesperE Puntos 34356

Se debe preferir los tipos genéricos a través de matrices. Como se ha mencionado por otros, las matrices son inflexibles y no tienen el poder expresivo de los tipos genéricos. (No obstante, el apoyo de tiempo de ejecución de validación de tipos, sino que se mezcla mal con los tipos genéricos.)

Pero, como siempre, a la hora de optimizar siempre hay que seguir estos pasos:

  • No optimizar hasta que tenga un bonito, limpio, y de trabajo versión de su código. Cambio de los tipos genéricos podría muy bien ser motivado en este paso ya.
  • Cuando usted tiene una versión de lo que es bonito y limpio, decidir si es lo suficientemente rápido.
  • Si no es lo suficientemente rápida, medir su rendimiento. Este paso es importante por dos razones. Si no se puede medir no (1) conocer el impacto de las optimizaciones de hacer y (2) saber a dónde hay que optimizar.
  • Optimizar la parte más caliente de su código.
  • Vuelva a medir. Esto es tan importante como la medición de antes. Si la optimización no no mejorar las cosas, volverá. Recuerde, el código sin la optimización estaba limpio, agradable, y de trabajo.

59voto

assylias Puntos 102015

Aunque las respuestas que propone usar ArrayList hace sentido en la mayoría de los escenario, la pregunta de rendimiento relativo que realmente no ha sido contestada.

Hay un par de cosas que usted puede hacer con una matriz:

  • crear
  • establecer un elemento
  • obtener un punto
  • clonar/copiar

Conclusión General

A pesar de obtener y establecer las operaciones son algo más lento en un objeto ArrayList (resp. 1 y 3 nanosegundos por llamada en mi máquina), hay muy poca sobrecarga de uso de un objeto ArrayList frente de una matriz por el no-uso intensivo. Sin embargo, hay algunas cosas a tener en cuenta:

  • cambio de tamaño en una lista (cuando se llama a list.add(...)) son costosos y uno debe tratar de establecer la capacidad inicial en un nivel adecuado cuando sea posible (tenga en cuenta que el mismo problema se plantea cuando se utiliza una matriz)
  • cuando se trata con primitivas, las matrices pueden ser significativamente más rápido ya que permitirá evitar muchos boxing/unboxing de conversiones
  • una aplicación que sólo se obtiene/establece los valores de un ArrayList (no es muy común!) podría ver un aumento del rendimiento de más del 25% por el cambio a una matriz

Resultados detallados

Aquí están los resultados que se mide por los tres operaciones mediante el jmh evaluación comparativa de la biblioteca (a veces en nanosegundos) con JDK 7 en un x86 estándar de la máquina de sobremesa. Tenga en cuenta que ArrayList son nunca cambia de tamaño en las pruebas para asegurarse de que los resultados sean comparables. Referencia código disponible aquí.

Matriz/ArrayList Creación

Corrí 4 pruebas, la ejecución de las siguientes declaraciones:

  • 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);

Los resultados (en nanosegundos por llamada, de confianza del 95%):

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.

realizar las operaciones

Corrí 2 pruebas, la ejecución de las siguientes declaraciones:

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

Los resultados (en nanosegundos por llamada, de confianza del 95%):

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

Conclusión: la obtención de una matriz es de aproximadamente un 25% más rápido que conseguir a partir de un objeto ArrayList, aunque la diferencia es sólo en el orden de una milésima de segundo.

conjunto de las operaciones

Corrí 2 pruebas, la ejecución de las siguientes declaraciones:

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

Los 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: conjunto de operaciones sobre matrices son alrededor de 40% más rápido que en las listas, pero, como para obtener, cada operación tiene un par de nanosegundos - así que por la diferencia para llegar a 1 segundo, uno debe definir los elementos de la lista/de la matriz de cientos de millones de veces!

clon/copia

ArrayList del constructor de copia a los delegados a Arrays.copyOf por lo que el rendimiento es idéntico al de la matriz de copia (copia de una matriz a través de clone, Arrays.copyOf o System.arrayCopy no hace ninguna diferencia material en cuanto al rendimiento).

16voto

Supongo que el cartel original viene de un C++/STL de fondo, lo que está causando algo de confusión. En C++ std::list es una lista doblemente vinculada.

En Java [java.util.]List es una implementación libre de la interfaz (pura clase abstracta términos de C++). List puede ser una lista doblemente vinculada - java.util.LinkedList es proporcionado. Sin embargo, el 99 veces de cada 100 cuando quieras new List, desea utilizar java.util.ArrayList , que es el equivalente aproximado de C++ std::vector. Hay otras implementaciones estándar, tales como las devoluciones por java.util.Collections.emptyList y java.util.Arrays.asList.

De un rendimiento de punto de vista hay un muy pequeño golpe de tener que ir a través de una interfaz y un objeto adicional, sin embargo en tiempo de ejecución inline significa esto rara vez tiene un significado. También recuerde que String son (generalmente) en un objeto más de la matriz. Así, para cada entrada, usted probablemente tiene otros dos objetos. En C++ std::vector<std::string>, aunque la copia de valor sin un puntero como tal, las matrices de caracteres se forma un objeto de cadena (y estos no suelen ser compartidas).

Si este código en particular es realmente sensibles al rendimiento, puede crear un único char[] de la matriz (o, incluso, byte[]) para todos los caracteres de todas las cadenas, y, a continuación, una serie de compensaciones. Si mal no recuerdo, esta es la forma javac se implementa.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X