哪种代码效率更高？

Question

以下哪一项是颠倒字符串中单词的有效方法？

public String Reverse(StringTokenizer st){
    String[] words = new String[st.countTokens()];
    int i = 0;
    while(st.hasMoreTokens()){
       words[i] = st.nextToken();i++}

    for(int j = words.length-1;j--)
       output = words[j]+" ";}

或

public String Reverse(StringTokenizer st, String output){        
    if(!st.hasMoreTokens()) return output;        
        output = st.nextToken()+" "+output;
        return Reverse(st, output);}       

public String ReverseMain(StringTokenizer st){       
    return Reverse(st, "");}

虽然第一种方法看起来更具可读性和直截了当，但它有两个循环。在第二种方法中，我尝试了尾递归的方式。但是我不确定java是否优化了尾递归代码。

Answer 1

您只需一次循环即可完成此操作

public String Reverse(StringTokenizer st){
    int length = st.countTokens();
    String[] words = new String[length];
    int i = length - 1;
    while(i >= 0){
      words[i] = st.nextToken();i--}
}

Answer 2

，但我不确定java是否优化了尾递归代码。

至少Sun/Oracle Java实现不支持Java 7，包括Java 7在内。

参考文献：

• "Tail calls in the VM" by John Rose @ Oracle.
• Bug 4726340 - RFE: Tail Call Optimization

我不知道这是否会使一种解决方案比另一种更快。(自己测试一下...注意避免标准的微观基准测试陷阱。)

然而，Java没有实现尾部调用优化的事实意味着，如果给第二个解决方案提供一个包含大量(足够)单词的字符串，它很容易耗尽堆栈空间。

最后，如果您正在寻找一种更节省空间的方法来实现这一点，有一种仅使用StringBuilder的聪明方法。

使用reverse().

• Step String

• Reverse

1. 从您的输入到StringBuilder中的字符创建一个，标识每个单词的开始和结束偏移量。对于每个开始/结束偏移对，反转偏移之间的字符。(您必须使用循环来完成此操作。)
2. 将StringBuilder转换回String.

Answer 3

您可以通过对大量结果进行计时来测试结果

例如：你颠倒了100000000个字符串，看看需要多少秒。您还可以比较开始和结束系统时间戳，以获得两个函数之间的确切差异。