Diferencias de tiempos de insercion entre ArrayList y LinkedList. CU00921C.

[RaGa]

Hola.

Estuve analizando el ejercicio resuelto de la entrega CU00921C. Probándolo con algunos cambios obtuve resultados no satisfactorios cuyos motivos no logro explicar. Quisiera compartir esa experiencia.

Vamos al código:
La clase Programa tal como está en la entrega funciona correctamente. Los tiempos que aparecen por consola irán variando dependiendo de, no solo qué procesador uno tenga, si no también de "qué tan ocupado" esté el procesador al momento de ejecutarse el programa. Lo importante de ver en cada corrida del programa es la diferencia relativa de tiempos.

Ahora bien, supongamos que introducimos una modificación de orden al programa original.
Supongamos que la modificación consiste en: primero realizar la inserción de un elemento en la posición 0 de la lista listalinked, y luego la insersión de un objeto en posición 0 en la lista listaarray. Es decir, en vez de realizar primero la inserción en listaarray como lo hacía el programa original, empezamos por insertar en la lista listalinked.

Lo que uno esperaría es que los tiempos mantuvieran la misma diferencia relativa, pero no sucede así.
El programa codificado de esta manera muestra que la insersión en la lista listalinked será  incluso hasta más lenta que en la lista listaarray.
Esto es lo que causa sorpresa. Uno hubiera esperado se mantuviera la diferencia relativa de tiempos insumidos por los procesos, y que principalmente el tiempo insumido por listalinked fuese menor que el tiempo insumido por listaarray.

Presumo tal vez que este comportamiento observado esté relacionado con otro tipo de cuestiones (externas) más que a la perfomance de los 2 tipos de implimentaciones analizadas (ArrayList y LinkedList).

(La siguiente es la clase modificada con el cambio ya explicado)

Código: [Seleccionar]

/* Ejemplo Interface List aprenderaprogramar.com */

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

 

public class Programa {

    public static void main(String arg[]) {

            List<Persona> listaarray = new ArrayList<Persona>();

            List<Persona> listalinked = new LinkedList<Persona>();

            long antes;

            for(int i=0;i<10000;i++)

            {

               listaarray.add(new Persona(i,"Persona"+i,i));  // En este ejemplo cada persona lleva datos ficticios

                listalinked.add(new Persona(i,"Persona"+i,i));

            }

            System.out.println("Tiempo invertido en insertar una persona en listalinked (en nanosegundos):");

            antes = System.nanoTime();

            listalinked.add(0,new Persona(10001,"Prueba",10001)); // Inserción en posicion 0 de una persona

            System.out.println(System.nanoTime()- antes);

            System.out.println("Tiempo invertido en insertar una persona en listaarray (en nanosegundos):");

            antes = System.nanoTime();

            listaarray.add(0,new Persona(10001,"Prueba",10001));  // Inserción en posicion 0 de una persona

            System.out.println(System.nanoTime()- antes);

      }

}

[César Krall]

Hola! Es curioso he hecho pruebas con el código que has presentado frente al original y he obtenido esto:

Con el programa original del curso:

Tiempo invertido en insertar una persona en listaarray (en nanosegundos): 37644
Tiempo invertido en insertar una persona en listalinked (en nanosegundos): 8031


Con el programa modificado:

Tiempo invertido en insertar una persona en listalinked (en nanosegundos): 17530
Tiempo invertido en insertar una persona en listaarray (en nanosegundos): 15784



Efectivamente llama la atención, a mí también me ha sorprendido y no tengo la respuesta de por qué ocurre así. Puedo hacer un intento de explicación, pero es solo un intento. La explicación pasaría porque el tiempo de inserción se compone de dos partes, por un lado la recuperación desde memoria de la lista y por otro lado la inserción en sí. Cuando se accede a memoria, es posible que se esté recuperando un bloque entero de memoria donde están las dos listas. De este modo traer el bloque tendría un coste digamos que en torno a 15000, insertar en linkedlist en torno a 2000, saltar dentro de un bloque desde la posición de una lista a otra en torno a 6000 e insertar en arrayList en torno a 15000.

De este modo para el programa original tendríamos:

Recuperar bloque 15000 + insertar en arrayList 15000 = aprox. 30000

Saltar a otra lista 6000 + insertar en linked list 2000 = aprox. 8000


Para el programa modificado

Recuperar bloque 15000 + insertar en linked list 2000 = 17000

Saltar a otra lista 6000 + insertar en ArrayList 6000 = 12000

Los números no cuadran exactamente y seguramente la explicación es más compleja   

Saludos!

[RaGa]

Hola César.

Muy buena explicación, hay un error de números en la cuenta final pero se entendió perfectamente el planteo.
Intuía que se trataba de cuestiones no inherentes a la propia perfomance de las clases (ya que el API de Java nos marca claramente las bondades de una y otra clase).
Entre esas cuestiones que denominaba "externas" no había tenido en cuenta que el acceso a memoria es por bloques, y es allí en donde podría explicarse esta diferencias de resultados.
Muy gráfica tu explicación y como siempre con mucha claridad conceptual.

Si hay otro aporte que clarifique este fenómeno nos sería bienvenido también.

Saludos!

[Alex Rodríguez]

Hola, más que nada comentar que los tiempos de respuesta nunca deberían tomarse en consideración por una ejecución, ya que pueden estar desvirtuados por la situación puntual del computador. Los tiempos de respuesta considerados deberían idealmente estar medidos bajo ciertas condiciones y ser un valor medio de un conjunto amplio de repeticiones (repito que esto es idealmente).

Saludos