在看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 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
测试的一个结果如下所示：
-------------------------- 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是有自己的统计的，但是样本不太好做。
如此看来，数据的准备，也就是测试用例的选取很关键,可能需要先生成并写入到文本文件中。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 