2016-03-14 4 views
22

Stavo guardando attraverso l'implementazione della classe di Java String e il successivo mi ha colpito come strano:Perché il metodo String.equals() di Java utilizza due variabili di conteggio?

public boolean equals(Object anObject) { 
    if (this == anObject) { 
     return true; 
    } 
    if (anObject instanceof String) { 
     String anotherString = (String)anObject; 
     int n = value.length; 
     if (n == anotherString.value.length) { 
      char v1[] = value; 
      char v2[] = anotherString.value; 
      int i = 0; 
      while (n-- != 0) {    // Here n is being decremented... 
       if (v1[i] != v2[i]) 
        return false; 
       i++;       // while i is being incremented 
      } 
      return true; 
     } 
    } 
    return false; 
} 

Questo potrebbe essere facilmente implementato con la variabile solo uno il conteggio mentre n sarebbe efficace finale, in questo modo:

while (i != n) { 
    if (v1[i] != v2[i]) 
     return false; 
    i++; 
} 

C'è anche questo, che si sbarazza del i tutto:

while (n-- != 0) { 
    if (v1[n] != v2[n]) 
     return false; 
} 

Ha a che fare con il confronto con 0 essendo (un minuscolo bit) più economico rispetto ad un'altra variabile o c'è qualche altra ragione particolare del perché è implementato in quel modo?

+10

* l'attraversamento di array inverso è (in confronto) molto più lento di attraversamento in avanti: * Dove l'hai sentito? – Tunaki

+4

Si intende proestamente che la List Iteration è più lenta. Questo è un array e l'iterazione e non dovrebbe essere più lento. – AlexWien

+0

Huh, mi sembra di averlo sentito da qualche parte. Forse l'ho confuso con l'attraversamento di un array 2D, dove il tuo ciclo interno scorre attraverso l'array esterno. Il mio male, lo modificherò. – Marv

risposta

10

Credo che abbia ad a con la substring attuazione prima JDK 7.

Al momento, la dimensione della matrice di caratteri sottostante non è necessariamente la dimensione della stringa. C'erano due campi, offset & count (i un j rispettivamente) che mostravano dove è this stringa nella matrice sottostante, in modo che il metodo era:

public boolean equals(Object anObject) { 
    if (this == anObject) { 
     return true; 
    } 
    if (anObject instanceof String) { 
     String anotherString = (String)anObject; 
     int n = count; 
     if (n == anotherString.count) { 
      char v1[] = value; 
      char v2[] = anotherString.value; 
      int i = offset; 
      int j = anotherString.offset; 
      while (n-- != 0) { 
       if (v1[i++] != v2[j++]) 
        return false; 
      } 
      return true; 
     } 
    } 
    return false; 
} 

Dopo il cambio di cui sopra, questo metodo doveva essere anche cambiati, in modo che solo fissati n per essere ora la lunghezza della matrice:

int n = value.length; 

e si sono sbarazzati di j (perché non c'è più di offset):

int i = 0; 

Ora perché i deve essere incrementato dopo 2 usi, si è incrementato in una dichiarazione separata:

if (v1[i] != v2[i]) 
    return false; 
i++; 

penso che è tutto, c'è un'implementazione più concisa che è evidente se si tratta di scriverlo da zero, ma dato che si trattava di un cambiamento spinto da un altro cambiamento ... Oracle persone sono persone normali come noi :)

Benchmarking

per quanto riguarda l'analisi comparativa String#equals vs 012.) Penso che dobbiamo confrontare le mele con le mele, così ho messo i due approcci per il confronto di 2 array di caratteri insieme:

public static void main(String[] args) { 
    final Random random = new Random(); 
    final int arrays = 10000; 
    final int chars = 1000; 
    // generate the arrays 
    char[][] array = new char[arrays][chars]; 
    for (int i = 0; i < arrays; i++) { 
     for (int j = 0; j < chars; j++) { 
      array[i][j] = (char)(random.nextInt(94) + 33); 
     } 
    } 
    // compare using Arrays equals 
    long before = System.nanoTime(); 
    for (int i = 0; i < arrays; i++) { 
     for (int j = 0; j < chars; j++) { 
      equals_Arrays(array[i], array[j]); 
     } 
    } 
    System.out.println(System.nanoTime() - before); 
    // compare using String equals 
    before = System.nanoTime(); 
    for (int i = 0; i < arrays; i++) { 
     for (int j = 0; j < chars; j++) { 
      equals_String(array[i], array[j]); 
     } 
    } 
    System.out.println(System.nanoTime() - before); 
} 

private static boolean equals_Arrays(char[] a, char[] a2) { 
    if (a == a2) 
     return true; 
    if (a == null || a2 == null) 
     return false; 

    int length = a.length; 
    if (a2.length != length) 
     return false; 

    for (int i = 0; i < length; i++) 
     if (a[i] != a2[i]) 
      return false; 

    return true; 
} 

private static boolean equals_String(char[] v1, char[] v2) { 
    if (v1 == v2) 
     return true; 
    if (v1 == null || v2 == null) 
     return false; 

    int length = v1.length; 
    if (length == v2.length) { 
     int i = 0; 
     while (length-- != 0) { 
      if (v1[i] != v2[i]) 
       return false; 
      i++; 
     } 
     return true; 
    } 
    return false; 
} 

Sulla mia casella non vedo differenza notevole.

+0

Sembra ragionevole :) – Antoniossss

+0

Curioso, ma sicuramente ha più senso ora che posso vedere l'implementazione precedente! – Marv

2

questo non è una risposta, justa pseudo banchmark:

public class CompString { 

    public static void main(String[] args) { 

     DecimalFormat df = new DecimalFormat("0.#################"); 
     int count = 1000000; 
     int length = 20; 
     int runs = 10; 

     String[] strings = new String[count]; 
     String[] copiedStrings = new String[count]; 
     char[][] chars = new char[count][]; 
     char[][] copiedChars = new char[count][]; 

     for (int i = 0; i < count; i++) { 
      String str = RandomStringUtils.random(length); 

      strings[i] = new String(str); 
      copiedStrings[i] = new String(str); 

      chars[i] = Arrays.copyOf(str.toCharArray(), str.length()); 
      copiedChars[i] = Arrays.copyOf(chars[i], chars[i].length); 
     } 

     System.out.println("Lets banchmark that !!"); 
     int loop = 0; 
     while (loop++ < runs) { 
      System.out.println("Run #" + loop); 
      long t = 0; 
      long t0 = System.currentTimeMillis(); 
      for (int i = 0; i < count; i++) { 
       strings[i].equals(copiedStrings[i]); 
      } 
      long t1 = System.currentTimeMillis(); 
      t = t1 - t0; 

      System.out.println("Avg String.equals() duration: " + df.format(t/(double) count)); 

      t0 = System.currentTimeMillis(); 
      for (int i = 0; i < count; i++) { 
       Arrays.equals(chars[i], copiedChars[i]); 
      } 
      t1 = System.currentTimeMillis(); 
      t = t1 - t0; 

      System.out.println("Avg Arrays.equals(char[] char[]) duration: " + df.format(t/(double) count)); 
      System.out.println(); 
     } 
    } 
} 

Ed ecco i risultati:

Run #1 
Avg String.equals() duration: 0,000017 
Avg Arrays.equals(char[] char[]) duration: 0,000013 

Run #2 
Avg String.equals() duration: 0,000037 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #3 
Avg String.equals() duration: 0,000002 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #4 
Avg String.equals() duration: 0,000003 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #5 
Avg String.equals() duration: 0,000002 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #6 
Avg String.equals() duration: 0,000003 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #7 
Avg String.equals() duration: 0,000003 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #8 
Avg String.equals() duration: 0,000003 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #9 
Avg String.equals() duration: 0,000002 
Avg Arrays.equals(char[] char[]) duration: 0 

Run #10 
Avg String.equals() duration: 0,000002 
Avg Arrays.equals(char[] char[]) duration: 0 

Quindi, a causa String.equals richiede più tempo quindi confrontando le matrici alla base (con la variabile singolo iteratore) possiamo escludere alcuni magici problemi di ottimizzazione JVM qui (ma potrebbe essere in passato?).

+0

Penso che per un confronto reale tra i 2 approcci devi scrivere 2 metodi con la stessa firma: 'booleano equals2 (char [] v1, char [] v2)', copia uno da Arrays e deduci il secondo da String equals. L'ho fatto sul mio locale e i risultati sono ~ uguali. – Bax

+1

E usa System.nanoTime() – AlexWien

4

Non è un codice reale per la maggior parte delle VM Java reali con HotSpot. String.equals è un metodo molto importante e viene implementato tramite intrinseco. Ha un'implementazione nativa specifica per piattaforma. Puoi trovare l'elenco completo qui src/share/vm/classfile/vmSymbols.hpp (vedi do_intrinsic)

+1

Bella cattura, ma perché è ancora più lento rispetto al confronto di 2 array di caratteri? (vedi codice sotto) Devo ammettere che la comparazione delle stringhe è piuttosto comune nella programmazione, quindi l'approccio nativo sembra ragionevole (prestazioni migliori) ma nel mondo reale sembra che non sia così veloce (come potrebbe essere) – Antoniossss

+1

Prima di tutto Anche Arrays.equals è intrinseco. Suppongo che possiamo vedere la differenza di tempo tra di loro perché Arrays.equals è un metodo statico e String.equals è un metodo oggetto. – sibnick

Problemi correlati