Java: .contains and .equals

Question

Sto provando ad eseguire un programma, per confrontare gli elementi in due elenchi collegati tra loro. in un modo, posso farlo eseguendo due cicli for e iterando su entrambi gli elenchi confrontando ogni elemento in list1 con list2 usando .equals(). l'altro modo è, semplicemente iterando sul primo elenco e controllando se list1.contains (list1.get (i)) .. la documentazione java dice che .contains fa .equals internamente. se questo è il caso, come è che il mio tempo di esecuzione per il primo è più lungo rispetto a quest'ultimo? Ho interpretato male la documentazione? Se l'ho fatto, come avviene esattamente il confronto interno quando lo uso contiene?

  using equals: 
      for (int i = 0; i < list_one.size(); i++) { 
       for (int j = 0; j < list_one.size(); j++) { 
        if (list_one.get(i).equals(list_two.get(j))) { count++; } 

      using contains: 
      for (int i = 0; i < list_one.size(); i++) { 
       if (list_two.contains(list_one.get(i)) == true) { count++; } 

Answer 1

credo, visto get(i) che si sta utilizzando get(j) in entrambi i loop. In una lista collegata che è inefficiente. for (String s1 : list1) for (String s2 : list2) ... dovrebbe avere la stessa velocità di contains.

Ad esempio get (3) dovrebbe iniziare con il primo elemento, prendere il collegamento alle tre volte successive. Mentre il per-use usa un iteratore che punta al prossimo elemento.

Answer 2

L'implementazione di contains interrompe l'iterazione una volta che equals restituisce true, quindi non itera l'intera lista se l'elemento che si sta cercando è da qualche parte all'inizio dell'elenco. Se la tua versione non lo fa, questo spiegherebbe perché è più lento.

PS: in entrambi i casi il tempo di percorrenza sarà sempre quadratico. Esistono modi più intelligenti per risolvere questo problema che non coinvolgono l'iterazione del secondo elenco per ogni elemento del primo elenco (ad esempio, ordinando prima i due elenchi o utilizzando un set).