Le moyen le plus rapide de diviser une chaîne délimitée en Java

Je construis un comparateur qui offre une capacité de tri multi-colonnes sur une chaîne délimitée. J'utilise actuellement la méthode de fractionnement de la classe String comme mon choix préféré pour diviser la chaîne brute en jetons.

Est-ce le moyen le plus performant de convertir la chaîne brute en un tableau de chaînes? Je vais trier des millions de lignes, donc je pense que l'approche est importante.

Il semble fonctionner correctement et est très facile, mais vous ne savez pas s'il existe un moyen plus rapide en java.

Voici comment fonctionne le tri dans mon comparateur:

public int compare(String a, String b) {

    String[] aValues = a.split(_delimiter, _columnComparators.length);
    String[] bValues = b.split(_delimiter, _columnComparators.length);
    int result = 0;

    for( int index : _sortColumnIndices ) {
        result = _columnComparators[index].compare(aValues[index], bValues[index]);
        if(result != 0){
            break;
        }
    }
    return result;
}

Après avoir comparé les différentes approches, croyez-le ou non, la méthode de fractionnement a été la plus rapide en utilisant la dernière version de java. Vous pouvez télécharger mon comparateur complet ici: https://sourceforge.net/projects/multicolumnrowcomparator/

J'ai écrit un test de référence rapide et sale pour cela. Il compare 7 méthodes différentes, dont certaines nécessitent une connaissance spécifique des données divisées.

Pour le fractionnement général de base, Guava Splitter est 3,5 fois plus rapide que String # split () et je recommanderais de l'utiliser. Stringtokenizer est légèrement plus rapide que cela et vous séparer avec indexOf est deux fois plus rapide que de nouveau.

Pour le code et plus d'informations, voir http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/

Comme l'écrit @Tom, une approche de type indexOf est plus rapide que String.split(), car cette dernière traite des expressions régulières et a beaucoup de surcharge supplémentaire pour elles.

Cependant, un changement d'algorithme qui pourrait vous donner une super accélération. En supposant que ce comparateur sera utilisé pour trier vos ~ 100 000 chaînes, n'écrivez pas le Comparator<String>. Parce que, au cours de votre tri, la même chaîne sera probablement comparée plusieurs fois, vous la diviserez donc plusieurs fois, etc.

Divisez toutes les chaînes une fois en chaînes [] et Comparator<String[]>triez la chaîne []. Ensuite, à la fin, vous pouvez les combiner tous ensemble.

Alternativement, vous pouvez également utiliser une carte pour mettre en cache la chaîne -> chaîne [] ou vice versa. Par exemple (sommaire) Notez également que vous échangez de la mémoire pour la vitesse, j'espère que vous avez beaucoup de RAM

HashMap<String, String[]> cache = new HashMap();

int compare(String s1, String s2) {
   String[] cached1 = cache.get(s1);
   if (cached1  == null) {
      cached1 = mySuperSplitter(s1):
      cache.put(s1, cached1);
   }
   String[] cached2 = cache.get(s2);
   if (cached2  == null) {
      cached2 = mySuperSplitter(s2):
      cache.put(s2, cached2);
   }

   return compareAsArrays(cached1, cached2);  // real comparison done here
}

Selon ces benchmarks , StringTokenizer est plus rapide pour le fractionnement de chaînes, mais il ne renvoie pas de tableau, ce qui le rend moins pratique.

Si vous avez besoin de trier des millions de lignes, je vous recommande d'utiliser un SGBDR.

C'est la méthode que j'utilise pour analyser de gros fichiers (1 Go +) délimités par des tabulations. Il a beaucoup moins de frais généraux que String.split(), mais est limité à charun délimiteur. Si quelqu'un a une méthode plus rapide, j'aimerais la voir. Cela peut également être fait sur CharSequenceet CharSequence.subSequence, mais cela nécessite une implémentation CharSequence.indexOf(char)(reportez-vous à la méthode du package String.indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex)si vous êtes intéressé).

public static String[] split(final String line, final char delimiter)
{
    CharSequence[] temp = new CharSequence[(line.length() / 2) + 1];
    int wordCount = 0;
    int i = 0;
    int j = line.indexOf(delimiter, 0); // first substring

    while (j >= 0)
    {
        temp[wordCount++] = line.substring(i, j);
        i = j + 1;
        j = line.indexOf(delimiter, i); // rest of substrings
    }

    temp[wordCount++] = line.substring(i); // last substring

    String[] result = new String[wordCount];
    System.arraycopy(temp, 0, result, 0, wordCount);

    return result;
}