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 回 = 50;//testMatch(allLen, subLen, cl, 回);} public static void testMatch(int allLen, int subLen, String cl, int 回){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 < 回; 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();intindexBF = 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+損失時間)/全時間 * 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(回+"*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();ランダムランダム = new 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 == 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);間違っています!");}////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 を比較します subscript 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 {// それ以外の場合は、内部ループの中断から抜け出します。}}// 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;メイン文字列 * @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++; } if (j < subArray.length) { return -1; i - subArray.length; // メイン文字列内のパターン文字列の先頭インデックスを返します。テストの結果の 1 つを以下に示します。
------------------------10 回 bfIndexOf= 94ms 10 回 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 倍; stringIndexOf の 50 倍; : 335ms50 回 KMPIndexOf; 合計所要時間: 450ms50 回 allbuild= 26501ms50 回 alltoArray= 637ms50*3 回、GC 合計時間: 734ms50 回、損失: 27142ms、損失率: 92.91705179555647% ------ -----
このことから、StringBuilder を使用して文字列を構築すると、800 万 * 50 回の追加に約 26 秒かかることがわかります。これは 1 秒あたり 1,600 万回に相当します。 。 。
特別なタイミング関数を記述する必要があるようですが、もともと Junit には独自の統計情報がありましたが、サンプルを作成するのは簡単ではありませんでした。
この観点から、データの準備、つまりテスト ケースの選択が重要であり、最初にデータを生成してテキスト ファイルに書き込む必要がある場合があります。