Pourquoi est-Chaîne.equalsIgnoreCase est si lent

J'ai rencontré une question en entrevue pour écrire une méthode pour vérifier les mots similaires indépendamment des cas de caractères.

J'y ai répondu en utilisant la différence de valeur ASCII pour chaque paire de caractères. Mais à la maison, quand je suis passé par la mise en œuvre réelle de celui-ci dans la chaîne.classe, je suis dérangé-Pourquoi est-il mis en œuvre de cette façon!

J'ai essayé de faire une comparaison entre intégré et ma méthode personnalisée, de cette façon-

public class EqualsIgnoreCase {

    public static void main(String[] args) {
        String str1 = "Srimant @$ Sahu 959s";
        String str2 = "sriMaNt @$ sAhu 959s";

        System.out.println("Avg millisecs with inbuilt () - " + averageOfTenForInbuilt(str1, str2));
        System.out.println("nAvg millisecs with custom () - " + averageOfTenForCustom(str1, str2));
    }

    public static int averageOfTenForInbuilt(String str1, String str2) {
        int avg = 0;
        for (int itr = 0; itr < 10; itr++) {
            long start1 = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                str1.equalsIgnoreCase(str2);
            }
            avg += System.currentTimeMillis() - start1;
        }
        return avg / 10;
    }

    public static int averageOfTenForCustom(String str1, String str2) {
        int avg = 0;
        for (int itr = 0; itr < 10; itr++) {
            long start2 = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                isEqualsIgnoreCase(str1, str2);
            }
            avg += System.currentTimeMillis() - start2;
        }
        return avg / 10;
    }

    public static boolean isEqualsIgnoreCase(String str1, String str2) {
        int length = str1.length();
        if (str2.length() != length) {
            return false;
        }

        for (int i = 0; i < length; i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str2.charAt(i);

            int val = Math.abs(ch1 - ch2);
            if (val != 0) {
                if (isInAlphabetsRange(ch1, ch2)) {
                    if (val != 32) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean isInAlphabetsRange(char ch1, char ch2) {
        return (((ch1 <= 122 && ch1 >= 97) || (ch1 <= 90 && ch1 >= 65)) && ((ch2 <= 122 && ch2 >= 97) || (ch2 <= 90 && ch2 >= 65)));
    }

}

Sortie-

Millisecs Avg avec intégré () - 14

Millisecs Avg avec custom () - 5

J'ai trouvé que la méthode intégrée frappait l'efficacité, comme à cause de beaucoup de vérifications et d'appels de méthode. Y a-t-il des raisons spécifiques derrière une telle mise en œuvre? Ou est-ce que je manque quelque chose dans ma logique?

Toutes les suggestions, sera chaleureusement apprécié!

22
demandé sur Raedwald 2014-05-27 12:49:26

5 réponses

Votre routine ne gère que les caractères ASCII. Le système gère tous les caractères unicode.

Considérons l'exemple suivant:

public class Test {

    public static void main(String[] args) {
        System.out.println((int) 'ě'); // => 283
        System.out.println((int) 'Ě'); // => 282 
    }

}
64
répondu Paul LeBeau 2014-05-27 09:08:07

Votre méthode est incorrecte à bien des égards. Par exemple, il considère "!"égal à "B", "B" est égale à "1", mais "!"pas égal à" 1 " (donc ce n'est pas transitif comme on s'attendrait à ce qu'une méthode égale soit).

Oui, il est assez facile d'écrire une implémentation incorrecte pour cette méthode qui est à la fois plus rapide et plus simple. Un défi équitable serait d'en écrire un correct, c'est-à-dire qui gère correctement tous les arguments de L'implémentation JDK.

Vous pouvez également regarder Comment puis-je Ecrire un micro-benchmark correct en Java? pour obtenir des mesures de performance plus fiables.

58
répondu meriton 2017-05-23 10:29:18

Ce n'est peut-être pas la raison seulement, mais le fait que votre solution ne fonctionne pas réellement pour toutes les chaînes possibles est certainement un facteur.

Il existe des paramètres régionaux (ennuyeux) pour lesquels deux caractères peuvent avoir les mêmes majuscules mais pas les mêmes minuscules. Pour cette raison, pour fonctionner (la plupart du temps, voir Turc), l'implémentation canonique doit comparer les chaînes char-for-char dans leurs cas inférieurs et supérieurs.

Votre implémentation est probablement parfait 99% du temps, surtout si vous avez seulement à traiter avec les paramètres régionaux anglais, mais l'implémentation de la bibliothèque de base ne peut malheureusement pas faire de telles hypothèses.

11
répondu Nicolas Rinaudo 2014-05-27 09:14:27

Je pense que la vérification de

String1.equalsIgnoreCase(String2)

Celui qui est fourni a une bien meilleure acceptation des caractères et il accepte toutes sortes de valeurs de caractères inclus dans le Unicode ; mais; ce que vous avez essayé de comprendre à travers votre code personnalisé est que vous ne comparez que les caractères alphabétiques anglais.

Donc, je pense,sur les lignes dePavel Horel , le commentateur de votre post, qu'en raison de la sophistication qu'il fournit pour la comparaison entre toutes sortes de caractères Unicode, cela pourrait prendre plus de temps.

4
répondu Am_I_Helpful 2014-05-27 09:02:57

Je pense que cet extrait de String.java est pertinent:

if (ignoreCase) {
    // If characters don't match but case may be ignored,
    // try converting both characters to uppercase.
    // If the results match, then the comparison scan should
    // continue.
    char u1 = Character.toUpperCase(c1);
    char u2 = Character.toUpperCase(c2);
    if (u1 == u2) {
        continue;
    }
    // Unfortunately, conversion to uppercase does not work properly
    // for the Georgian alphabet, which has strange rules about case
    // conversion.  So we need to make one last check before
    // exiting.
    if (Character.toLowerCase(u1) == Character.toLowerCase(u2)) {
        continue;
    }
}
2
répondu Zotov 2014-06-22 19:43:39