عند النظر إلى خوارزمية KMP، أريد ببساطة حساب وقت التنفيذ والأداء.
الاستنتاج هو: تتميز طريقة String IndexOf الخاصة بـ Java بأفضل أداء، تليها خوارزمية KMP، تليها خوارزمية BF التقليدية. بالطبع، المقارنة بعيدة المنال بعض الشيء، حيث تم تطبيق خوارزمية SUN أيضًا في Java. لا يبدو الأمر كذلك. KMP يحتاج إلى دراسة تفصيلية.
يبدو رمز الاختبار كما يلي:
الحزمة 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;بداية طويلة = 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 = النظام .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.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");نهاية طويلة = System.currentTimeMillis();long allTime = نهاية البداية;long LossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(i+" مرات، إجمالي الوقت المستغرق: "+(allTime)+"ms; Loss:" + LossTime +"ms; نسبة الخسارة: " +( (0.0+وقت الخسارة)/كل الوقت * 100)+"%");System.out.println("--------------------------");}}//System.out. 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( 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;// بذرة طويلة = System.nanoTime();عشوائي عشوائي = جديد 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 إذا (TYPE_LOWERCASE == نوع){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 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) {// قارن int بدءًا من i منخفض 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;}}// If ي إذا أصبحت مساوية لـ 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; 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* * @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++; } else { j = next[j] } } if (j < subArray.length) { return -1 ; i - subArray.length; // إرجاع فهرس رأس سلسلة النمط في السلسلة الرئيسية} }تظهر إحدى نتائج الاختبار أدناه:
-------------------------- 10 مرات bfIndexOf = 94 مللي ثانية 10 مرات stringIndexOf = 56 مللي ثانية 10 مرات KMPIndexOf = 76 مللي ثانية 10 مرات allbuild = 5870 مللي ثانية 10 مرات alltoArray = 137 مللي ثانية 10 * 3 مرات ، GC = 155 مللي ثانية 10 مرات، إجمالي الوقت المستغرق: 6388 مللي ثانية؛ الخسارة: 6007 مللي ثانية؛ 94.03569192235442%----------------------------------------- 30 مرة bfIndexOf= 365ms30 مرة stringIndexOf= 222ms30 مرة KMPIndexOf= 295ms30 مرة allbuild= 16452ms30 مرة alltoArray = 395 مللي ثانية30* 3 مرات، GC= 452 مللي ثانية30 مرة، إجمالي الوقت المستغرق: 18184 مللي ثانية؛ الخسارة: 16850 مللي ثانية نسبة الخسارة: 92.66388033435987%------------------------- 50 مرة bfIndexOf; : 335 مللي ثانية 50 مرة إجمالي الوقت المستغرق: 450 مللي ثانية 50 مرة allbuild = 26501 مللي ثانية 50 مرة alltoArray = 637 مللي ثانية 50 * 3 مرات ، إجمالي استهلاك الوقت: 734 مللي ثانية 50 مرة ، إجمالي استهلاك الوقت: 29211 مللي ثانية ؛ نسبة الخسارة: 92.91705179555647% -------------------- - -----
يمكن أن نرى من هذا أنه باستخدام StringBuilder لإنشاء سلسلة، فإن 8 ملايين * 50 ملحقة تستهلك حوالي 26 ثانية. وهذا يترجم إلى 16 مليون مرة في الثانية الواحدة. . .
يبدو أننا بحاجة إلى كتابة دالة توقيت خاصة، في الأصل، كان لدى Junit إحصائيات خاصة بها، ولكن لم يكن من السهل إنشاء العينات.
من وجهة النظر هذه، يعد إعداد البيانات، أي اختيار حالات الاختبار، أمرًا بالغ الأهمية، وقد يلزم إنشاءها وكتابتها في ملف نصي أولاً.