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

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:

De la chaîne de replaceAll() - méthode la plus lente
- 517009 résultats /sec
Précompiler un Modèle, puis utilisez Comparateur de replaceAll()
- 637836 résultats /sec
Utilisation StringBuffer, obtenir codepoints à l'aide de codepointAt() un par un et de les ajouter à StringBuffer
- 711946 résultats /sec
Utilisation 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);

Des idées sur la façon de le rendre encore plus rapide?

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 cliquet freak rendements impressionnants 3105590 résultats /s de performance, un +24% d'amélioration!
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 recueilli toutes les solutions proposées et de ses croix-mutations et publié comme un petite analyse comparative cadre sur github. Actuellement, il arbore 17 algorithmes. L'un d'eux est "spécial" - Voo1 algorithme (pour les utilisateur de 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 specs:

Debian sid
Linux 2.6.39-2-amd64 (x86_64)
Java 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:

Seule et même chaîne de

Ce mode fonctionne sur une seule et même chaîne fournie par 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:
Même seule chaîne graphique http://www.greycat.ru/img/os-chart-single.png

Plusieurs cordes à la fois, 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, 100% de concentration http://www.greycat.ru/img/os-chart-multi100.png

Plusieurs chaînes, plus 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 les caractères de contrôle à tous. 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:
Plusieurs chaînes, la concentration de 1% http://www.greycat.ru/img/os-chart-multi1.png

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

"Cette question montre effort de recherche" - hmm... ouais, passe. +1
StringBuilder sera légèrement plus rapide que StringBuffer que c'est non-synchronisé, je viens de le mentionner parce que vous tagged cette micro-optimization
Roberson: ok, donc, nous allons faire tous les champs en lecture seule finale et l'extrait de s.length() de la for boucle 🙂
Certains caractères en dessous de l'espace sont imprimables par exemple \t et \n. De nombreux personnages au-dessus de 127 sont non-imprimables dans votre jeu de caractères.
avez-vous initialisation de la mémoire tampon de chaîne avec une capacité de s.length()?
Je suis d'accord je fais tout ce que je peux final, mais pour autres raisons et si vous êtes à la recherche à la micro-optimisation de la prise de la .length() lu une fois est un autre micro-optimisation. Je veux dire, c'est taggés micro-optimization n'est-ce pas!
Roberson: plein d'accusé de réception, c'est pourquoi j'ai mentionné, c' - btw je fais tous les champs final pour exactement la même raison 🙂
freak: Oui, je n'ai new StringBuffer(s.length())
voulez-vous poster le code de l'actuel meilleur des cas? C'est un peu difficile à démêler ensemble des réponses à ces questions et à vos commentaires.
S'il vous plaît vérifier la question de mise à jour - j'ai posté le cadre de tests et massive de l'abattage de l'ensemble des 17 algorithmes proposés.
regardant en arrière, nous n'avons fait éviter le superflu, la répartition des tableaux de char (et de la nouvelle Chaîne de l'objet quand il n'y avait pas de changement)
Ouais, mais ce sont vraiment microoptimizations - de sorte qu'ils dépendent des données d'entrée d'un lot, une petite maj dans quelques coefficient rend les algorithmes avec ou sans contrôles supplémentaires changer de place.

InformationsquelleAutor GreyCat | 2011-08-23

9

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é.
- Excellente idée! Jusqu'à présent, il a introduit le compte jusqu'à 3471017 chaînes de caractères par seconde - c'est à dire un +12% d'amélioration par rapport aux précédentes meilleure version.
InformationsquelleAutor Ed Staub

à 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]='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);
';//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);

Merci! Votre version des rendements 3105590 chaînes de caractères / s - une amélioration massive!
newLen++;: que sur l'utilisation de pré-incrémentation ++newLen;? - (++j dans la boucle). Jetez un oeil ici: stackoverflow.com/questions/1546981/...
L'ajout de final à cet algorithme et l'utilisation de oldChars[newLen++] (++newLen est une erreur de l'ensemble de la chaîne de large par 1!) n'apportent pas de gains de performance mesurables (c'est à dire-je obtenir ±2..3% des différences, qui sont comparables à des différences de différentes pistes)
J'ai fait une autre version avec quelques autres optimisations
ainsi vous pouvez initialiser newLen avec -1 pour tenir compte de cela.
Ne pourrait-il pas être oldChars[length]='\0?
corrigé 🙂
Vous avez sans doute signifiait oldChars[length] = '\0' au lieu oldChars='\0'? Mais même alors, si me manque avec des résultats erronés... Laissez-moi vérifier...
J'ai fait le char tableau 1 plus grand compte de cette
freak Votre nouvelle version ne coupons pas le premier a trouvé un caractère non imprimable - il pourrait être rapidement corrigé par l'ajout de newLen-- après une boucle while...
Et, ainsi, aucun des améliorations mesurables dans votre 2ème version...
eh bien, il serait seulement d'améliorer dans ma deuxième version, lorsque le début de la chaînes sont pour une grande partie imprimable (c'est à dire les caractères non imprimables sont rares et la plupart du temps près de la fin).
Hmm! C'est une idée géniale! 99,9% des chaînes dans mon environnement de production n'aurez pas vraiment besoin de décapage - je peux l'améliorer afin d'éliminer même les premiers char[] allocation et le retour de la Chaîne, si aucun décapage qui s'est passé.

InformationsquelleAutor ratchet freak

9

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 obtient 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.
- Merci pour la solution, s'il vous plaît vérifier la question de mise à jour - j'ai publié mon framework de test et a ajouté 3 essai de résultats pour les 17 algorithmes. Votre algorithme est toujours sur le dessus, mais il change d'état interne de Java String, brisant ainsi le "immuable" Chaîne de contrat => il serait assez difficile de l'utiliser dans le monde réel de l'application. Test-sage, ouais, c'est le meilleur résultat, mais je crois que je vais l'annoncer en tant que distincte de candidature 🙂
- Ouais, il a certainement quelques grosses ficelles attachées et honnêtement j'ai assez bien écrit parce que je suis assez sûr il n'y a pas de manière notable à améliorer votre meilleure solution actuelle plus loin. Il y a des situations où je suis certain que ça va fonctionner correctement (pas de sous-chaîne ou stagiaire appels avant de la dépouiller ), mais c'est parce que de la connaissance sur un Hotspot version (c'est à dire autant que je sache, il ne sera pas stagiaire chaînes de lire à partir de IO - ne serait pas particulièrement utile). Il peut être utile si on a vraiment besoin de personnes supplémentaires x%, mais autrement plus une base de référence pour voir combien vous pouvez encore améliorer 😉
- Si je suis tenté d'essayer une JNI version si je trouve le temps - n'a jamais été utilisé jusqu'à présent donc, ce serait intéressant. Mais je suis sûr que ça va être plus lent en raison de l'appel supplémentaire, les frais généraux (les chaînes de caractères sont trop petits) et le fait que l'équipe ne devrait pas avoir tant de mal à optimiser les fonctions. Il suffit de ne pas utiliser new String() dans le cas où votre chaîne n'a pas été changé, mais je pense que vous avez déjà.
- J'ai déjà essayé de faire exactement la même chose dans le plus pur C - et bien, il ne fait pas vraiment preuve de beaucoup d'amélioration par rapport à votre réflexion basée sur la version. C version fonctionne quelque chose comme +5..10% plus rapide, pas vraiment de la great - j'ai pensé qu'il serait au moins égal à 1,5 x 1,7 x...
InformationsquelleAutor Voo
2

Vous pourriez diviser la tâche en plusieurs parallèle des sous-tâches, en fonction du processeur de la quantité.
- Ouais, j'y ai pensé aussi, mais il n'est pas de dégager des gains de performances dans ma situation - ce dépouillement de l'algorithme serait appelé déjà massivement parallèle du système.
- Et, d'ailleurs, pourrais-je deviner que la fourche quelques threads de traitement pour tous les 50-100 chaîne d'octets serait une énorme overkill.
- Oui, un fork de threads pour chaque petite chaîne n'est pas une bonne idée. Mais d'équilibrage de la charge pourrait améliorer les performances. BTW, avez-vous le test de performance avec StringBuilder au lieu de StringBuffer qui a des performances manque car il est synchronisé.
- Ma production de l'exécution du programme engendre plusieurs processus distincts et utilise la quantité parallèle des Processeurs et des carottes que possible, afin que je puisse utiliser librement StringBuilder partout sans aucun problème à tous.
InformationsquelleAutor umbr
1

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

Aussi, cette a quelques idées amusantes pour les optimisations.
- Je doute qu'aucun de dérouler pourrait être fait ici, comme il y a (a) les dépendances sur les étapes suivantes de l'algorithme sur les étapes précédentes, (b) je n'ai même pas entendu parler de quelqu'un manuel déroulement de la boucle en Java produire des résultats stellaires; JIT fait généralement un bon travail à dérouler ce qu'il voit à côté de la tâche. Merci pour la suggestion et un lien bien 🙂
InformationsquelleAutor Ryan Ransford
1

J'étais tellement libre et écrit un petit test pour les différents algorithmes. Il n'est pas parfait, mais je prends le minimum de 1000 pistes d'un algorithme donné 10000 fois sur une chaîne aléatoire (à propos de 32/200% non imprimables par défaut). Qui doit prendre soin des choses comme la GC, l'initialisation et ainsi de suite - il n'y a pas tellement généraux que l'algorithme ne devriez pas avoir au moins un run sans trop d'entraves.

Pas particulièrement bien documenté, mais bon. Ici nous allons - J'ai inclus à la fois de ratchet freak les algorithmes et la version de base. Au moment où je au hasard initialiser un 200 caractères chaîne de caractères uniformément distribué des caractères dans la plage [0, 200).
- +1 pour l'effort, mais vous devriez vous m'avez demandé - j'ai déjà une semblable analyse comparative de suite - c'est là où j'ai été le tester mes algorithmes 😉
- Eh bien, je pourrais avoir, mais juste jeter que ensemble (hors de code existant de toute façon), a probablement été plus rapide 😉
InformationsquelleAutor Voo
0

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")?

Si vous voulez dire String#getBytes("utf-8") etc.: Cela ne devrait pas être plus rapide - sauf pour une meilleure mise en cache depuis Charset.forName("utf-8") est utilisé en interne, si le jeu de caractères n'est pas mis en cache.

Une chose peut-être que vous êtes à l'aide de différents jeux de caractères (ou peut-être certains de votre code n'transparente) mais le jeu de caractères mis en cache dans StringCoding ne change pas.

InformationsquelleAutor Thomas

Vous devez vous connecter pour publier un commentaire.