que - list java español

Implementaciones de lista: ¿LinkedList realmente funciona tan mal frente a ArrayList y TreeList?

Question

Tomado del documento Apache TreeList :

Las siguientes estadísticas relativas de rendimiento son indicativas de esta clase:

             get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325

Continúa diciendo:

LinkedList rara vez es una buena opción de implementación. TreeList casi siempre es un buen reemplazo para él, aunque utiliza una cantidad ligeramente mayor de memoria.

Mis preguntas son:

• ¿Qué ArrayList con ArrayList add , insert y remove tiempos de aplastamiento de LinkedList ? ¿Deberíamos esperar, por ejemplo, que los casos de inserción y eliminación del mundo real sean muy favorables a ArrayList ?

• ¿Esta TreeList simplemente pone el clavo en el ataúd de la venerable LinkedList ?

Estoy tentado de concluir que han amortizado o ignorado los dolores de crecimiento de ArrayList , y no han tenido en cuenta los tiempos de inserción y eliminación de un artículo en una LinkedList que ya se ha localizado.

Answer 1

Debido a que una lista vinculada tiene que navegar nodo por nodo para llegar a cualquier parte de la lista (guardar el frente y probablemente el reverso dependiendo de la implementación) tiene sentido que los números sean tan altos.

Para agregar / insertar / eliminar en una LinkedList grande, tendría muchos saltos de un nodo a otro para llegar al lugar correcto.

Si hicieron la ArrayList del tamaño adecuado para comenzar con los dolores de crecimiento no será nada. Si ArrayList es pequeño, los dolores de crecimiento no importan.

Para LinkedList, si las operaciones están todas al principio de la lista, impactaría mucho menos que si estuvieran al final.

Lo que debe hacer es usar siempre la interfaz, por ejemplo: Lista al declarar variables y parámetros, luego puede cambiar la "nueva ListaEnlazada ();" a "new ArrayList ();" y perfila el código para ver cómo funciona en tu código específico.

Debido a la velocidad de no tener que saltar de un nodo a otro, de manera predeterminada siempre utilizo ArrayList en lugar de LinkedList.

Creo que la lista de árboles va a ser significativamente más rápida que ambas (incluso sin mirar el código). Los árboles están diseñados para ser rápidos.

Answer 2

La clave aquí es la complejidad de las operaciones de inserción / eliminación en las tres implementaciones de la lista. ArrayList tiene O (n) veces de inserción / eliminación para índices arbitrarios, pero es O (1) si la operación se encuentra al final de la lista. ArrayList también tiene la conveniencia de O (1) acceso para cualquier ubicación. LinkedList es similarmente O (n), pero es O (1) para operaciones en cualquiera de los extremos de la Lista (inicio y final) y O (n) acceso para posiciones arbitrarias. TreeList tiene complejidad O (logn) para todas las operaciones en cualquier posición.

Esto muestra claramente que TreeList es más rápido para listas lo suficientemente grandes como para insertar / eliminar en posiciones arbitrarias. Pero AFAIK, TreeLists se implementan como un árbol de búsqueda binario, y tiene una constante mucho mayor asociada con sus operaciones O (logn) que las operaciones similares con ArrayLists que son simplemente envoltorios alrededor de una matriz. Esto hace que TreeList realmente sea más lento para listas pequeñas. Además, si todo lo que hace es agregar elementos a una lista, el rendimiento O (1) de ArrayList / LinkedList es claramente más rápido. Además, a menudo el número de inserción / eliminación es mucho menor que el número de accesos, lo que hace que ArrayList sea más rápido en general en muchos casos. La inserción / eliminación de tiempo constante de LinkedList al final de la Lista lo hace mucho más rápido implementando estructuras de datos como Colas, Apilamientos y Deques.

Al final del día, todo depende de para qué necesitas una Lista exactamente. No hay una solución única para todos. Debe seleccionar la implementación más adecuada para su trabajo.

Answer 3

Para ArrayList, dado que se realiza con poca frecuencia, básicamente puede tener un costo insignificante. Si es realmente un problema, simplemente haga que la matriz sea más grande para comenzar.

Si tengo una lista pequeña, entonces tiene sentido usar LinkedList ya que hay un beneficio mínimo en ese punto. Si la lista va a ser larga, obviamente una TreeList tiene más sentido.

Si voy a hacer una gran cantidad de acceso aleatorio a una lista, entonces ArrayList tiene más sentido.

Qué contenedor usar realmente depende de lo que harás con él. No hay un contenedor correcto, ya que cada uno tiene sus fortalezas y debilidades, y con la experiencia se empieza a entender cuándo usarla.

Answer 4

Se debe a las estructuras de datos detrás de estas Colecciones. TreeList es un tree que permite lecturas, inserciones y eliminaciones relativamente rápidas (todas O (log n)). ArrayList utiliza una array para almacenar los datos, por lo que cuando inserta o quita, cada elemento de la matriz debe desplazarse hacia arriba o hacia abajo (O (n) el peor caso). Las matrices también tienen un tamaño fijo, por lo que si se desborda la capacidad de la matriz actual, se debe crear una nueva, más grande (por lo general el doble del tamaño de la última, para mantener el tamaño al mínimo). LinkedList usó ... una lista vinculada . Una lista vinculada generalmente tiene una referencia a los primeros (y algunas veces últimos) elementos en la lista. Luego, cada elemento de la lista hace referencia tanto al siguiente elemento de la lista (para una lista vinculada individualmente) como a los elementos siguientes y anteriores (para una lista con doble enlace). Debido a esto, para acceder a un elemento específico, debe recorrer cada elemento antes de llegar (O (n) el peor caso). Al insertar o eliminar elementos específicos, debe encontrar la posición para insertarlos o eliminarlos, lo que lleva tiempo (O (n) el peor caso). Sin embargo, hay muy poco costo para simplemente agregar otro elemento al principio o al final (O (1)).

Hay libros enteros escritos sobre estructuras de datos y cuándo usarlos, recomiendo leer sobre los más fundamentales.

Answer 5

Tenga en cuenta que ArrayList generalmente es más rápido que LinkedList, incluso cuando su código solo llama a los métodos que son tiempo constante para ambos. Por ejemplo, ArrayList.add () simplifica la copia de una sola variable e incrementa un contador cuando no se necesita cambiar el tamaño, mientras que LinkedList.add () también debe crear un nodo y establecer múltiples punteros. Además, los nodos de LinkedList requieren más memoria, lo que ralentiza su aplicación, y la recolección de basura debe tratar con los nodos.

Si necesita agregar o eliminar elementos de cualquier extremo de la lista, pero no requiere acceso aleatorio, un ArrayDeque es más rápido que una lista vinculada, aunque requiere Java 6.

Una ListaEnlazada tiene sentido para iterar a través de la lista y luego agregar o eliminar elementos en el medio, pero esa es una situación inusual.

Answer 6

Todas y cada una de las personas que respondieron aquí son correctas. Todos tienen razón en su idea de que depende en gran medida de su patrón de uso, es decir, no hay una lista única para todos. Pero en el momento de escribir, olvidaron mencionar (o eso, o soy un descuidado lector) un caso de uso cuando LinkedList está en el mejor: inserto colocado en un iterador. Eso significa que si no estás solo

LinkedList::add(int index, E element) 
          Inserts the specified element at the specified position in this list.

que parece ser el método que utilizaron para obtener las estadísticas, pero

iterator.insert(E element)

con un iterator obtenido a través de cualquiera

public abstract ListIterator<E> listIterator(int index)
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.

o

public Iterator<E> iterator()
Returns an iterator over the elements in this list (in proper sequence).

, entonces está obligado a obtener el mejor rendimiento de inserción arbitraria jamás. Eso implica, por supuesto, que puede limitar el número de llamadas a iterator () y listIterator (), y el número de movimientos del iterador a través de la lista (por ejemplo, puede hacer solo un pase secuencial sobre la lista para hacer todas las inserciones que necesita ) Esto hace que sus casos de uso sean bastante limitados en su número, pero sin embargo son los que ocurren con mucha frecuencia. Y el rendimiento de LinkedList en ellos es la razón por la que se guardará (y se mantendrá en el futuro) en todas las colecciones de contenedores de todos los idiomas, no solo de Java.

PD. Todo lo anterior, por supuesto, se aplica a todas las demás operaciones, como get (), remove (), etc. Es decir, el acceso cuidadosamente diseñado a través del iterador hará que todas ellas sean O (1) con una constante real muy pequeña. Lo mismo, por supuesto, puede decirse para todas las otras Listas, es decir, el acceso al iterador las acelerará a todas (aunque sea levemente). Pero no insert () de ArrayList y remove () - todavía van a ser O (n) ... Y no insertar TreeList () y eliminar () - la sobrecarga de equilibrio de árbol no es algo que puedas evitar ... Y TreeList probablemente tenga más memoria por encima ... Ya entendiste mi idea. Para resumir todo, LinkedList es para pequeñas operaciones de escaneo de hi-perf sobre listas. Si ese es el caso de uso que necesitas o no, solo tú lo sabes.

PSS. Dicho eso, por lo tanto, también me quedo

tentados a concluir que han amortizado o ignorado los dolores de crecimiento de ArrayList, y no han tomado en consideración los tiempos de inserción y remoción de un artículo en una LinkedList que ya ha sido localizado.