Comparando dos LinkedList <String> con ListIterator versus for loop y get (int index)

Tengo dos objetos LinkedList que siempre son del mismo tamaño. Quiero compararlos para ver si son idénticos en contenido. ¿Cuáles son las implicaciones generales de rendimiento y estilo de crear un ListIterator para cada lista y usar while whileLove Next versus usar un contador (int i) e iterar de 0 a linkedlist.size() usando linkedlist.get (i) para obtener y comparar ¿Los valores? ¿Hay una mejor manera que estoy pasando por alto?Comparando dos LinkedList <String> con ListIterator versus for loop y get (int index)

Lo único que se me ocurre es que el método ListIterator puede ser mejor ya que podría cambiar más fácilmente en otra lista Comparable más adelante (no es que lo haga). No sé cómo se ven los dos bajo el capó, así que no estoy seguro de cómo los compararía en cuanto a rendimiento.

Fuente

2010-02-24 msilver

Como resulta AbstractList.equals() (que usa LinkedList) hará esto automáticamente así que use eso. El código es:

public boolean equals(Object o) { 
    if (o == this) 
    return true; 
    if (!(o instanceof List)) 
    return false; 

    ListIterator<E> e1 = listIterator(); 
    ListIterator e2 = ((List) o).listIterator(); 
    while (e1.hasNext() && e2.hasNext()) { 
    E o1 = e1.next(); 
    Object o2 = e2.next(); 
    if (!(o1 == null ? o2 == null : o1.equals(o2))) 
     return false; 
    } 
    return !(e1.hasNext() || e2.hasNext()); 
}

No reinvente la rueda.

Una última nota: no use get(index) para repetir en un LinkedList. Es O (n) acceso (O (1) para ArrayList) por lo que un cruce LinkedList utilizando get(index) será O (n).

Fuente

2010-02-24 03:34:31 cletus

Gracias. Eso es similar a lo que estoy usando. – msilver

¿No sería mejor devolver falso de inmediato, cuando las dos listas son de diferente tamaño, en lugar de su última devolución condicional? –

Sí, creo que una revisión rápida de los tamaños sería una buena idea para evitar iterar a través de listas de diferentes tamaños en primer lugar. Buena atrapada. – msilver

El acceso aleatorio a un LinkedList tiene un rendimiento horrible (debe comenzar en un extremo e invocar next o similar repetidamente), por lo que el ListIterator sería más rápido.

Fuente

2010-02-24 03:35:38

Gracias, eso tiene mucho sentido. También me di cuenta de que descuidé la posibilidad de usar list1.equals (list2), que, de acuerdo con la API, debería tener el comportamiento esperado (y supondría que lo implementaron con Iterators). – msilver

get(n) para las listas vinculadas no es una operación constante para las clases que se extienden AbstractSequentialList; es O(n). De AbstractSequentialList#get(int index):

Esta implementación primero obtiene un iterador de lista que apunta al elemento indexado (con listIterator(index)). Luego, obtiene el elemento usando ListIterator.next y lo devuelve.

Generalmente no desea hacer acceso aleatorio en colecciones que no implementan la interfaz de marcador java.util.RandomAccess.

Como regla general, una aplicación lista debe implementar esta interfaz si, para los casos típicos de la clase, este bucle:
for (int i=0, n=list.size(); i < n; i++) 
    list.get(i); 
corre más rápido que este bucle:
for (Iterator i=list.iterator(); i.hasNext();) 
    i.next(); 

A partir de Java SE 6, las clases de implementación son ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector.

Fuente

2010-02-24 04:00:16 polygenelubricants

Comparando dos LinkedList <String> con ListIterator versus for loop y get (int index)

Respuesta

Cuestiones relacionadas