Wenn ich mir den KMP-Algorithmus ansehe, möchte ich einfach die Ausführungszeit und Leistung zählen.
Die Schlussfolgerung lautet: Die String-IndexOf-Methode von Java hat die beste Leistung, gefolgt vom KMP-Algorithmus, gefolgt vom traditionellen BF-Algorithmus. Natürlich ist der Vergleich etwas weit hergeholt. Der SUN-Algorithmus ist auch in Java implementiert. Es sieht nicht danach aus. KMP muss im Detail untersucht werden.
Der Testcode sieht so aus:
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. Der Verlust beim Erstellen eines Strings long buildStart = System.currentTimeMillis();String sub = buildString(subLen, cl);String all = buildString(allLen, sub) +sub;long buildEnd = System .currentTimeMillis();allbuild += (buildEnd - buildStart);// 2. Der Verlust von 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+";Zeitaufwändig: "+timeoutBF+" ms");//System.out.println("indexString="+indexString+";Zeitaufwändig: "+timeoutString+"ms");if(indexBF == indexString && indexKMP == indexString){//System.out.println("!!!!Kontrast gleich. ");} else {throw new RuntimeException("Vergleichsfehler.");}//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 times,GC= "+allGC+"ms");long end = System.currentTimeMillis();long allTime = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(i+" mal, alle Gesamtzeitverbrauch: "+(allTime)+"ms; Verlust:" + lossTime +"ms; Verlustverhältnis: " +( (0,0+lossTime)/allTime * 100)+"%");System.out.println("--------------------------");}}//System. out.println(times+"times bfIndexOf; Gesamtzeitverbrauch: "+allBF+"ms");System.out.println(times+"times stringIndexOf; Gesamtzeitverbrauch: "+allString+"ms");System.out.println( mal+" mal KMPIndexOf; insgesamt aufgewendete Zeit: "+allKMP+"ms");System.out.println(times+"allbuild= "+allbuild+"ms");System.out.println(times+"alltoArray= "+alltoArray+"ms");System.out. println( times+"*3 times, GC; insgesamt aufgewendete Zeit: "+allGC+"ms");long end = System.currentTimeMillis();long allTime = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(times+" mal, alle Gesamtzeitverbrauch: "+(allTime)+"ms; loss:" + lossTime +" ms; Verlustverhältnis: " +((0.0+lossTime)/allTime * 100)+"%");System.out.println("------------------- -------");}//// Zeichen erstellen 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 seeds = System.nanoTime();Random random = 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 == 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();}/** * Javas eigene Methode, intern implementiert * @param all * @param sub * @return */public static int stringIndexOf(String all, String sub){// Defensive Programmierung if(null == all || null== sub){return -1;}//Java-String-Methode aufrufen return all.indexOf(sub);}/** * BF-Algorithmus* @param all * @param sub * @return */public static int bfIndexOf(String all, String sub) { // Defensive Programmierung if(null == all || null== sub){return -1;}//int lenAll = all.length();int lenSub = sub.length();int i = 0;while (i < lenAll) {// Vergleiche int beginnend mit i subscript j = 0;while (j < lenSub) {//char all_i = all.charAt(i);char sub_j = sub.charAt(j) ; if(all_i == sub_j){// Wenn gleich, fahren Sie mit dem Vergleich des nächsten Zeichens fort i++;j++ // Diese Erhöhung ist sehr wichtig} else {// Andernfalls springen Sie aus der inneren Schleife break;}}// If J Wenn es gleich lenSub wird, ist die Übereinstimmung erfolgreich if (lenSub == j){return i - lenSub;} else {i = 1+i - j; // Backtrack i}}//return -1;} /** * KMP-Algorithmus * @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);} /** * Den nächsten Funktionswert des Strings abrufen* * @param t * String* @return next function value*/ public static int[] next(char[] t) { int[] next = new int[t.length] = -1; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; next[i] = j; } else { next[i] = next[j] } } return next; Hauptzeichenfolge * @param subArray * Musterzeichenfolge * @return Wenn die Übereinstimmung erfolgreich ist, geben Sie den Index zurück, andernfalls geben Sie -1 zurück */ 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++ } if (j < subArray.length) { return -1; i - subArray.length; // Den Kopfindex der Musterzeichenfolge in der Hauptzeichenfolge zurückgeben} }Ein Ergebnis des Tests ist unten dargestellt:
--------------------------10-mal bfIndexOf= 94ms10-mal stringIndexOf= 56ms10-mal KMPIndexOf= 76ms10-mal allbuild= 5870ms10-mal alltoArray= 137ms10*3-mal ,GC= 155ms10 mal, Gesamtzeit: 6388ms; Verlustverhältnis: 6007ms; 94.03569192235442%--------------30 mal bfIndexOf= 365ms30 mal stringIndexOf= 222ms30 mal KMPIndexOf= 295ms30 mal allbuild= 16452ms30 mal alltoArray = 395 ms30* 3-mal, GC= 452 ms30-mal, Gesamtzeit: 18184 ms; Verlust: 16850 ms; Verlustverhältnis: 92,66388033435987 % ---------- 50 mal bfIndexOf; : 335 ms50-mal KMPIndexOf; Gesamtzeit: 450 ms50-mal allbuild= 26501 ms50-mal alltoArray= 637 ms50*3-mal, GC; Gesamtzeitverbrauch: 29211 ms; Verlustverhältnis: 92,91705179555647 %; -----
Daraus ist ersichtlich, dass bei Verwendung von StringBuilder zum Erstellen einer Zeichenfolge 8 Millionen * 50 Anhänge etwa 26 Sekunden verbrauchen. Das entspricht 16 Millionen Mal pro Sekunde. . .
Es scheint, dass wir eine spezielle Timing-Funktion schreiben müssen. Ursprünglich hatte Junit seine eigenen Statistiken, aber die Beispiele waren nicht einfach zu erstellen.
Unter diesem Gesichtspunkt ist die Datenvorbereitung, also die Auswahl der Testfälle, von entscheidender Bedeutung und muss möglicherweise zuerst generiert und in eine Textdatei geschrieben werden.