La façon la plus rapide de la bande de tous les caractères non-imprimables à partir d'une Chaîne de Java

Question

Quel est le moyen le plus rapide de la bande de tous les caractères non-imprimables à partir d'un String en Java?

Jusqu'à présent, j'ai essayé et mesurée sur 138 octets, 131-Chaîne de caractères:

• La chaîne de replaceAll() - méthode la plus lente
  • 517009 résultats / sec
• Précompiler un Modèle, puis utilisez la Correspondance de l' replaceAll()
  • 637836 résultats / sec
• L'utilisation de StringBuffer, obtenir codepoints l'aide d' codepointAt() un par un et de les ajouter à StringBuffer
  • 711946 résultats / sec
• L'utilisation de StringBuffer, obtenir des caractères à l'aide charAt() un par un et de les ajouter à StringBuffer
  • 1052964 résultats / sec
• Préallouer un char[] tampon, obtenir des caractères à l'aide charAt() un par un et de remplir ce tampon, puis de les convertir en chaînes de caractères
  • 2022653 résultats / sec
• Préallouer 2 char[] tampons - ancien et le nouveau, obtenir tous les caractères de Chaîne existante à la fois à l'aide de getChars(), itération sur le vieux tampon un par un et de remplir la mémoire tampon, puis la convertir en un nouveau tampon de Chaîne - ma propre version la plus rapide
  • 2502502 résultats / sec
• Même chose avec 2 tampons seule à l'aide de byte[], getBytes() et en spécifiant l'encodage "utf-8"
  • 857485 résultats / sec
• Même chose avec 2 byte[] tampons, mais en spécifiant l'encodage comme une constante, Charset.forName("utf-8")
  • 791076 résultats / sec
• Même chose avec 2 byte[] tampons, mais en spécifiant l'encodage 1 octet local d'encodage (à peine un sane chose à faire)
  • 370164 résultats / sec

Mon meilleur essai a été le suivant:

    char[] oldChars = new char[s.length()];
    s.getChars(0, s.length(), oldChars, 0);
    char[] newChars = new char[s.length()];
    int newLen = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = oldChars[j];
        if (ch >= ' ') {
            newChars[newLen] = ch;
            newLen++;
        }
    }
    s = new String(newChars, 0, newLen);

Toute réflexion sur la façon de le rendre encore plus rapide?

Les points de Bonus pour répondre à une très étrange question: pourquoi à l'aide de "utf-8" charset directement le nom d'offre de meilleures performances que l'utilisation des pré-alloués static const Charset.forName("utf-8")?

Mise à jour

• Suggestion de ratchet freak rendements impressionnants 3105590 résultats / s de performance, un +amélioration de 24%!
• Suggestion de Ed Staub rendements pourtant, une autre amélioration - 3471017 résultats / sec, un +12% sur le meilleur.

Mise à jour 2

J'ai essayé de mon mieux pour collectées toutes les solutions proposées et de son les mutations et l'a publié comme une petite analyse comparative cadre sur github. Actuellement, il arbore 17 algorithmes. L'un d'eux est "spécial" - Voo1 algorithme (fourni par l'utilisateur Voo) emploie complexes réflexion astuces afin de réaliser ainsi stellaire vitesses, mais il bousille JVM des chaînes d'état, donc c'est étalonnés séparément.

Vous êtes les bienvenus de le vérifier et de l'exécuter pour déterminer les résultats sur votre boîte. Voici un résumé des résultats que j'ai sur la mienne. C'est les specs:

• Debian sid
• Linux 2.6.39-2-amd64 (x86_64)
• Java est installé à partir d'un package sun-java6-jdk-6.24-1, JVM identifie lui-même comme
  • Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
  • Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, en mode mixte)

Différents algorithmes de montrer en fin de compte des résultats différents étant donné un ensemble différent de données d'entrée. J'ai couru un test dans 3 modes:

Même chaîne unique

Ce mode fonctionne sur une seule et même chaîne fournie par l' StringSource classe comme une constante. L'épreuve de force est:

 Ops / s │ Algorithme
──────────┼──────────────────────────────
6 535 947 │ Voo1
──────────┼──────────────────────────────
5 350 454 │ RatchetFreak2EdStaub1GreyCat1
5 249 343 │ EdStaub1
5 002 501 │ EdStaub1GreyCat1
4 859 086 │ ArrayOfCharFromStringCharAt
4 295 532 │ RatchetFreak1
4 045 307 │ ArrayOfCharFromArrayOfChar
2 790 178 │ RatchetFreak2EdStaub1GreyCat2
2 583 311 │ RatchetFreak2
1 274 859 │ StringBuilderChar
1 138 174 │ StringBuilderCodePoint
 994 727 │ ArrayOfByteUTF8String
 918 611 │ ArrayOfByteUTF8Const
 756 086 │ MatcherReplace
 598 945 │ StringReplaceAll
 460 045 │ ArrayOfByteWindows1251

Dans le tracé de la forme:

Plusieurs chaînes de caractères, 100% des chaînes contiennent des caractères de contrôle

Source de la chaîne de fournisseur de pré-généré beaucoup de chaînes aléatoires à l'aide de (0..127) jeu de caractères - ainsi, presque toutes les chaînes de caractères contenues au moins un caractère de contrôle. Les algorithmes reçu des chaînes à partir de cette pré-généré tableau en round robin.

 Ops / s │ Algorithme
──────────┼──────────────────────────────
2 123 142 │ Voo1
──────────┼──────────────────────────────
1 782 214 │ EdStaub1
1 776 199 │ EdStaub1GreyCat1
1 694 628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
 893 176 │ ArrayOfByteUTF8String
 817 127 │ ArrayOfByteUTF8Const
 778 089 │ StringBuilderChar
 734 754 │ StringBuilderCodePoint
 377 829 │ ArrayOfByteWindows1251
 224 140 │ MatcherReplace
 211 104 │ StringReplaceAll

Dans le tracé de la forme:

Plusieurs chaînes de caractères, 1% de chaînes contiennent des caractères de contrôle

Identique au précédent, mais seulement 1% des chaînes a été généré avec les caractères de contrôle - autres 99% a été généré à l'aide de [32..127] jeu de caractères, de sorte qu'ils ne pouvaient pas contenir de caractères de contrôle. Cette charge de synthèse se rapproche le plus du monde réel, l'application de cet algorithme à ma place.

 Ops / s │ Algorithme
──────────┼──────────────────────────────
3 711 952 │ Voo1
──────────┼──────────────────────────────
2 851 440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426 007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1 922 707 │ RatchetFreak2EdStaub1GreyCat1
1 857 010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
 939 055 │ StringBuilderChar
 907 194 │ ArrayOfByteUTF8Const
 841 963 │ StringBuilderCodePoint
 606 465 │ MatcherReplace
 501 555 │ StringReplaceAll
 381 185 │ ArrayOfByteWindows1251

Dans le tracé de la forme:

Il est très difficile pour moi de décider qui a fourni la meilleure réponse, mais compte tenu de l'application réelle de la meilleure solution a été donnée/inspiré par Ed Staub, je pense qu'il serait juste de marquer sa réponse. Merci pour tous ceux qui ont pris part à cette, vos commentaires ont été très utiles et précieux. Se sentir libre pour exécuter la suite de tests sur votre zone et de proposer des solutions encore meilleures (travail JNI solution, quelqu'un?).

Références

• GitHub avec une analyse comparative de suite

Answer 1

à l'aide de 1 char tableau pourrait travailler un peu mieux

int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

et j'ai évité les appels répétés à la s.length();

un autre micro-optimisation qui pourrait fonctionner est

int length = s.length();
char[] oldChars = new char[length+1];
s.getChars(0, length, oldChars, 0);
oldChars[length]='\0';//avoiding explicit bound check in while
int newLen=-1;
while(oldChars[++newLen]>=' ');//find first non-printable,
                       // if there are none it ends on the null char I appended
for (int  j = newLen; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;//the while avoids repeated overwriting here when newLen==j
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

Answer 2

S'il est raisonnable d'intégrer cette méthode dans une classe qui ne sont pas partagées entre les threads, vous pouvez réutiliser la mémoire tampon:

char [] oldChars = new char[5];

String stripControlChars(String s)
{
    final int inputLen = s.length();
    if ( oldChars.length < inputLen )
    {
        oldChars = new char[inputLen];
    }
    s.getChars(0, inputLen, oldChars, 0);

etc...

C'est une grande victoire - 20% ou alors, si je comprends bien l'actuel meilleur des cas.

Si c'est pour être utilisé sur des grandes chaînes et de la mémoire "fuite" est une préoccupation, une référence faible peut être utilisé.

Answer 3

Eh bien, je l'ai battu la meilleure méthode (freak de la solution avec le préaffectés array) d'environ 30%, selon mes mesures. Comment? En vendant mon âme.

Comme je suis sûr que tout le monde qui a suivi la discussion sait cela viole à peu près toute la programmation de base, principe, mais bon. De toute façon le suivant ne fonctionne que si la matrice de caractères de la chaîne n'est pas partagé entre les autres cordes - si ce n'est celui qui a pour déboguer ce sera tout à fait le droit de décider de vous tuer (sans les appels à la fonction substring() et l'utilisation de ce sur des chaînes de caractères littérales cela devrait fonctionner car je ne vois pas pourquoi la JVM serait stagiaire chaînes uniques de lire à partir d'une source extérieure). Mais n'oubliez pas de assurez-vous que l'indice de référence code de ne pas le faire - c'est très probable et serait d'aider à la réflexion solution évidemment.

De toute façon, ici, nous allons:

    // Has to be done only once - so cache those! Prohibitively expensive otherwise
    private Field value;
    private Field offset;
    private Field count;
    private Field hash;
    {
        try {
            value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            offset = String.class.getDeclaredField("offset");
            offset.setAccessible(true);
            count = String.class.getDeclaredField("count");
            count.setAccessible(true);
            hash = String.class.getDeclaredField("hash");
            hash.setAccessible(true);               
        }
        catch (NoSuchFieldException e) {
            throw new RuntimeException();
        }

    }

    @Override
    public String strip(final String old) {
        final int length = old.length();
        char[] chars = null;
        int off = 0;
        try {
            chars = (char[]) value.get(old);
            off = offset.getInt(old);
        }
        catch(IllegalArgumentException e) {
            throw new RuntimeException(e);
        }
        catch(IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        int newLen = off;
        for(int j = off; j < off + length; j++) {
            final char ch = chars[j];
            if (ch >= ' ') {
                chars[newLen] = ch;
                newLen++;
            }
        }
        if (newLen - off != length) {
            // We changed the internal state of the string, so at least
            // be friendly enough to correct it.
            try {
                count.setInt(old, newLen - off);
                // Have to recompute hash later on
                hash.setInt(old, 0);
            }
            catch(IllegalArgumentException e) {
                e.printStackTrace();
            }
            catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        // Well we have to return something
        return old;
    }

Pour mon test qui reçoit 3477148.18ops/s vs 2616120.89ops/s pour la variante ancienne. Je suis assez sûr que la seule façon de le battre que pourrait être l'écrire en C (sans doute pas si) ou d'une approche complètement différente personne n'a pensé. Bien que je ne suis absolument pas sûr si le timing est stable à travers les différentes plates-formes - donne des résultats fiables sur ma boîte (Java7, Win7 x64) au moins.

Answer 4

Vous pourriez diviser la tâche en plusieurs parallèle des sous-tâches, en fonction du processeur de la quantité.

Answer 5

IANA faible niveau de performance java junkie, mais avez-vous essayé de dérouler votre boucle principale? Il semble que cela pourrait permettre à certains CPU pour effectuer des contrôles en parallèle.

Aussi, la présente a quelques idées amusantes pour les optimisations.