Tests de performances StringBuilder en Java

Lorsque je regarde l'algorithme KMP, je veux simplement compter le temps d'exécution et les performances.

La conclusion est la suivante : la méthode String indexOf de Java a les meilleures performances, suivie de l'algorithme KMP, suivi de l'algorithme BF traditionnel. Bien sûr, la comparaison est un peu tirée par les cheveux. L'algorithme de SUN est également implémenté en Java, et ce n'est pas le cas. Cela ne ressemble pas à cela. KMP doit être étudié en détail.

Le code du test ressemble à ceci :

 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. La perte de la construction d'une chaîne long buildStart = System.currentTimeMillis();String sub = buildString(subLen, cl);String all = buildString(allLen, sub) +sub;long buildEnd = Système .currentTimeMillis();allbuild += (buildEnd - buildStart);// 2. La perte 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 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+";Prend du temps : "+timeoutBF+" ms");//System.out.println("indexString="+indexString+";Prend du temps : "+timeoutString+"ms");if(indexBF == indexString && indexKMP == indexString){//System.out.println("!!!!Contraste égal. ");} else {throw new RuntimeException("Erreur de comparaison.");}//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 fois,GC= "+allGC+"ms");long end = System.currentTimeMillis();long allTime = fin-début;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(i+" fois, tout le temps total : "+(allTime)+"ms; perte:" + lossTime +"ms; taux de perte : " +( (0,0+lossTime)/allTime * 100)+"%");System.out.println("--------------------------");}}//System. out.println(times+"times bfIndexOf; consommation de temps totale : "+allBF+"ms");System.out.println(times+"times stringIndexOf; consommation de temps totale : "+allString+"ms");System.out.println( times+" times KMPIndexOf ; temps total passé : "+allKMP+"ms");System.out.println(times+"allbuild= "+allbuild+"ms");System.out.println(times+"alltoArray= "+alltoArray+"ms");System.out.println( times+"*3 fois, GC ; temps total passé : "+allGC+"ms");long end = System.currentTimeMillis();long allTime = end-start;long lossTime = allTime - (allBF+allString+allKMP+allGC);System.out.println(times+" fois, toute la consommation de temps totale : "+(allTime)+"ms; loss:" + lossTime +" ms ; Taux de perte : " +((0.0+lossTime)/allTime * 100)+"%");System.out.println("---------------------------------- -------");}//// Caractères de construction 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;//graine longue = System.nanoTime();Random random = nouveau 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 {lancer un nouveau 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();}/** * Méthode propre à Java, implémentée en interne * @param all * @param sub * @return */public static int stringIndexOf(String all, String sub){// Programmation défensive if(null == all || null== sub){return -1;}//Appeler la méthode String de Java return all.indexOf(sub);}/** * Algorithme BF* @param all * @param sub * @return */public static int bfIndexOf(String all, String sub) { // Programmation défensive if(null == all || null== sub){return -1;}//int lenAll = all.length();int lenSub = sub.length();int i = 0; while (i < lenAll) {// Comparez int à partir de i indice j = 0; while (j < lenSub) {//char all_i = all.charAt(i);char sub_j = sub.charAt(j) ; if(all_i == sub_j){// Si égal, continuez à comparer le caractère suivant i++;j++; // Cette augmentation est très importante} else {// Sinon, sortez de la boucle interne break;}}// If j S'il devient égal à lenSub, la correspondance est réussie if (lenSub == j){return i - lenSub;} else {i = 1+i - j; // Backtrack i}}//return -1;} /** * Algorithme 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);} /** * Obtenir la valeur de fonction suivante de la chaîne* * @param t * String* @return valeur de fonction suivante*/ public static int[] next(char[] t) { int[] next = new int[t.length] ; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; j++; next[i] = j; } else { next[i] = next[j]; } } else { j = next[j] } } return next; Chaîne principale * @param subArray * Chaîne de modèle * @return Si la correspondance réussit, renvoie l'indice, sinon renvoie -1 */ public static int KMP_Index(char[] allArray, char[] subArray) { int[] next = next (sous-Array ); int i = 0; int j = 0; tandis que (i <= allArray.length - 1 && j <= subArray.length - 1) { if (j == -1 || allArray[i] == subArray[j]) { i++; j++; else { j = next[j] } } if (j < subArray.length) { return -1 } else return i - subArray.length; // Renvoie l'index de tête de la chaîne de modèle dans la chaîne principale} }

Un résultat du test est présenté ci-dessous :

 ------------------------------------10 fois bfIndexOf= 94 ms10 fois stringIndexOf= 56 ms10 fois KMPIndexOf= 76 ms10 fois allbuild= 5870 ms10 fois alltoArray= 137 ms10*3 fois ,GC= 155 ms10 fois, temps total pris : 6388 ms ; perte : 6007 ms ; 94,03569192235442%---------------------------------------30 fois bfIndexOf= 365 ms30 fois stringIndexOf= 222 ms30 fois KMPIndexOf= 295 ms30 fois allbuild= 16452 ms30 fois alltoArray = 395 ms30* 3 fois, GC= 452 ms30 fois, temps total pris : 18 184 ms ; Perte : 16 850 ms ; Taux de perte : 92,66388033435987 %-------------------------50 fois bfIndexOf ; consommation de temps totale : 550 ms50 fois stringIndexOf ; : 335 ms50 fois KMPIndexOf ; temps total pris : 450 ms50 fois allbuild= 26 501 ms50 fois alltoArray= 637 ms50*3 fois, GC ; consommation de temps totale : 734 ms50 fois, consommation de temps totale : 29 211 ms ; taux de perte : 27 142 ms ; -----

On peut voir ici qu'en utilisant StringBuilder pour construire une chaîne, 8 millions * 50 ajouts consomment environ 26 secondes. Cela se traduit par 16 millions de fois par seconde. . .
Il semble que nous devions écrire une fonction de timing spéciale. À l'origine, Junit avait ses propres statistiques, mais les échantillons n'étaient pas faciles à réaliser.

De ce point de vue, la préparation des données, c'est-à-dire la sélection des cas de test, est essentielle et peut devoir être générée et écrite au préalable dans un fichier texte.