¿Qué lista de implementación <Object> será la más rápida para escribir, leer y luego destruir?

Question

¿Cuál es la implementación más rápida de la lista (en java) en un escenario donde la lista se creará un elemento a la vez y luego se leerá un elemento a la vez? Las lecturas se realizarán con un iterador y luego la lista se destruirá.
Sé que la notación Big O para get es O (1) y add es O (1) para una ArrayList, mientras que LinkedList es O (n) para get y O (1) para add. ¿El iterador se comporta con la misma notación de Big O?

Answer 1

Depende en gran medida de si conoce el tamaño máximo de cada lista por adelantado.

Si lo hace, use ArrayList; sin duda será más rápido.

De lo contrario, probablemente tendrá que crear un perfil.Si bien el acceso al ArrayList es O (1), crearlo no es tan simple, debido al cambio de tamaño dinámico.

Otro punto a considerar es que la compensación del espacio-tiempo no es clara. Cada objeto Java tiene bastante sobrecarga. Si bien un ArrayList puede desperdiciar algo de espacio en las ranuras sobrantes, cada ranura tiene solo 4 bytes (o 8 en una JVM de 64 bits). Cada elemento de LinkedList tiene probablemente unos 50 bytes (quizás 100 en una JVM de 64 bits). Así que debe tener bastantes máquinas tragamonedas desperdiciadas en un ArrayList antes de que LinkedList gane realmente su supuesta ventaja de espacio. La localidad de referencia también es un factor, y también es preferible ArrayList.

En la práctica, casi siempre uso ArrayList.

Answer 2

Iterar a través de una lista vinculada es O (1) por elemento.

El tiempo de ejecución de Big O para cada opción es el mismo. Probablemente ArrayList sea más rápido debido a una mejor localidad de memoria, pero tendría que medirlo para estar seguro. Elija lo que haga que el código sea más claro.

Answer 3

primeros pensamientos:

• Refactor su código para no necesitar la lista.
• Simplificar los datos a un tipo de datos escalar, a continuación, utilizar: int []
• O incluso sólo tiene que utilizar una matriz de cualquier objeto que tenga: Object [] - John Gardner
• Inicializar la lista a tamaño completo: nueva ArrayList (123);

Por supuesto, como todos los demás mencionan, realice pruebas de rendimiento, demuestre que su nueva solución es una mejora.

Answer 4

Sugiero compararlo. Una cosa es leer la API, pero hasta que no la pruebes, sería académica.

debe ser justo fácil de probar, simplemente asegúrese de hacer operaciones significativas, o punto de acceso saldrá a la luz inteligente que usted y optimizar todo a un no-op :)

Answer 5

Tenga en cuenta que iteración a través de una instancia de LinkedList puede ser O (n^2) si se hace ingenuamente. Específicamente:

List<Object> list = new LinkedList<Object>(); 
for (int i = 0; i < list.size(); i++) { 
    list.get(i); 
} 

Esto es absolutamente horrible en términos de eficiencia debido al hecho de que la lista debe ser atravesada hasta i dos veces para cada iteración. Si usted hace uso de LinkedList, asegúrese de usar un Iterator o de Java 5 mejorada for -loop:

for (Object o : list) { 
    // ... 
} 

El código anterior es O (n), ya que la lista es atravesada statefully en el lugar.

Para evitar todas las molestias anteriores, simplemente use ArrayList. No siempre es la mejor opción (especialmente para la eficiencia del espacio), pero generalmente es una apuesta segura.

Answer 6

Es casi seguro que desee un ArrayList. Tanto la adición como la lectura son "tiempo constante amortizado" (es decir, O (1)) como se especifica en la documentación (tenga en cuenta que esto es cierto incluso si la lista tiene que aumentar su tamaño; está diseñado así, vea http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html). Si sabe aproximadamente la cantidad de objetos que almacenará, incluso se eliminará el aumento de tamaño de ArrayList.

Agregar al final de una lista vinculada es O (1), pero el multiplicador constante es mayor que ArrayList (ya que generalmente se crea un objeto nodo cada vez). La lectura es prácticamente idéntica a ArrayList si está utilizando un iterador.

Es una buena regla usar siempre la estructura más simple posible, a menos que haya una buena razón para no hacerlo. Aquí no hay tal razón.

La cita exacta de la documentación de ArrayList es: "La operación de adición se ejecuta en tiempo constante amortizado, es decir, agregar elementos n requiere O (n) tiempo. Todas las demás operaciones se ejecutan en tiempo lineal (en términos generales) . El factor constante es bajo comparado con el de la implementación LinkedList ".

Answer 7

De hecho, he empezado a pensar que se debe evitar el uso de estructuras de datos con un comportamiento no determinista, como ArrayList o HashMap, por lo que yo diría que solo use ArrayList si puede enlazar su tamaño; cualquier lista ilimitada usa LinkedList. Sin embargo, eso se debe a que, principalmente, codigo sistemas con requisitos de tiempo casi real.

El problema principal es que cualquier asignación de memoria (que podría ocurrir al azar con cualquier operación de adición) también podría causar una recolección de elementos no utilizados, y cualquier recolección de elementos no utilizados puede hacer que pierda un objetivo. Cuanto mayor sea la asignación, más probabilidades habrá de que esto ocurra, y esto también se agravará si está utilizando el recopilador de CMS. CMS no es compactante, por lo que encontrar espacio para un nuevo nodo de lista enlazado generalmente será más fácil que encontrar espacio para una nueva matriz de 10.000 elementos.

Cuanto más riguroso sea su enfoque de codificación, más cerca podrá estar en tiempo real con una JVM estándar. Pero elegir solo estructuras de datos con un comportamiento determinista es uno de los primeros pasos que debería tomar.

Answer 8

Hay una nueva implementación de lista llamada GlueList que es más rápida que todas las implementaciones de listas clásicas.