2011-10-25 19 views
1

次のうちどれが文字列の単語を逆にする効率的な方法ですか?どのコードがより効率的ですか?

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

OR

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, "");} 

最初の方法は、より読みやすく、まっすぐ進むと思われる一方で、その内の2つのループがあります。 2番目の方法では、私はtail-recursiveな方法でそれをやってみました。しかし、javaがtail-recursiveコードを最適化するかどうかはわかりません。

+1

ベストプラクティスを見つけるには、コードをプロファイリングしてより速く実行する方法があります。 – NickLH

+0

http://stackoverflow.com/questions/771092/is-method-a-faster-than-method-b – paxdiablo

+0

'StringTokenizer'は推奨されていませんが、* StringTokenizerは互換性の理由から保持されるレガシークラスです新しいコードではその使用は推奨されません。この機能を探している人は、splitメソッド(Stringまたはjava.util.regexパッケージ)を使用することをお勧めします。*(java docsから) –

答えて

2

あなたは現在のJavadocを読んでいる場合はStringTokenizerは非推奨ではなく、ただ一つのループ

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--} 
} 
2

しかし、私がtail-recursiveコードを最適化するかどうかはわかりません。

これはありません。ジョン・ローズ@オラクルによって


これは速く、他のよりも一つの解決策になるかどうか、私は知りません。

しかし、Javaがテールコール最適化を実装していないということは、第2の解決策がスタック領域を使い果たす可能性があることを意味しますあなたが大きな(十分な)数の単語を含む文字列を与えるならば。あなたはこれを実装するために、より多くのスペース効率的な方法を探している場合


最後に、ちょうどStringBuilder使用する巧妙な方法があります。

  1. あなたの入力からString
  2. StringBuilderを作成reverse()を使用してStringBuilder内の文字を逆にします。
  3. StringBuilderを実行し、各単語の開始オフセットと終了オフセットを特定します。各開始/終了オフセット対について、オフセット間の文字を反転させる。 (ループを使用してこれを行う必要があります)
  4. StringStringBuilderを戻します。
+0

だから、2番目の解が危険なのであれば、私は を参照して、正確に再帰の使用は何ですか?スタックオーバーフローを引き起こすように、再帰的メソッドへの入力が特定の制限を超えないことが確実である場合にのみ有効ですか? Javaでプログラミングしている場合には、再帰呼び出しをtail-recursiveにしても意味がありませんか?tail再帰は関数型言語に対してのみ役に立ちますか...ありがとう – comatose

+0

Javaで再帰を使用する場合、しかし、それはまったく使用すべきではありません。たとえば、入力データ構造のサイズ/形状が再帰の量に妥当な範囲を設定していることが事前に分かっている場合は、それだけで問題ありません。将来のJava実装では、テールコールの最適化が組み込まれる可能性もあります。しかし、はい、あなたのコードをtail-recursiveに変換しても、現世代のJavaではパフォーマンスは向上しません。 –

0

あなたは結果

例えば大量にそれらの両方のタイミングで結果をテストすることができます。 100000000文字列を逆にして、何秒かかるかを確認します。開始と終了システムのタイムスタンプを比較して、2つの機能の正確な違いを得ることもできます。

0

でこれを行うことができます...

StringTokenizerは、互換性のために保持されているレガシークラスですが、新しいコードでの使用は推奨されません。この機能を求めている人は、Stringのsplitメソッドまたはjava.util.regexパッケージを代わりに使用することをお勧めします。

String[] strArray = str.split(" "); 
StringBuilder sb = new StringBuilder(); 
for (int i = strArray.length() - 1; i >= 0; i--) 
    sb.append(strArray[i]).append(" "); 

String reversedWords = sb.substring(0, sb.length -1) // strip trailing space 
関連する問題