Java에서 StringBuilder 성능 테스트

KMP 알고리즘을 보면 단순히 실행시간과 성능만을 계산하고 싶다.

결론은 다음과 같습니다. Java의 String indexOf 메소드가 가장 성능이 좋으며 그 다음은 KMP 알고리즘, 그 다음은 전통적인 BF 알고리즘입니다. 물론 SUN의 알고리즘도 Java에서 구현되므로 비교가 어렵습니다. 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;긴 시작 = 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 = 시스템 .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();//긴 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+손실시간)/전체시간 * 100)+"%");System.out.println("---------------");}}//시스템. out.println(times+"times bfIndexOf; 총 시간 소비: "+allBF+"ms");System.out.println(times+"times stringIndexOf; 총 시간 소비: "+allString+"ms");System.out.println( 회+" 회 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; loss:" + 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;//긴 시드 = System.nanoTime();무작위 무작위 = 신규 Random(seed);////StringBuilder builder = new StringBuilder();for (int i = 0; i < len; i++) {//int type = random.nextInt(3);// 0-2int cvalue = 0;if(TYPE_NUMBER == 유형){cvalue = '0' + random.nextInt(10);// 0~(n-1)} else if(TYPE_LOWERCASE == 유형){cvalue = 'a' + random.nextInt(26);// 0~(n-1)} else if(TYPE_UPPERCASE == 유형){cvalue = 'A' + random.nextInt( 26);// 0~(n-1)} else {새 항목 던지기 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;}}// If j lenSub와 같아지면 일치가 성공합니다. if (lenSub == j){return i - lenSub;} else {i = 1+i - j; // Backtrack 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);} /** * 문자열의 다음 함수 값 가져오기* * @param t * String* @return 다음 함수 값*/ public static int[] next(char[] t) { int[] next = new int[t.length]; next[0] = -1 int i = 0; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; 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) == -1 || allArray[i] == subArray[j]) { i++; j++; } else { j = next[j] } } if (j < subArray.length) } else return i - subArray.length; // 메인 문자열의 패턴 문자열의 선두 인덱스를 반환합니다.} }

테스트 결과 중 하나는 다음과 같습니다.

 -------------10회 bfIndexOf= 94ms10회 stringIndexOf= 56ms10회 KMPIndexOf= 76ms10회 allbuild= 5870ms10회 alltoArray= 137ms10*3회 ,GC= 155ms10회, 총 소요 시간: 6388ms, 손실률: 6007ms 94.03569192235442%------------------30회 bfIndexOf= 365ms30회 stringIndexOf= 222ms30회 KMPIndexOf= 295ms30회 allbuild= 16452ms30회 alltoArray = 395ms30* 3회, GC= 452ms30회, 총 소요 시간: 18184ms; 손실: 16850ms; 손실률: 92.66388033435987%------------50배 bfIndexOf; 총 시간 소비: 550ms; : 335ms50배 KMPIndexOf; 총 소요 시간: 450ms50배 allbuild= 26501ms50배 alltoArray= 637ms50*3회, GC, 총 시간 소모: 734ms50회, 총 시간 소모: 29211ms, 손실률: 92.91705179555647%------- -----

StringBuilder를 사용하여 문자열을 생성하면 800만 * 50번 추가에 약 26초가 소요되는 것을 볼 수 있습니다. 이는 초당 1,600만 번에 해당합니다. . .
원래 Junit에는 자체 통계가 있었지만 샘플을 만드는 것이 쉽지 않았습니다.

이러한 관점에서 데이터 준비, 즉 테스트 사례 선택이 중요하며 먼저 생성하여 텍스트 파일에 작성해야 할 수도 있습니다.