5

我想知道哪个程序变体更好的运行时？
这两种变体看起来都很容易实现。但是什么更好用，在哪些情况下更好用？

字符串反转：

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

StringBuilder 反向：

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();
}
4

4 回答 4

6

在你的两种情况下：我更喜欢第二种

因为编译器会将第一个转换为 ：

rev += s.charAt(i);

至 ：

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

但是，看看最坏的情况：

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+="*";
    }
}

输出将是：

slow elapsed 173 ms
fast elapsed 1 ms
于 2013-04-14T08:17:54.250 回答
5

考虑到您可以这样做，两者都不是很好：

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

如果您必须使用上述其中一个，那么选择 StringBuilder 反向 - 使用第一个，您可以通过屋顶发送 GC，创建和处置尽可能多的字符串对象，就像您拥有的字符一样。

于 2013-04-14T07:52:23.873 回答
0

Stringjava中的class是不可变的，一生都无法改变，两个字符串的连接create newString和return，但是StringBuilder是一个可变的字符序列，可以改变内存中字符串的字符，使用StringBuilder应该更好。
作为另一种解决方案，您可以将字符串转换为 char 数组和反向数组，最后转换为 String 

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);

有关更多信息，请参阅 javadoc： StringBuilder、String
和查看StringBuilder类源代码以了解想要真正发生在附加字符上

于 2013-04-14T08:10:05.307 回答
0

一些有趣的细节。
我们可以编写一个递归函数来反转字符串并且不使用任何循环。使用字符串方法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);
}

这种方法效率如何？
该方法具有线性运行时间。

于 2013-04-17T16:18:20.643 回答