Java 문자열에서 인쇄 할 수없는 모든 문자를 제거하는 가장 빠른 방법
StringJava 에서 인쇄 할 수없는 모든 문자를 제거하는 가장 빠른 방법은 무엇입니까 ?
지금까지 138 바이트, 131 자 문자열을 시도하고 측정했습니다.
- 문자열
replaceAll()- 가장 느린 방법- 517009 결과 / 초
- 패턴을 미리 컴파일 한 다음 Matcher의
replaceAll()- 637836 결과 / 초
- StringBuffer 사용,
codepointAt()하나씩 사용하여 코드 포인트 가져 오기 및 StringBuffer 추가- 711946 개의 결과 / 초
- StringBuffer를 사용하고,
charAt()하나씩 사용하여 문자를 얻고 StringBuffer에 추가하십시오.- 1052964 결과 / 초
char[]버퍼를 미리 할당하고 ,charAt()하나씩 사용하여 문자를 가져 와서이 버퍼를 채운 다음 다시 문자열로 변환합니다.- 2022653 개의 결과 / 초
- 2 개 미리 할당
char[]버퍼 - 사용하여 한 번에 과거와는 문자열을 기존의 모든 문자를 얻을getChars()반복,이 위에 오래 된 버퍼 일대일로 새로운 버퍼를 채우기, 다음 문자열에 새로운 버퍼를 변환 - 내 자신의 빠른 버전을- 2502502 개 결과 / 초
- 만 사용 -이 버퍼와 같은 것들
byte[],getBytes()그리고 "UTF-8"로 인코딩을 지정- 857485 결과 / 초
- 2 개의
byte[]버퍼가있는 동일한 항목 이지만 인코딩을 상수로 지정Charset.forName("utf-8")- 791076 개의 결과 / 초
- 2 개의
byte[]버퍼가있는 동일한 항목 이지만 인코딩을 1 바이트 로컬 인코딩으로 지정 (간신히 수행해야 할 일)- 370164 결과 / 초
최선의 시도는 다음과 같습니다.
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);
더 빠르게 만드는 방법에 대한 의견이 있으십니까?
매우 이상한 질문에 답하는 데 대한 보너스 포인트 : "utf-8"문자셋 이름을 사용하면 사전 할당 된 정적 const를 사용하는 것보다 직접적으로 더 나은 성능을 얻을 수있는 이유는 Charset.forName("utf-8")무엇입니까?
최신 정보
- 래칫 괴물의 제안 은 인상적인 3105590 결과 / 초 성능을 제공하여 + 24 % 향상되었습니다!
- Ed Staub의 제안은 또 다른 개선을 가져 왔습니다. 3471017 결과 / 초, 이전 최고 대비 + 12 %.
업데이트 2
나는 모든 제안 된 솔루션과 그 교차 돌연변이를 수집하기 위해 최선을 다하고 github에 작은 벤치마킹 프레임 워크 로 게시했습니다 . 현재 17 개의 알고리즘이 있습니다. 그중 하나는 "특별한" -Voo1 알고리즘 ( SO 사용자 Voo 제공 )은 복잡한 반사 트릭을 사용하여 뛰어난 속도를 달성하지만 JVM 문자열의 상태를 엉망으로 만들어 별도로 벤치마킹됩니다.
확인하고 실행하여 상자에 대한 결과를 확인할 수 있습니다. 다음은 제가 얻은 결과의 요약입니다. 사양 :
- 데비안 sid
- Linux 2.6.39-2-amd64 (x86_64)
- 패키지에서 설치된 Java
sun-java6-jdk-6.24-1, JVM은 자신을 다음과 같이 식별합니다.- Java (TM) SE 런타임 환경 (빌드 1.6.0_24-b07)
- Java HotSpot (TM) 64 비트 서버 VM (빌드 19.1-b02, 혼합 모드)
서로 다른 알고리즘은 서로 다른 입력 데이터 세트가 주어지면 궁극적으로 서로 다른 결과를 보여줍니다. 3 가지 모드에서 벤치 마크를 실행했습니다.
동일한 단일 문자열
이 모드는 StringSource클래스가 상수로 제공하는 동일한 단일 문자열에서 작동합니다 . 대결은 다음과 같습니다.
Ops / s │ 알고리즘 ──────────┼────────────────────────────── 6535947 │ Voo1 ──────────┼────────────────────────────── 5350454 │ RatchetFreak2EdStaub1GreyCat1 5249 343 │ EdStaub1 5002501 │ EdStaub1GreyCat1 4859086 │ ArrayOfCharFromStringCharAt 4295532 │ RatchetFreak1 4045307 │ ArrayOfCharFromArrayOfChar 2790178 │ RatchetFreak2EdStaub1GreyCat2 2583311 │ RatchetFreak2 1274 859 │ StringBuilderChar 1138174 │ StringBuilderCodePoint 994727 │ ArrayOfByteUTF8String 918611 │ ArrayOfByteUTF8Const 756 086 │ MatcherReplace 598945 │ StringReplaceAll 460 045 │ ArrayOfByteWindows1251
차트 형식 : (출처 : greycat.ru )
여러 문자열, 문자열의 100 %에 제어 문자가 포함됨
소스 문자열 공급자는 (0..127) 문자 집합을 사용하여 많은 임의의 문자열을 미리 생성했습니다. 따라서 거의 모든 문자열에 하나 이상의 제어 문자가 포함되었습니다. 알고리즘은이 사전 생성 된 배열에서 라운드 로빈 방식으로 문자열을 수신했습니다.
Ops / s │ 알고리즘 ──────────┼────────────────────────────── 2123142 │ Voo1 ──────────┼────────────────────────────── 1782214 │ EdStaub1 1776199 │ EdStaub1GreyCat1 1694628 │ ArrayOfCharFromStringCharAt 1481481 │ ArrayOfCharFromArrayOfChar 1460 067 │ RatchetFreak2EdStaub1GreyCat1 1438435 │ RatchetFreak2EdStaub1GreyCat2 1366 494 │ RatchetFreak2 1,349,710 │ RatchetFreak1 893176 │ ArrayOfByteUTF8String 817127 │ ArrayOfByteUTF8Const 778 089 │ StringBuilderChar 734754 │ StringBuilderCodePoint 377 829 │ ArrayOfByteWindows1251 224140 │ MatcherReplace 211104 │ StringReplaceAll
차트 형식 : (출처 : greycat.ru )
여러 문자열, 문자열의 1 %에 제어 문자가 포함됨
이전과 동일하지만 제어 문자로 문자열의 1 % 만 생성되었습니다. 다른 99 %는 [32..127] 문자 집합을 사용하여 생성되었으므로 제어 문자를 전혀 포함 할 수 없습니다. 이 합성 부하는 제 자리에서이 알고리즘의 실제 적용에 가장 가깝습니다.
Ops / s │ 알고리즘 ──────────┼────────────────────────────── 3711952 │ Voo1 ──────────┼────────────────────────────── 2851440 │ EdStaub1GreyCat1 2455796 │ EdStaub1 2426007 │ ArrayOfCharFromStringCharAt 2347969 │ RatchetFreak2EdStaub1GreyCat2 2242152 │ RatchetFreak1 2171 553 │ ArrayOfCharFromArrayOfChar 1922707 │ RatchetFreak2EdStaub1GreyCat1 1857010 │ RatchetFreak2 1,023 751 │ ArrayOfByteUTF8String 939 055 │ StringBuilderChar 907194 │ ArrayOfByteUTF8Const 841963 │ StringBuilderCodePoint 606465 │ MatcherReplace 501555 │ StringReplaceAll 381185 │ ArrayOfByteWindows1251
차트 형식 : (출처 : greycat.ru )
누가 가장 좋은 답변을 제공했는지 결정하기가 매우 어렵지만 실제 응용 프로그램이 Ed Staub에 의해 제공되고 영감을받은 실제 응용 프로그램을 고려할 때 그의 답변을 표시하는 것이 공정 할 것 같습니다. 참여 해주신 모든 분들께 감사 드리며, 귀하의 의견은 매우 유용하고 귀중했습니다. 상자에서 테스트 스위트를 자유롭게 실행하고 더 나은 솔루션을 제안하십시오 (JNI 솔루션을 사용하고 있습니까?).
참고 문헌
- 벤치마킹 제품군이있는 GitHub 저장소
스레드간에 공유되지 않는 클래스에이 메서드를 포함하는 것이 합리적이면 버퍼를 재사용 할 수 있습니다.
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);
기타...
현재 최선의 사례를 이해하고 있기 때문에 20 % 정도의 큰 승리입니다.
이것이 잠재적으로 큰 문자열에 사용되어야하고 메모리 "누수"가 우려되는 경우 약한 참조를 사용할 수 있습니다.
1 문자 배열을 사용하면 조금 더 잘 작동 할 수 있습니다.
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);
그리고 나는 반복되는 전화를 피했습니다 s.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);
내 측정에 따르면 현재 최선의 방법 (사전 할당 된 배열을 사용하는 괴물의 솔루션)을 약 30 % 이겼습니다. 어떻게? 내 영혼을 팔아서.
As I'm sure everyone that has followed the discussion so far knows this violates pretty much any basic programming principle, but oh well. Anyways the following only works if the used character array of the string isn't shared between other strings - if it does whoever has to debug this will have every right deciding to kill you (without calls to substring() and using this on literal strings this should work as I don't see why the JVM would intern unique strings read from an outside source). Though don't forget to make sure the benchmark code doesn't do it - that's extremely likely and would help the reflection solution obviously.
Anyways here we go:
// 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;
}
For my teststring that gets 3477148.18ops/s vs. 2616120.89ops/s for the old variant. I'm quite sure the only way to beat that could be to write it in C (probably not though) or some completely different approach nobody has thought about so far. Though I'm absolutely not sure if the timing is stable across different platforms - produces reliable results on my box (Java7, Win7 x64) at least.
You could split the task into a several parallel subtasks, depending of processor's quantity.
I was so free and wrote a small benchmark for different algorithms. It's not perfect, but I take the minimum of 1000 runs of a given algorithm 10000 times over a random string (with about 32/200% non printables by default). That should take care of stuff like GC, initialization and so on - there's not so much overhead that any algorithm shouldn't have at least one run without much hindrance.
Not especially well documented, but oh well. Here we go - I included both of ratchet freak's algorithms and the basic version. At the moment I randomly initialize a 200 chars long string with uniformly distributed chars in the range [0, 200).
IANA low-level java performance junkie, but have you tried unrolling your main loop? It appears that it could allow some CPU's to perform checks in parallel.
Also, this has some fun ideas for optimizations.
why using "utf-8" charset name directly yields better performance than using pre-allocated static const Charset.forName("utf-8")?
If you mean String#getBytes("utf-8") etc.: This shouldn't be faster - except for some better caching - since Charset.forName("utf-8") is used internally, if the charset is not cached.
One thing might be that you're using different charsets (or maybe some of your code does transparently) but the charset cached in StringCoding doesn't change.
'Development Tip' 카테고리의 다른 글
| 블루투스 핸즈프리 클라이언트 볼륨 제어 (0) | 2020.10.10 |
|---|---|
| Docker 및 --userns-remap, 호스트와 컨테이너간에 데이터를 공유하기 위해 볼륨 권한을 관리하는 방법은 무엇입니까? (0) | 2020.10.10 |
| 2012 년 6 월 12 일부터 내 웹 사이트에서 요청한 URL의 1 %에 "정의되지 않음"이 무작위로 추가됨 (0) | 2020.10.10 |
| 서버에서 보낸 이벤트와 PHP-서버에서 이벤트를 트리거하는 것은 무엇입니까? (0) | 2020.10.10 |
| Git-선택한 파일에서 병합 충돌 및 수동 병합을 강제하는 방법 (0) | 2020.10.10 |