Welche Varianten String Reverse sind besser?

Question

Ich frage mich zu wissen, welche Programmvariante bessere Laufzeit sind?
Beide Varianten sieht einfach zu implementieren. Aber was ist besser zu verwenden und in welchen Fällen?

String umkehren:

public static String reverse(String s) 
{ 
    String rev = ""; 
    for (int i = s.length() - 1; i >= 0; i--) 
     rev += s.charAt(i); 
    return rev; 
} 

String umkehren:

public static String reverse(String s) 
{ 
    StringBuilder rev = new StringBuilder(); 
    for (int i = s.length() - 1; i >= 0; i--) 
     rev.append(s.charAt(i)); 
    return rev.toString(); 
} 

Answer 1

in Ihren beiden Fällen anhängt: ziehe ich es das zweite

weil die compiler will convert the first one from:

rev += s.charAt(i);

zu:

(new StringBuilder()).append(rev).append(s.charAt(i)).toString();

Aber see the worst case scenario:

public class Main 
{ 
    public static void main(String[] args) 
    { 
     long now = System.currentTimeMillis(); 
     slow(); 
     System.out.println("slow elapsed " + (System.currentTimeMillis() - now) + " ms"); 

     now = System.currentTimeMillis(); 
     fast(); 
     System.out.println("fast elapsed " + (System.currentTimeMillis() - now) + " ms"); 
    } 

    private static void fast() 
    { 
     StringBuilder s = new StringBuilder(); 
     for(int i=0;i<100000;i++) 
      s.append("*");  
    } 

    private static void slow() 
    { 
     String s = ""; 
     for(int i=0;i<100000;i++) 
      s+="*"; 
    } 
} 

der Ausgang sein:

slow elapsed 173 ms 
fast elapsed 1 ms 

Answer 2

Weder ist wirklich toll bedenkt, kann man einfach tun:

new StringBuilder(str).reverse().toString(); 

Wenn Sie musste eine der oben genannten obwohl, dann wählen Sie die StringBuilder Reverse - mit der ersten könnte Sie die GC durch das Dach zu schaffen und zu entsorgen so viele String-Objekte wie Sie Zeichen haben.

Answer 3

String Klasse in Java ist unveränderlich und kann nicht in seinem Leben ändern, und Verkettung von zwei String erstellen neue String und zurück, aber StringBuilder ist ein veränderliches Folge von Zeichen, die Zeichen der Zeichenfolge im Speicher ändern kann, und mit StringBuilder sollte besser sein.
als eine andere Lösung, können Sie konvertieren String-Array verkohlen und Array umkehren und schließlich in String konvertieren

char[] arr = s.toCharArray(); 
char tmp; 
int maxIndex = arr.length-1; 
for(int i = arr.length>>2; i>=0;i--) { 
    tmp = arr[i]; 
    arr[i] = arr[maxIndex-i]; 
    arr[maxIndex-i] = tmp; 
} 
return new String(arr); 

für weitere Informationen siehe javadoc: StringBuilder, String
und schauen StringBuilder Klasse Quellcodes wollen zu verstehen, ist wirklich passieren auf ein Zeichen

Answer 4

Einige interessante Details.
Wir können eine rekursive Funktion schreiben, um eine Zeichenfolge umzukehren und keine Schleifen zu verwenden. Verwenden Sie die String-Methode substring():

public static String reverse(String s) { 
    int N = s.length(); 
    if (N <= 1) return s; 
    String a = s.substring(0, N/2); 
    String b = s.substring(N/2, N); 
    return reverse(b) + reverse(a); 
} 

Wie effizient ist diese Methode?
Diese Methode hat eine linearithmische Laufzeit.