Pourquoi la plupart des manipulations de chaînes en Java sont-elles basées sur des regexp ?

Question

En Java, il existe un grand nombre de méthodes qui ont toutes pour but de manipuler des chaînes de caractères. L'exemple le plus simple est la méthode String.split("quelque chose").

La définition réelle d'un grand nombre de ces méthodes est qu'elles prennent toutes une expression régulière comme paramètre(s) d'entrée. Ce qui en fait des blocs de construction très puissants.

Maintenant, il y a deux effets que vous verrez dans beaucoup de ces méthodes :

1. Ils recompilent l'expression chaque fois que la méthode est invoquée. Elles ont donc un impact sur les performances.
2. J'ai constaté que dans la plupart des situations "réelles", ces méthodes sont appelées avec des textes "fixes". L'utilisation la plus courante de la méthode split est encore pire : elle est généralement appelée avec un seul caractère (généralement un ' ', un ';' ou un '&') à séparer.

Ainsi, les méthodes par défaut ne sont pas seulement puissantes, elles semblent également surpuissantes pour ce à quoi elles sont réellement utilisées. En interne, nous avons développé une méthode "fastSplit" qui sépare les chaînes de caractères fixes. J'ai écrit un test à la maison pour voir combien plus vite je pourrais le faire si l'on savait qu'il s'agissait d'un seul caractère. Les deux méthodes sont nettement plus rapides que la méthode de fractionnement "standard".

Je me demandais donc : pourquoi l'API Java a été choisie telle qu'elle est maintenant ? Quelle était la bonne raison d'opter pour cela au lieu d'avoir quelque chose comme split(char), split(String) et splitRegex(String) ?

---

Mise à jour : J'ai fait quelques appels pour voir combien de temps prennent les différentes façons de diviser une chaîne.

Bref résumé : il fait un grand différence !

J'ai fait 10000000 itérations pour chaque cas de test, en utilisant toujours l'entrée

"aap,noot,mies,wim,zus,jet,teun" 

et en utilisant toujours ',' ou "," comme argument de division.

Voici ce que j'ai obtenu sur mon système Linux (c'est une boîte Atom D510, donc un peu lente) :

fastSplit STRING
Test  1 : 11405 milliseconds: Split in several pieces
Test  2 :  3018 milliseconds: Split in 2 pieces
Test  3 :  4396 milliseconds: Split in 3 pieces

homegrown fast splitter based on char
Test  4 :  9076 milliseconds: Split in several pieces
Test  5 :  2024 milliseconds: Split in 2 pieces
Test  6 :  2924 milliseconds: Split in 3 pieces

homegrown splitter based on char that always splits in 2 pieces
Test  7 :  1230 milliseconds: Split in 2 pieces

String.split(regex)
Test  8 : 32913 milliseconds: Split in several pieces
Test  9 : 30072 milliseconds: Split in 2 pieces
Test 10 : 31278 milliseconds: Split in 3 pieces

String.split(regex) using precompiled Pattern
Test 11 : 26138 milliseconds: Split in several pieces 
Test 12 : 23612 milliseconds: Split in 2 pieces
Test 13 : 24654 milliseconds: Split in 3 pieces

StringTokenizer
Test 14 : 27616 milliseconds: Split in several pieces
Test 15 : 28121 milliseconds: Split in 2 pieces
Test 16 : 27739 milliseconds: Split in 3 pieces

Comme vous pouvez le constater, cela fait une grande différence si vous avez beaucoup de fractionnements à faire.

Pour vous donner un aperçu, je suis actuellement dans l'arène des fichiers journaux Apache et d'Hadoop avec les données d'un projet de recherche sur la santé. grand site web. Donc, pour moi, ce genre de choses compte vraiment :)

Un élément que je n'ai pas pris en compte ici est le ramasseur de déchets. D'après ce que je sais, la compilation d'une expression régulière dans un Pattern/Matcher/... allouera beaucoup d'objets, qui devront être collectés à un moment donné. Donc peut-être qu'à long terme, les différences entre ces versions sont encore plus grandes .... ou plus petites.

Mes conclusions jusqu'à présent :

• Ne l'optimisez que si vous avez BEAUCOUP de chaînes à diviser.
• Si vous utilisez les méthodes regex, précompilez toujours si vous utilisez plusieurs fois le même motif.
• Oubliez le StringTokenizer (obsolète)
• Si vous voulez diviser un seul caractère, utilisez une méthode personnalisée, surtout si vous avez besoin de le diviser en un nombre spécifique de morceaux (comme ... 2).

P.S. Je vous donne toutes mes méthodes de division par char pour jouer avec (sous la licence que tout sur ce site tombe sous :) ). Je ne les ai jamais testées complètement pour le moment. Amusez-vous bien.

private static String[]
        stringSplitChar(final String input,
                        final char separator) {
    int pieces = 0;

    // First we count how many pieces we will need to store ( = separators + 1 )
    int position = 0;
    do {
        pieces++;
        position = input.indexOf(separator, position + 1);
    } while (position != -1);

    // Then we allocate memory
    final String[] result = new String[pieces];

    // And start cutting and copying the pieces.
    int previousposition = 0;
    int currentposition = input.indexOf(separator);
    int piece = 0;
    final int lastpiece = pieces - 1;
    while (piece < lastpiece) {
        result[piece++] = input.substring(previousposition, currentposition);
        previousposition = currentposition + 1;
        currentposition = input.indexOf(separator, previousposition);
    }
    result[piece] = input.substring(previousposition);

    return result;
}

private static String[]
        stringSplitChar(final String input,
                        final char separator,
                        final int maxpieces) {
    if (maxpieces <= 0) {
        return stringSplitChar(input, separator);
    }
    int pieces = maxpieces;

    // Then we allocate memory
    final String[] result = new String[pieces];

    // And start cutting and copying the pieces.
    int previousposition = 0;
    int currentposition = input.indexOf(separator);
    int piece = 0;
    final int lastpiece = pieces - 1;
    while (currentposition != -1 && piece < lastpiece) {
        result[piece++] = input.substring(previousposition, currentposition);
        previousposition = currentposition + 1;
        currentposition = input.indexOf(separator, previousposition);
    }
    result[piece] = input.substring(previousposition);

    // All remaining array elements are uninitialized and assumed to be null
    return result;
}

private static String[]
        stringChop(final String input,
                   final char separator) {
    String[] result;
    // Find the separator.
    final int separatorIndex = input.indexOf(separator);
    if (separatorIndex == -1) {
        result = new String[1];
        result[0] = input;
    }
    else {
        result = new String[2];
        result[0] = input.substring(0, separatorIndex);
        result[1] = input.substring(separatorIndex + 1);
    }
    return result;
}

Answer 1

Notez que la regex ne doit pas être recompilée à chaque fois. De la Javadoc :

Une invocation de cette méthode de la forme str.split(regex, n) donne le même résultat que l'expression

Pattern.compile(regex).split(str, n) 

En d'autres termes, si vous vous préoccupez des performances, vous pouvez précompiler le motif et le réutiliser ensuite :

Pattern p = Pattern.compile(regex);
...
String[] tokens1 = p.split(str1); 
String[] tokens2 = p.split(str2); 
...

au lieu de

String[] tokens1 = str1.split(regex);
String[] tokens2 = str2.split(regex);
...

Je pense que la principale raison de cette conception de l'API est la commodité. Étant donné que les expressions régulières incluent également toutes les chaînes/chaînes "fixes", le fait d'avoir une seule méthode au lieu de plusieurs simplifie l'API. Et si quelqu'un s'inquiète des performances, l'expression régulière peut toujours être précompilée comme indiqué ci-dessus.

Mon sentiment (que je ne peux étayer par aucune preuve statistique) est que la plupart des cas String.split() est utilisé dans un contexte où la performance n'est pas un problème. Par exemple, il s'agit d'une action unique, ou la différence de performance est négligeable par rapport à d'autres facteurs. Les cas où vous divisez des chaînes de caractères en utilisant la même regex des milliers de fois dans une boucle serrée sont rares, et l'optimisation des performances a alors tout son sens.

Il serait intéressant de voir une comparaison des performances d'une implémentation d'un matcheur regex avec des chaînes/chars fixes par rapport à celle d'un matcheur spécialisé dans ces derniers. La différence pourrait ne pas être assez importante pour justifier une implémentation séparée.

Answer 2

Je ne dirais pas que la plupart des manipulations de chaînes sont basées sur les regex en Java. En réalité, nous ne parlons que de split y replaceAll / replaceFirst . Mais je suis d'accord, c'est une grosse erreur.

Outre la laideur d'avoir une caractéristique de bas niveau du langage (chaînes de caractères) qui devient dépendante d'une caractéristique de plus haut niveau (regex), c'est aussi un piège pour les nouveaux utilisateurs qui pourraient naturellement supposer qu'une méthode avec la signature String.replaceAll(String, String) serait une fonction de remplacement de chaîne de caractères. Le code écrit en partant de cette hypothèse aura l'air de fonctionner, jusqu'à ce qu'un caractère spécial de regex s'y glisse, auquel cas vous aurez des bogues déroutants, difficiles à déboguer (et peut-être même importants pour la sécurité).

Il est amusant qu'un langage qui peut être aussi pédant et strict sur le typage ait fait l'erreur de traiter une chaîne de caractères et une regex comme la même chose. Il est moins amusant de constater qu'il y a toujours pas de méthode intégrée pour remplacer ou diviser une chaîne de caractères simple. Vous devez utiliser une expression rationnelle de remplacement avec un paramètre Pattern.quote d string. Et vous n'obtenez cela qu'à partir de Java 5. C'est sans espoir.

@Tim Pietzcker :

Y a-t-il d'autres langues qui font la même chose ?

Les chaînes de caractères de JavaScript sont en partie modelées sur celles de Java et sont également désordonnées dans le cas de replace() . En passant une chaîne, vous obtenez un remplacement de chaîne simple, mais il ne remplace que la première correspondance, ce qui est rarement ce que l'on veut. Pour obtenir un "replace-all", vous devez passer une chaîne de caractères de type RegExp avec l'objet /g qui pose à nouveau des problèmes si vous voulez le créer dynamiquement à partir d'une chaîne de caractères (il n'y a pas d'indicateur intégré RegExp.quote en JS). Heureusement, split() est purement basé sur les chaînes de caractères, vous pouvez donc utiliser l'idiome :

s.split(findstr).join(replacestr)

Et bien sûr, Perl fait absolument tout avec regexen, parce que c'est pervers comme ça.

(Il s'agit d'un commentaire plus que d'une réponse, mais il est trop grand pour une réponse. Pourquoi Est-ce que Java a fait ça ? Je ne sais pas, ils ont fait beaucoup d'erreurs à leurs débuts. Certaines d'entre elles ont été corrigées depuis. Je pense que s'ils avaient pensé à mettre la fonctionnalité regex dans la case marquée Pattern Dans la version 1.0, la conception de String serait plus propre pour correspondre).

Answer 3

J'imagine qu'une bonne raison est qu'ils peuvent simplement passer la main à la méthode regex, qui fait le gros du travail pour toutes les méthodes de chaîne. Je suppose qu'ils ont pensé que s'ils avaient déjà une solution fonctionnelle, il était moins efficace, du point de vue du développement et de la maintenance, de réinventer la roue pour chaque méthode de manipulation de chaîne.

Answer 4

Discussion intéressante !

À l'origine, Java n'a pas été conçu comme un langage de programmation par lots. En tant que telle, l'API est plus adaptée à l'exécution d'un "replace", d'un "parse", etc., sauf lors de l'initialisation de l'application, lorsque l'on peut s'attendre à ce que l'application analyse un ensemble de fichiers de configuration.

L'optimisation de ces API a donc été sacrifiée sur l'autel de la simplicité. Mais la question soulève un point important. Le désir de Python de maintenir la distinction entre les regex et les non-regex dans son API provient du fait que Python peut également être utilisé comme un excellent langage de script. Sous UNIX également, les versions originales de fgrep ne supportaient pas les regex.

J'étais engagé dans un projet où nous devions faire une certaine quantité de travail ETL en Java. À l'époque, je me souviens avoir proposé le type d'optimisations auxquelles vous avez fait allusion dans votre question.

Answer 5

En regardant la classe Java String, les utilisations de la regex semblent raisonnables, et il existe des alternatives si la regex n'est pas souhaitée :

http://java.sun.com/javase/6/docs/api/java/lang/String.html

boolean matches(String regex) - Une regex semble appropriée, sinon vous pourriez simplement utiliser equals

String replaceAll/replaceFirst(String regex, String replacement) - Il existe des équivalents qui prennent CharSequence à la place, ce qui empêche les regex.

String[] split(String regex, int limit) - Une division puissante mais coûteuse, vous pouvez utiliser StringTokenizer pour diviser par des jetons.

Ce sont les seules fonctions que j'ai vues qui prennent en charge les regex.

Edit : Après avoir vu que StringTokenizer est un héritage, je m'en remettrais à la réponse de Péter Török pour précompiler la regex pour split au lieu d'utiliser le tokenizer.