¿Alguna gran diferencia entre usar contains o loop en una lista?

Question

En cuanto al rendimiento, ¿existe realmente una gran diferencia entre el uso de:

• ArrayList.contains (o) vs foreach | iterador
• LinkedList.contains (o) vs foreach | iterador

De Por supuesto, para los bucles foreach | iterator, tendré que comparar explícitamente los métodos y devolver true o false en consecuencia.

El objeto que estoy comparando es un objeto donde equals() y hashcode() se han sobrescrito correctamente.

EDITAR: No necesita saber acerca de containsValue después de todo, perdón por eso. Y sí, soy estúpido ... Me di cuenta de lo estúpida que era mi pregunta sobre containsKey vs foreach, no importaba eso, no sé lo que estaba pensando. Básicamente quiero saber sobre los anteriores (editados los otros).

Answer 1

EDITADO:

Con la nueva forma de la pregunta ya no incluyendo HashMap y TreeMap, mi respuesta es completamente diferente. Ahora digo no.

Estoy seguro de que otras personas han respondido esto, pero tanto en LinkedList como en ArrayList, contiene() simplemente llama a indexOf(), que itera sobre la colección.

Es posible que haya pequeñas diferencias de rendimiento, tanto entre LinkedList como ArrayList, y entre contains y foreach, no hay ninguna gran diferencia entre .

Answer 2

Sin evaluación comparativa, el contenido debe ser más rápido o el mismo en todos los casos.

Para 1 y 2, no necesita llamar a los métodos del iterador. Puede circular internamente. Tanto ArrayList y LinkedList implementan contiene en términos de indexOf

1. ArrayList - indexOf es un estilo de C para el bucle en la matriz de soporte.
2. LinkedList - indexOf recorre la lista vinculada en un estilo C para el bucle.

Para 3 y 4, debe distinguir entre containsKey y containsValue.

3.   HashMap, containsKey is O (1). Funciona al mezclar la clave, obtener el depósito asociado y luego recorrer la lista enlazada. containsValue es O (n) y funciona simplemente verificando cada valor en cada segmento en un bucle for anidado.

4.   TreeMap, containsKey is O (log n). Comprueba si está dentro del alcance, luego busca el árbol rojo-negro. containsValue, que es O (n), usa una caminata en orden del árbol.

Answer 3

Creo que usar contains es mejor porque generalmente la implementación de la biblioteca es más eficiente que la implementación manual de la misma. Comprueba si puedes durante la construcción del objeto o luego pasa un método de comparación que hayas escrito que cumpla con tu implementación personalizada de igual y código hash.

Gracias, Krishna

Answer 4

Atravesando el recipiente con foreach/iterador es siempre un tiempo O (n). La búsqueda ArrayList/LinkedList es O (n) también.

HashMap.containsKey() es O (1) amortized tiempo.

TreeMap.containsKey() es O (log n) time.

Tanto HashMap como TreeMap containsValue() es O (n), pero puede haber implementaciones optimizadas para containsValue() que sean tan rápidas como containsKey().

Answer 5

ArrayList.contains hace

return indexOf(o) >= 0; 

donde

public int indexOf(Object o) { 
if (o == null) { 
    for (int i = 0; i < size; i++) 
    if (elementData[i]==null) 
     return i; 
} else { 
    for (int i = 0; i < size; i++) 
    if (o.equals(elementData[i])) 
     return i; 
} 
return -1; 
} 

Es similar para LinkedList, solamente se utiliza .Next() para recorrer los elementos, por lo que no hay mucha diferencia.

public int indexOf(Object o) { 
    int index = 0; 
    if (o==null) { 
     for (Entry e = header.next; e != header; e = e.next) { 
      if (e.element==null) 
       return index; 
      index++; 
     } 
    } else { 
     for (Entry e = header.next; e != header; e = e.next) { 
      if (o.equals(e.element)) 
       return index; 
      index++; 
     } 
    } 
    return -1; 
} 

HashMap.containKey utiliza el hash de la clave a buscar todas las claves con que de hash (que es rápido) y luego usa iguales sólo en esas llaves, así que no hay una mejora; pero containsValue() pasa por los valores con a for.

TreeMap.containsKey parece hacer una búsqueda informada utilizando un comparador para encontrar la clave más rápido, por lo que es aún mejor; pero containsValue todavía parece pasar por los tres hasta que encuentra un valor.

En general, creo que deberías usar los métodos, ya que son más fáciles de escribir que hacer un bucle cada vez :).

Answer 6

Esto no tiene ningún differency ya que contiene (O) llama indexOf (o), que simplemente bucles de la siguiente manera:

for (int i = 0; i < size; i++) 
    if (o.equals(elementData[i])) 
     return i; 

(registramos en ArrayList)