StringBuilder 는 성능 을 얼마나 소모 합 니까?
9329 단어 알고리즘
결론 은 자바 의 String 의 index Of 방법 은 성능 이 가장 좋 고 그 다음은 KMP 알고리즘 이 며 그 다음은 전통 적 인 BF 알고리즘 입 니 다. 물론 비교 가 약간 억 지 스 럽 습 니 다. 썬 의 알고리즘 도 자바 로 이 루어 지고 사용 하 는 것 이 KMP 가 아 닌 것 같 습 니 다. 상세 한 연구 가 필요 합 니 다.
테스트 코드 는 다음 과 같다.
package com.test.test.kmp;
import java.util.Random;
public class KMPTest {
public static void main(String[] args) {
test();
}
//
public static void test() {
//
int allLen = 8000000;
int subLen = 11;
int charLen = 4;
String cl = buildString(charLen);
int times = 50;
//
testMatch(allLen, subLen, cl, times);
}
public static void testMatch(int allLen, int subLen, String cl, int times){
int allBF = 0;
int allString = 0;
int allKMP = 0;
int allGC = 0;
int allbuild = 0;
int alltoArray = 0;
long start = System.currentTimeMillis();
System.out.println("--------------------------");
for (int i = 0; i < times; i++) {
// 1.
long buildStart = System.currentTimeMillis();
String sub = buildString(subLen, cl);
String all = buildString(allLen, sub) +sub;
long buildEnd = System.currentTimeMillis();
allbuild += (buildEnd - buildStart);
// 2. toCharArray
long toArrayStart = System.currentTimeMillis();
char[] allArray = all.toCharArray();
char[] subArray = sub.toCharArray();
long toArrayEnd = System.currentTimeMillis();
alltoArray += (toArrayEnd - toArrayStart);
//
long startBF = System.currentTimeMillis();
int indexBF = bfIndexOf(all, sub);
long endBF = System.currentTimeMillis();
//
long timeoutBF = endBF - startBF;
allBF += timeoutBF;
System.gc();
allGC += (System.currentTimeMillis() - endBF);
//
long startString = System.currentTimeMillis();
int indexString = stringIndexOf(all, sub);
long endString = System.currentTimeMillis();
//
long timeoutString = endString - startString;
allString += timeoutString;
System.gc();
allGC += (System.currentTimeMillis() - endString);
//
long startKMP = System.currentTimeMillis();
//int indexKMP = kmpIndexOf(all, sub);
int indexKMP = KMP_Index(allArray, subArray);
long endKMP = System.currentTimeMillis();
//
long timeoutKMP = endKMP - startKMP;
allKMP += timeoutKMP;
System.gc();
allGC += (System.currentTimeMillis() - endKMP);
//
//System.out.println("all="+all.substring(0,100)+" ......");
//System.out.println("sub="+sub);
//
//System.out.println("indexBF="+indexBF+"; : "+timeoutBF+"ms");
//System.out.println("indexString="+indexString+"; : "+timeoutString+"ms");
if(indexBF == indexString && indexKMP == indexString){
//System.out.println("!!!! 。");
} else {
throw new RuntimeException(" .");
}
//
if(i % 20 == 10){
System.out.println(i+" bfIndexOf= "+allBF+"ms");
System.out.println(i+" stringIndexOf= "+allString+"ms");
System.out.println(i+" KMPIndexOf= "+allKMP+"ms");
System.out.println(i+" allbuild= "+allbuild+"ms");
System.out.println(i+" alltoArray= "+alltoArray+"ms");
System.out.println(i+"*3 ,GC= "+allGC+"ms");
long end = System.currentTimeMillis();
long allTime = end-start;
long lossTime = allTime - (allBF+allString+allKMP+allGC);
System.out.println(i+" , : "+(allTime)+"ms; :" + lossTime +"ms; : " +((0.0+lossTime)/allTime * 100)+"%");
System.out.println("--------------------------");
}
}
//
System.out.println(times+" bfIndexOf; : "+allBF+"ms");
System.out.println(times+" stringIndexOf; : "+allString+"ms");
System.out.println(times+" KMPIndexOf; : "+allKMP+"ms");
System.out.println(times+" allbuild= "+allbuild+"ms");
System.out.println(times+" alltoArray= "+alltoArray+"ms");
System.out.println(times+"*3 ,GC; : "+allGC+"ms");
long end = System.currentTimeMillis();
long allTime = end-start;
long lossTime = allTime - (allBF+allString+allKMP+allGC);
System.out.println(times+" , : "+(allTime)+"ms; :" + lossTime +"ms; : " +((0.0+lossTime)/allTime * 100)+"%");
System.out.println("--------------------------");
}
//
//
public static String buildString(int len){
return buildString(len, null);
}
public static String buildString(int len, String sub){
//
final int TYPE_NUMBER = 0;
final int TYPE_LOWERCASE = 1;
final int TYPE_UPPERCASE = 2;
//
long seed = System.nanoTime();
Random random = new Random(seed);
//
//
StringBuilder builder = new StringBuilder();
for (int i = 0; i < len; i++) {
//
int type = random.nextInt(3);// 0-2
int cvalue = 0;
if(TYPE_NUMBER == type){
cvalue = '0' + random.nextInt(10);// 0~(n-1)
} else if(TYPE_LOWERCASE == type){
cvalue = 'a' + random.nextInt(26);// 0~(n-1)
} else if(TYPE_UPPERCASE == type){
cvalue = 'A' + random.nextInt(26);// 0~(n-1)
} else {
throw new RuntimeException(Random.class.getName()+"#newxtInt(int);Wrong!");
}
//
//cvalue = 'A' + random.nextInt(26);// 0~(n-1)
//
char c = (char)cvalue;
if(null != sub && sub.length() > 1){
int index = random.nextInt(sub.length());
c = sub.charAt(index);
}
//String s = String.valueOf(c);
builder.append(c);
//
}
//
return builder.toString();
}
/**
* Java ,
* @param all
* @param sub
* @return
*/
public static int stringIndexOf(String all, String sub){
//
if(null == all || null== sub){
return -1;
}
// Java String
return all.indexOf(sub);
}
/**
* BF
* @param all
* @param sub
* @return
*/
public static int bfIndexOf(String all, String sub){
//
if(null == all || null== sub){
return -1;
}
//
int lenAll = all.length();
int lenSub = sub.length();
int i = 0;
while (i < lenAll) {
// i
int j = 0;
while (j < lenSub) {
//
char all_i = all.charAt(i);
char sub_j = sub.charAt(j);
if(all_i == sub_j){
//
i++;
j++; //
} else {
//
break;
}
}
// j lenSub ,
if(lenSub == j){
return i - lenSub;
} else {
i = 1+i - j; // i
}
}
//
return -1;
}
/**
* KMP
* @param all
* @param sub
* @return
*/
public static int kmpIndexOf(String all, String sub){
//
char[] allArray = all.toCharArray();
char[] subArray = sub.toCharArray();
//
return KMP_Index(allArray, subArray);
}
/**
* next
*
* @param t
*
* @return next
*/
public static int[] next(char[] t) {
int[] next = new int[t.length];
next[0] = -1;
int i = 0;
int j = -1;
while (i < t.length - 1) {
if (j == -1 || t[i] == t[j]) {
i++;
j++;
if (t[i] != t[j]) {
next[i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j];
}
}
return next;
}
/**
* KMP
*
* @param allArray
*
* @param subArray
*
* @return ， ， -1
*/
public static int KMP_Index(char[] allArray, char[] subArray) {
int[] next = next(subArray);
int i = 0;
int j = 0;
while (i <= allArray.length - 1 && j <= subArray.length - 1) {
if (j == -1 || allArray[i] == subArray[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j < subArray.length) {
return -1;
} else
return i - subArray.length; //
}
}
테스트 의 결 과 는 다음 과 같다.
--------------------------
10 bfIndexOf= 94ms
10 stringIndexOf= 56ms
10 KMPIndexOf= 76ms
10 allbuild= 5870ms
10 alltoArray= 137ms
10*3 ,GC= 155ms
10 , : 6388ms; :6007ms; : 94.03569192235442%
--------------------------
30 bfIndexOf= 365ms
30 stringIndexOf= 222ms
30 KMPIndexOf= 295ms
30 allbuild= 16452ms
30 alltoArray= 395ms
30*3 ,GC= 452ms
30 , : 18184ms; :16850ms; : 92.66388033435987%
--------------------------
50 bfIndexOf; : 550ms
50 stringIndexOf; : 335ms
50 KMPIndexOf; : 450ms
50 allbuild= 26501ms
50 alltoArray= 637ms
50*3 ,GC; : 734ms
50 , : 29211ms; :27142ms; : 92.91705179555647%
--------------------------
StringBuilder 구조 문자열 을 사용 하면 800 만 * 50 회 append 가 약 26 초 소 모 된 것 을 알 수 있 습 니 다.환산 해 보면 1 초 에 1600 만 번...
보아하니 전문 적 으로 시간 을 재 는 함 수 를 써 야 할 것 같다. 원래 Junit 는 자신의 통 계 를 가지 고 있 지만 견본 은 만 들 기 가 쉽 지 않다.
그 러 고 보 니 데이터 의 준비, 즉 테스트 사례 의 선택 이 관건 이 고 텍스트 파일 에 먼저 생 성하 고 기록 해 야 할 수도 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
