Come indicato in precedenza, qual è il tempo di esecuzione di equals() in java.util.Arrays?Qual è il runtime di equals() in java.util.Arrays?
Ad esempio se si confrontano due int[], esegue il ciclo di ogni elemento dell'array, quindi O (n)? E per tutto il equals() in singole classi 'equals() in java, possiamo supporre che il runtime sia sempre O (n)?
Grazie.
Come titolo dichiarato, qual è il tempo di esecuzione pari di default() in java.util.Arrays?
Il valore di default equivale a Object.equals. Arrays.equals() è in genere ciò che desideri veramente.
Ad esempio se si confrontano due int [], scorre in ciclo ogni elemento dell'array, quindi O (n)?
sì, questo è quello che suggerisce la fonte.
E per tutti i valori di default equals() in java, possiamo assumere che il runtime sia sempre O (n)?
Per alcune collezioni questo è vero, ma per le collezioni d'albero può essere O (n log n). Il caso peggiore per HashMap è O (N^2) Per le non raccolte n non ha significato.
È definito nelle specifiche JVM, come come implementare Array.equals(), oppure l'implementazione è lasciata ai particolari scrittori JVM . vale anche per IBM JVM e la Dalvik VM o potrebbe cambiare in una futura JVM Oracle? –
@ SamuelWalker Mentre dubito che faccia parte delle specifiche, il comportamento dei metodi di lunga data non cambia molto in base al fatto che non si sa mai cosa potrebbe rompere se lo facesse. In questo caso, è difficile immaginare perché lo implementerai in un altro modo esp. dato che hai un'implementazione di riferimento. –
Come può essere O (n log n) per un albero? Non è O (n * n log n)? – soandos
afferrato dal codice sorgente (codice sorgente vale 100 parole: P):
/**
* Returns <tt>true</tt> if the two specified arrays of ints are
* <i>equal</i> to one another. Two arrays are considered equal if both
* arrays contain the same number of elements, and all corresponding pairs
* of elements in the two arrays are equal. In other words, two arrays
* are equal if they contain the same elements in the same order. Also,
* two array references are considered equal if both are <tt>null</tt>.<p>
*
* @param a one array to be tested for equality
* @param a2 the other array to be tested for equality
* @return <tt>true</tt> if the two arrays are equal
*/
public static boolean equals(int[] a, int[] 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;
}
Questo non è il valore predefinito equals. – Henry
Mi spiace intendevo gli uguali in java.util.Array, non il default equivale nell'oggetto –
Prima controlla la lunghezza, e se uguale, passanti su tutti gli elementi e le chiamate uguale su di essi.
Quindi, se si desidera ignorare il costo dei singoli uguali, sì, sarebbe O (n). Ma se le voci sono stringhe, ad esempio, si allungherà anche quando le stringhe si allungheranno, non solo man mano che aumentano (perché anche i confronti sono O (m)).
Il javadoc states: due array sono uguali se contengono gli stessi elementi nello stesso ordine. Quindi è chiaro che questa operazione sarà di tipo O (n) in quanto dovrà scorrere su tutti gli elementi (almeno se sono tutti uguali).
Il default equals (cioè Object # uguale) è un O (1) il funzionamento, è un semplice confronto riferimento:
per eventuali non nulli valori di riferimento x ed y, questo metodo restituisce vero se e solo se x ed y si riferiscono allo stesso oggetto (x == y ha il valore vero)
perché non controllate la fonte ?? – PermGenError
Nel caso generale, non è specificato (perché una classe potrebbe avere il proprio 'equals'). Tuttavia, è un confronto profondo, quindi probabilmente è O (n) per confrontare due 'int []' –
cosa intendi per default è uguale? –