What is the fastest way to strip all non-printable characters from a String
in Java?
So far I've tried and measured on 138-byte, 131-character String:
replaceAll()
- slowest method replaceAll()
codepointAt()
one-by-one and append to StringBuffer charAt()
one-by-one and append to StringBuffer char[]
buffer, get chars using charAt()
one-by-one and fill this buffer, then convert back to String char[]
buffers - old and new, get all chars for existing String at once using getChars()
, iterate over old buffer one-by-one and fill new buffer, then convert new buffer to String - my own fastest version byte[]
, getBytes()
and specifying encoding as "utf-8" byte[]
buffers, but specifying encoding as a constant Charset.forName("utf-8")
byte[]
buffers, but specifying encoding as 1-byte local encoding (barely a sane thing to do) My best try was the following:
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);
Any thoughts on how to make it even faster?
Bonus points for answering a very strange question: why using "utf-8" charset name directly yields better performance than using pre-allocated static const Charset.forName("utf-8")
?
I've tried my best to collected all the proposed solutions and its cross-mutations and published it as a small benchmarking framework at github. Currently it sports 17 algorithms. One of them is "special" - Voo1 algorithm (provided by SO user Voo) employs intricate reflection tricks thus achieving stellar speeds, but it messes up JVM strings' state, thus it's benchmarked separately.
You're welcome to check it out and run it to determine results on your box. Here's a summary of results I've got on mine. It's specs:
sun-java6-jdk-6.24-1
, JVM identifies itself as Different algorithms show ultimately different results given a different set of input data. I've ran a benchmark in 3 modes:
This mode works on a same single string provided by StringSource
class as a constant. The showdown is:
Ops / s │ Algorithm ──────────┼────────────────────────────── 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
In charted form:
(source: greycat.ru)
Source string provider pre-generated lots of random strings using (0..127) character set - thus almost all strings contained at least one control character. Algorithms received strings from this pre-generated array in round-robin fashion.
Ops / s │ Algorithm ──────────┼────────────────────────────── 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
In charted form:
(source: greycat.ru)
Same as previous, but only 1% of strings was generated with control characters - other 99% was generated in using [32..127] character set, so they couldn't contain control characters at all. This synthetic load comes the closest to real world application of this algorithm at my place.
Ops / s │ Algorithm ──────────┼────────────────────────────── 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
In charted form:
(source: greycat.ru)
It's very hard for me to decide on who provided the best answer, but given the real-world application best solution was given/inspired by Ed Staub, I guess it would be fair to mark his answer. Thanks for all who took part in this, your input was very helpful and invaluable. Feel free to run the test suite on your box and propose even better solutions (working JNI solution, anyone?).
replaceAll("\\p{Cntrl}", "?"); The following will replace all ASCII non-printable characters (shorthand for [\p{Graph}\x20] ), including accented characters: my_string. replaceAll("[^\\p{Print}]", "?");
The idea is to use the deleteCharAt() method of StringBuilder class to remove first and the last character of a string. The deleteCharAt() method accepts a parameter as an index of the character you want to remove. Remove last character of a string using sb. deleteCharAt(str.
string_variable. replaceAll("\\p{C}", "?"); This will replace all non-printable characters. Where p{C} selects the invisible control characters and unused code points.
using 1 char array could work a bit better
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);
and I avoided repeated calls to s.length();
another micro-optimization that might work is
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);
If it is reasonable to embed this method in a class which is not shared across threads, then you can reuse the buffer:
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...
This is a big win - 20% or so, as I understand the current best case.
If this is to be used on potentially large strings and the memory "leak" is a concern, a weak reference can be used.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With