Quale parte di codice è più efficiente rispetto ai costi di Tempo e Memoria? [chiuso]

Question

Quale parte di codice è più efficiente rispetto ai costi di Tempo e Memoria? [chiuso]

#1 da (3 voti)
#2 da (1 voti)

-5

Codice 1:

private static int myCompare(String a, String b) {

    /* my version of the compareTo method from the String Java class */

    int len1 = a.length();
    int len2 = b.length();

    if (len1 == len2) { 

        for (int i = 0; i < a.length(); i++) { 

            int intValueOfStringA = (int) a.charAt(i); 
            int intValueOfStringB = (int) b.charAt(i); 

            if (intValueOfStringA != intValueOfStringB) {

                return intValueOfStringA - intValueOfStringB;
            }
        }
    }
    return len1 - len2;
}

Codice 2:

private static int stringCompare(String a, String b) {

    /* Direct implementation of the compareTo from the String Java class */


    int len1 = a.length(); 
    int len2 = b.length();
    int lim = Math.min(len1, len2); 

    char[] v1 = a.toCharArray(); 
    char[] v2 = b.toCharArray(); 

    int k = 0;
    while (k < lim) { 
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) { 
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

Si prega di ignorare i commenti sul tipo di modificatore di accesso utilizzato o sugli argomenti resi disponibili per il metodo. In realtà mi sono inventato il Codice 1 prima di essere consigliato dal mio amico di usare il metodo "compareTo" della String Class, che è riprodotto qui sotto il Codice 2. Mi chiedo quale pezzo di codice sia più efficace (w.r.t tempo e memoria). Si prega di avvisare.

Sto cercando di capire il Big O sia per i blocchi di codice che per migliorare elegantemente l'efficienza. Il codice IMO 2 è relativamente costoso con l'utilizzo della memoria. Voglio confermarlo Mi scuso se la mia domanda potrebbe alludere alla classica micro-ottimizzazione Vs. dibattito sul codice leggibile.

java strings string-matching

posta Avid Programmer 05.02.2017 - 08:58

fonte

2 risposte

Leggi altre domande sui tag java strings string-matching

In quali modi pratici è bene ricordare il modello di memoria / puntatori? [chiuso] Qual è l'algoritmo migliore per assegnare ID / numeri seriali univoci a un gruppo di oggetti identici?

score 3 · Answer 1

Primo: i due metodi fanno due cose diverse. stringCompare restituisce l'ordinamento alfabetico di due stringhe, il che significa che può essere utilizzato per ordinare un insieme di stringhe in ordine alfabetico.

myCompare restituisce -1 se le punture hanno lunghezze diverse, il che significa che non può essere utilizzato per l'ordinamento. Quindi confrontare le prestazioni dei metodi non ha molto senso dal momento che non fanno la stessa cosa.

Per myCompare il comportamento è così sorprendentemente diverso tra stringhe della stessa lunghezza e stringhe di lunghezza diversa che considererei un cattivo design indipendentemente dalle prestazioni.

Se vuoi solo confrontare le stringhe per l'uguaglianza e non preoccuparti dell'ordinamento, non dovresti confrontare il codice con String.stringCompare() ma con String.equals() che hanno la stessa ottimizzazione per stringhe di lunghezze diverse.

Ad ogni modo, considerando stringhe della stessa lunghezza, entrambi i campioni usano lo stesso algoritmo di base per il confronto, ma il secondo campione copia gli array di caratteri, che richiedono più memoria. Tuttavia entrambi gli algoritmi sono operazioni O (n), quindi la differenza sarà in fattori costanti come il possibile overhead di chiamare length() più volte e utilizzando charAt() piuttosto che usare l'indicizzazione di array. Tali differenze dipenderanno dal compilatore e dall'ambiente, quindi l'unico modo per scoprirlo è il benchmarking.

score 1 · Answer 2

Il metodo 1 è abbastanza efficiente per quanto riguarda il tempo di esecuzione e l'utilizzo della memoria. Sfortunatamente, è completamente inutile, quindi l'efficienza non aiuta.

Il metodo 2 non è necessario inefficiente per la maggior parte delle coppie di stringhe, dove probabilmente il primo o il secondo carattere sono già diversi, ma si convertono le stringhe complete in matrici di caratteri.