Ao analisar o algoritmo KMP, quero simplesmente contar o tempo de execução e o desempenho.
A conclusão é: o método String indexOf do Java tem o melhor desempenho, seguido pelo algoritmo KMP, seguido pelo algoritmo BF tradicional. Claro, a comparação é um pouco rebuscada. O algoritmo da SUN também é implementado em Java, e não. Não parece que o KMP precisa ser estudado em detalhes.
O código de teste fica assim:
pacote com.test.test.kmp;importar java.util.Random;classe pública 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 vezes = 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;início longo = System.currentTimeMillis();System.out.println("--------------------------");for (int i = 0; i < times; i++) {// 1. A perda de construção de uma string long buildStart = System.currentTimeMillis();String sub = buildString(subLen, cl);String all = buildString(allLen, sub) +sub;long buildEnd = Sistema .currentTimeMillis();allbuild += (buildEnd - buildStart);// 2. A perda de 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 índiceKMP = KMP_Index(allArray, subArray);fim longoKMP = 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+";Demorado: "+timeoutBF+" ms");//System.out.println("indexString="+indexString+";Demorado: "+timeoutString+"ms");if(indexBF == indexString && indexKMP == indexString){//System.out.println("!!!!Contraste igual. ");} else {throw new RuntimeException("Erro de comparação.");}//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 vezes,GC= "+allGC+"ms");long end = System.currentTimeMillis();long allTime = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(i+" vezes, todo o tempo total consumido: "+(allTime)+"ms; loss:" + lossTime +"ms; taxa de perda: " +( (0,0+perdaTempo)/allTime * 100)+"%");System.out.println("--------------------------");}}//System. out.println(times+"times bfIndexOf; consumo total de tempo: "+allBF+"ms");System.out.println(times+"times stringIndexOf; consumo total de tempo: "+allString+"ms");System.out.println( vezes+" vezes KMPIndexOf; tempo total gasto: "+allKMP+"ms");System.out.println(times+"allbuild= "+allbuild+"ms");System.out.println(times+"alltoArray= "+alltoArray+"ms");System.out.println( times+"*3 vezes, GC; tempo total gasto: "+allGC+"ms");long end = System.currentTimeMillis();long allTime = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(times+" times, todo o consumo de tempo total: "+(allTime)+"ms; loss:" + lossTime +" ms; Taxa de perda: " +((0.0+lossTime)/allTime * 100)+"%");System.out.println("------------------- -------");}//// Construir caracteres 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;//semente longa = System.nanoTime();Aleatório aleatório = novo Random(seed);////StringBuilder construtor = new StringBuilder();for (int i = 0; i < len; i++) {//int type = random.nextInt(3);// 0-2int cvalue = 0;if(TYPE_NUMBER == tipo){cvalue = '0' + random.nextInt(10);// 0~(n-1)} else if(TYPE_LOWERCASE == tipo){cvalue = 'a' + random.nextInt(26);// 0~(n-1)} else if(TYPE_UPPERCASE == tipo){cvalue = 'A' + random.nextInt( 26);// 0~(n-1)} else {lançar novo RuntimeException(Random.class.getName()+"#newxtInt(int);Errado!");}////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();}/** * Método próprio do Java, implementado internamente * @param all * @param sub * @return */public static int stringIndexOf(String all, String sub){// Programação defensiva if(null == all || null== sub){return -1;}//Chamar o método String do Java return all.indexOf(sub);}/** * Algoritmo BF* @param all * @param sub * @return */public static int bfIndexOf(String all, String sub) { // Programação defensiva if(null == all || null== sub){return -1;}//int lenAll = all.length();int lenSub = sub.length();int i = 0;while (i < lenAll) {// Compare int começando em i subscrito j = 0;while (j < lenSub) {//char all_i = all.charAt(i);char sub_j = sub.charAt(j) ; if(all_i == sub_j){// Se for igual, continue a comparar o próximo caractere i++;j++; // Este aumento é muito importante} else {// Caso contrário, salte do loop interno break;}}// If j Se for igual a lenSub, a correspondência será bem-sucedida if (lenSub == j){return i - lenSub;} else {i = 1+i - j; // Backtrack i}}//return -1;} /** * Algoritmo 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);} /** * Obtenha o próximo valor da função da string* * @param t * String* @return próximo valor da função*/ public static int[] próximo(char[] t) { int[] próximo = new int[t.length] próximo[0] = -1; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; next[i] = j; else { next[i] = next[j] } else { j = next[j] } return next } /** * KMP correspondente string* * @param allArray * String principal * @param subArray * String padrão * @return Se a correspondência for bem-sucedida, retorne o subscrito, caso contrário, retorne -1 */ public static int KMP_Index(char[] allArray, char[] subArray) { int[] next = next (subArray ); int i = 0; int j = 0 enquanto (i <= allArray.length - 1 && j <= subArray.length - 1) { if (j == -1 || allArray[i] == subArray[j]) { i++ } else { j = next[j] } if (j < subArray.length) { return -1; i - subArray.length; // Retorna o índice principal da string padrão na string principal} }Um resultado do teste é mostrado abaixo:
--------------------------10 vezes bfIndexOf= 94ms10 vezes stringIndexOf= 56ms10 vezes KMPIndexOf= 76ms10 vezes allbuild= 5870ms10 vezes alltoArray= 137ms10*3 vezes ,GC= 155ms10 vezes, tempo total gasto: 6388ms perda: 6007ms; 94.03569192235442% -----------------------------30 vezes bfIndexOf= 365ms30 vezes stringIndexOf= 222ms30 vezes KMPIndexOf= 295ms30 vezes allbuild= 16452ms30 vezes alltoArray = 395ms30* 3 vezes, GC= 452ms30 vezes, tempo total gasto: 18184ms; Perda: 16850ms; Taxa de perda: 92,66388033435987%--------------------------50 vezes bfIndexOf; : 335ms50 vezes KMPIndexOf; tempo total gasto: 450ms50 vezes allbuild= 26501ms50 vezes alltoArray= 637ms50*3 vezes, GC; consumo total de tempo: 734ms50 vezes, consumo total de tempo: 29211ms; taxa de perda: 92,91705179555647%-------------------- - -----
Pode-se ver a partir disso que usando StringBuilder para construir uma string, 8 milhões * 50 acréscimos consomem aproximadamente 26 segundos. Isso se traduz em 16 milhões de vezes por segundo. . .
Parece que precisamos escrever uma função de temporização especial. Originalmente, o Junit tinha suas próprias estatísticas, mas as amostras não eram fáceis de fazer.
Deste ponto de vista, a preparação dos dados, ou seja, a seleção dos casos de teste, é crítica e pode precisar ser gerada e gravada primeiro em um arquivo de texto.