1. IT分享知识网首页

StringBuilder有多消耗性能?[通俗易懂]

老牧童 • • 未分类 • 阅读 179

StringBuilder有多消耗性能?[通俗易懂]在看KMP算法时,想要简单的统计一下执行时间和性能。 dechude

大家好，欢迎来到IT知识分享网。

在看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;
		
		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秒。换算下来每秒钟是1600万次。。。

看来是需要写一个专门计时的函数，本来Junit是有自己的统计的，但是样本不太好做。

如此看来，数据的准备，也就是测试用例的选取很关键,可能需要先生成并写入到文本文件中。

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/26285.html

赞 (0)
老牧童老牧童
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信