เมื่อดูอัลกอริธึม KMP ฉันต้องการเพียงแค่นับเวลาดำเนินการและประสิทธิภาพ
ข้อสรุปคือ: วิธี String IndexOf ของ Java มีประสิทธิภาพดีที่สุด ตามด้วยอัลกอริธึม KMP ตามด้วยอัลกอริธึม BF แบบดั้งเดิม แน่นอนว่าอัลกอริธึมของ SUN นั้นยังถูกนำไปใช้ใน Java ด้วยเช่นกัน ดูไม่เหมือนเลย ต้องศึกษา KMP อย่างละเอียด
รหัสทดสอบมีลักษณะดังนี้:
แพ็คเกจ com.test.test.kmp; นำเข้า java.util.Random; คลาสสาธารณะ KMPTest { โมฆะคงที่สาธารณะ main (String [] args) {ทดสอบ ();} // การทดสอบโมฆะคงที่สาธารณะ () {//int allLen = 8000000;int subLen = 11;int charLen = 4;String cl = buildString(charLen);int ครั้ง = 50;//testMatch (allLen, subLen, cl, ครั้ง);} โมฆะสาธารณะ 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("---------------------------");สำหรับ (int i = 0; i < ครั้ง; 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 (ทั้งหมด, ย่อย); ปลายยาว BF = System.currentTimeMillis (); // หมดเวลานาน BF = endBF - startBF; allBF += หมดเวลา BF; 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(ทั้งหมด, ย่อย);int indexKMP = KMP_Index(allArray, subArray);ปลายยาวKMP = System.currentTimeMillis();//การหมดเวลานานKMP = 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("!!!!Contrast เท่ากัน ");} else {throw new RuntimeException("Comparison error.");}//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 = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(i+" ครั้ง ใช้เวลาทั้งหมดทั้งหมด: "+(allTime)+"ms; loss:" + lossTime +"ms; อัตราการสูญเสีย: " +( (0.0+เวลาสูญเสีย)/ตลอดเวลา * 100)+"%");System.out.println("--------------------------");}}//System. 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");ปลายยาว = System.currentTimeMillis();เวลาทั้งหมดยาว = 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("------------------ -------");}////// สร้างอักขระสตริงคงที่สาธารณะ buildString (int len) {return buildString (len, null);} สตริงคงที่สาธารณะ buildString (int len, สตริงย่อย){//final int TYPE_NUMBER = 0;final int TYPE_LOWERCASE = 1;final int TYPE_UPPERCASE = 2;//เมล็ดยาว = System.nanoTime();สุ่มสุ่ม = ใหม่ สุ่ม (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)} อื่น ๆ ถ้า (TYPE_LOWERCASE == ประเภท) {cvalue = 'a' + Random.nextInt (26); // 0 ~ (n-1)} อื่น ๆ ถ้า (TYPE_UPPERCASE == ประเภท) {cvalue = 'A' + Random.nextInt ( 26);// 0~(n-1)} else {โยนใหม่ 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 == ทั้งหมด || null== sub) {return -1;}//เรียกเมธอด String ของ Java return all.indexOf(sub);}/** * อัลกอริทึม BF* @param all * @param sub * @return */public static int bfIndexOf(String all, String sub) { // การเขียนโปรแกรมป้องกันถ้า (null == ทั้งหมด || null== ย่อย) {return -1;}//int lenAll = all.length();int lenSub = sub.length();int i = 0; ในขณะที่ (i < lenAll) {// เปรียบเทียบ int โดยเริ่มจาก i ตัวห้อย j = 0; ในขณะที่ (j < lenSub) {//char all_i = all.charAt(i);char sub_j = sub.charAt(j) ; if(all_i == sub_j){// ถ้าเท่ากัน ให้เปรียบเทียบอักขระถัดไป i++;j++; // การเพิ่มขึ้นนี้สำคัญมาก} else {// มิฉะนั้น ให้กระโดดออกจากตัวแบ่งลูปด้านใน;}}// If เจ ถ้ามันเท่ากับ lenSub การจับคู่จะสำเร็จถ้า (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 int คงที่ [] ถัดไป (ถ่าน [] t) { int [] ถัดไป = ใหม่ int [t.length]; ถัดไป [0] = -1; int i = 0; ในขณะที่ (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; j++; if (t[i] != t[j]) { next[i] = j; } else { next[i] = next[j]; } else { j = next[j]; } กลับถัดไป; } /** * สตริงที่ตรงกันของ 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; ในขณะที่ (i <= allArray.length - 1 && j <= subArray.length - 1) { == -1 ||. allArray[i] == subArray[j]) { i++; j++; } else { j = ถัดไป [j]; } } ถ้า (j < subArray.length) { return -1; i - subArray.length; // กลับดัชนีส่วนหัวของสตริงรูปแบบในสตริงหลัก} }ผลลัพธ์หนึ่งของการทดสอบแสดงไว้ด้านล่าง:
-------------------------- 10 ครั้ง bfIndexOf= 94ms10 ครั้ง 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 เท่าของ bfIndexOf; การสิ้นเปลืองเวลาทั้งหมด: 550ms50 เท่าของ stringIndexOf; : 335ms50 เท่าของ KMPIndexOf; เวลาทั้งหมดที่ใช้: 450ms50 เท่าของ allbuild= 26501ms50 เท่าของ alltoArray= 637ms50*3 ครั้ง, GC; การบริโภคเวลาทั้งหมด: 734ms50 ครั้ง, การบริโภคเวลาทั้งหมด: 29211ms; การสูญเสีย: 27142ms; -----
จากสิ่งนี้จะเห็นได้ว่าการใช้ StringBuilder เพื่อสร้างสตริง 8 ล้าน * 50 ต่อท้ายใช้เวลาประมาณ 26 วินาที ซึ่งแปลเป็น 16 ล้านครั้งต่อวินาที - -
ดูเหมือนว่าเราจำเป็นต้องเขียนฟังก์ชันจับเวลาแบบพิเศษ เดิมที Junit มีสถิติเป็นของตัวเอง แต่การสร้างตัวอย่างนั้นไม่ใช่เรื่องง่าย
จากมุมมองนี้ การเตรียมข้อมูลซึ่งก็คือการเลือกกรณีทดสอบถือเป็นสิ่งสำคัญ และอาจจำเป็นต้องสร้างและเขียนลงในไฟล์ข้อความก่อน