¿Qué lista < Objeto > ¿La implementación será la más rápida para una pasada de escritura, lectura, y luego destrucción?

Question

¿Cuál es la implementación de la lista más rápida (en java) en un escenario en el que la lista se creará un elemento a la vez y, posteriormente, 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 obtener es O (1) y agregar es O (1) para un ArrayList, mientras que LinkedList es O (n) para obtener y O (1) para agregar. ¿Se comporta el iterador con la misma notación Big O?

Answer 1

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

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

De lo contrario, probablemente tendrás que hacer un perfil. Si bien el acceso a ArrayList es O (1), su creación no es tan simple, debido al cambio de tamaño dinámico.

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

En la práctica, casi siempre uso ArrayList .

Answer 2

Primeros pensamientos:

• Refactoriza tu código para no necesitar la lista.
• Simplifique los datos a un tipo de datos escalar, luego use: int […] […]
• O incluso simplemente use una matriz de cualquier objeto que tenga: Objeto [] - John Gardner
• Inicialice la lista a tamaño completo: nueva ArrayList (123);

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

Answer 3

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 el ArrayList sea más rápido debido a la mejor ubicación de la memoria, pero tendrías que medirlo para estar seguro. Elige lo que haga que el código sea más claro.

Answer 4

Tenga en cuenta que la iteración a través de una instancia de LinkedList puede ser O (n ^ 2) si se hace de forma ingenua. 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 se debe recorrer hasta i dos veces para cada iteración. Si usa LinkedList , asegúrese de usar un Iterator o un mejorado para para -loop:

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

El código anterior es O (n), ya que la lista se recorre permanentemente en el lugar.

Para evitar todos los problemas anteriores, solo use ArrayList . No siempre es la mejor opción (especialmente para la eficiencia del espacio), pero generalmente es una apuesta segura.

Answer 5

Sugiero hacer una evaluación comparativa. Una cosa es leer el API, pero hasta que lo pruebes por ti mismo, sería académico.

Debería ser bastante fácil de probar, solo asegúrate de realizar operaciones significativas, o el punto de acceso lo superará y lo optimizará a un NO-OP :)

Answer 6

Es casi seguro que quieras una lista de arreglos . Tanto la suma 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 de manera que vea http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html ). Si conoce aproximadamente la cantidad de objetos que va a almacenar, incluso el aumento de tamaño de ArrayList se elimina.

Agregar al final de una lista enlazada es O (1), pero el multiplicador constante es más grande que ArrayList (ya que generalmente creas un objeto de nodo cada vez). La lectura es prácticamente idéntica a la ArrayList si está utilizando un iterador.

Es una buena regla usar siempre la estructura más simple que puedas, 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 n elementos requiere tiempo O (n). Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente hablando). El factor constante es bajo en comparación con el de la implementación de LinkedList. & Quot;

Answer 7

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

Answer 8

En realidad, he empezado a pensar que debería evitarse cualquier uso de estructuras de datos con un comportamiento no determinista, como ArrayList o HashMap, por lo que diría que solo use ArrayList si puede limitar su tamaño; cualquier lista ilimitada utiliza LinkedList. Sin embargo, esto se debe a que codifico principalmente sistemas con requisitos casi en tiempo real.

El problema principal es que cualquier asignación de memoria (que podría suceder aleatoriamente con cualquier operación de adición) también podría causar una recolección de basura, y cualquier recolección de basura puede hacer que pierda un objetivo. Cuanto mayor sea la asignación, más probable es que esto ocurra, y esto también se complica si está utilizando el recopilador CMS. CMS no es compacto, por lo que encontrar espacio para un nuevo nodo de lista enlazada 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 la codificación, más cerca podrá acercarse al tiempo real con una JVM estándar. Pero elegir solo las estructuras de datos con comportamiento determinista es uno de los primeros pasos que tendría que tomar.