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 1481 481 │ ArrayOfCharFromArrayOfChar 1460067 │ 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 % 이겼습니다. 어떻게? 내 영혼을 팔아서.
지금까지 논의한 모든 사람들이 이것이 거의 모든 기본 프로그래밍 원칙을 위반한다는 것을 알고 있다고 확신합니다. 어쨌든 다음은 문자열의 사용 된 문자 배열이 다른 문자열간에 공유되지 않는 경우에만 작동합니다. 디버깅해야하는 사람이 누구든지 당신을 죽일 수있는 모든 권리를 가질 것입니다 (substring () 호출없이 리터럴 문자열에 이것을 사용하는 것입니다) 이것은 JVM이 외부 소스에서 읽은 고유 문자열을 인턴하는 이유를 알지 못하기 때문에 작동합니다.) 벤치 마크 코드가이를 수행하지 않는지 확인하는 것을 잊지 마십시오. 이는 매우 가능성이 높으며 분명히 리플렉션 솔루션에 도움이 될 것입니다.
어쨌든 우리는 간다 :
// 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;
}
내 테스트 문자열의 경우 이전 변형 3477148.18ops/s과 비교 2616120.89ops/s합니다. 이길 수있는 유일한 방법은 C로 작성하거나 (아마도 그렇지 않을 수도 있음) 지금까지 아무도 생각하지 않은 완전히 다른 접근 방식을 사용하는 것입니다. 타이밍이 다른 플랫폼에서 안정적인지 확실하지 않지만 적어도 내 상자 (Java7, Win7 x64)에서 안정적인 결과를 생성합니다.
답변
프로세서의 수량에 따라 작업을 여러 개의 병렬 하위 작업으로 분할 할 수 있습니다.
답변
나는 너무 자유롭고 다른 알고리즘에 대한 작은 벤치 마크를 작성했습니다. 완벽하지는 않지만 임의의 문자열 (기본적으로 약 32 / 200 % 인쇄 불가능)에 대해 주어진 알고리즘을 10000 번 이상 실행합니다. 그것은 GC, 초기화 등과 같은 것들을 처리해야합니다. 어떤 알고리즘도 많은 방해없이 적어도 한 번의 실행을 가져서는 안되는 오버 헤드가 너무 많지 않습니다.
특히 잘 문서화되어 있지는 않지만 오 잘. 여기에 우리 는 래칫 괴물의 알고리즘과 기본 버전을 모두 포함했습니다. 현재는 [0, 200) 범위의 균일하게 분산 된 문자로 200 자 긴 문자열을 무작위로 초기화합니다.
답변
답변
“utf-8″문자셋 이름을 사용하면 미리 할당 된 static const Charset.forName ( “utf-8”)을 사용하는 것보다 직접적으로 더 나은 성능을 얻을 수있는 이유는 무엇입니까?
String#getBytes("utf-8")등 을 의미하는 경우 : Charset.forName("utf-8")문자 집합이 캐시되지 않은 경우 내부적으로 사용 되기 때문에 더 나은 캐싱을 제외하고는 빠르지 않아야합니다 .
한 가지는 다른 문자 집합을 사용하고 있거나 일부 코드가 투명하게 작동하지만 캐시 된 문자 집합 StringCoding이 변경되지 않는다는 것입니다.
