2016-05-04 11 views
0

私はthis FizzBuzz exercise on CodingBatを行っていました。FizzBu​​zzを解決するための最もパフォーマンスに優しいアプローチ

文字列strが与えられた場合、文字列が "f"で始まる場合は "Fizz"を返します。文字列が "b"で終わる場合は "Buzz"を返します。 "f"と "b"の両方の条件が真であれば、 "FizzBu​​zz"を返します。それ以外の場合は、文字列をそのまま返します。

この回答が出ました。

public String fizzString(String str) 
{ 
    String sum = ""; 

    if (str.startsWith("f")) sum += "Fizz"; 
    if (str.endsWith("b")) sum += "Buzz"; 

    return (sum == "") ? str : sum; 
} 

ただし、問題の著者は行った。あまりにも冗長に思えた

public String fizzString(String str) 
{ 
    if (str.startsWith("f") && str.endsWith("b")) return "FizzBuzz"; 
    if (str.startsWith("f")) return "Fizz"; 
    if (str.endsWith("b")) return "Buzz"; 

    return str; 
} 

...

私はそれはむしろ、最初のプログラムのための第二を行くために、性能面現実世界の違いになるだろう、不思議でしたか?

+4

2番目の方が高速です。私はFizzBu​​zzのパフォーマンスが現実世界では重要だとは思わない。 – erickson

+0

現実世界では?おそらくそうではありません。厄介な世界では、どちらのアプローチともトレードオフがあります。最初のアプローチでは 'String'連結を使用しています。これは[notoriously slow](http://stackoverflow.com/q/1532461/758280)です。 2番目のアプローチでは、1番目のアプローチより多くの条件を使用します。 – Jeffrey

+0

解決法#2の最悪の場合、文字列連結は余分な条件チェックの価値がありません。ブール条件をチェックするよりもはるかに遅い文字列連結のために、より多くのメモリを割り当てる必要があるかもしれません。 –

答えて

0

私の計算は(コメントセクションがあまりにも混雑しました。)...そう言う

は、私は時間の設定量のためにできるだけ速く、コードのブロックを実行するJavaプログラムを持っている(1000ミリ秒) 。これは、平均、最小、および最大を得るためにこれを10回行う。

私は、最初の方法は平均して毎秒約400,000回のループが発生すると言います。ここで

は私の結果です:

First Method: 
Least loops: 26,312,768 
Most loops: 26,918,157 
Average loops: 26,582,653.7 

    Second Method: 
Least loops: 22,039,592 
Most loops: 22,596,476 
Average loops: 22,424,598.5 

ここで私が持っているソースコードです、私が得たデータが歪められているかもしれない方法を教えてください。私は自分のコンピュータが一定の負荷をかけていたので、コードを一定に保った。変更されたのは、whileループ内で呼び出されたものだけでした。

package personal; 
 

 
import java.util.ArrayList; 
 
import java.util.Arrays; 
 
import java.util.Collections; 
 
import java.util.List; 
 

 
public class SpeedTest { 
 

 
    public static void main(String[] args) { 
 
    int loops = 10; 
 
    double DELAY = 1000; 
 
    int i; 
 
    double[] loopCount = new double[loops + 1]; 
 
    double sum = 0; 
 
    for (i = 0; i < loops + 1; i++) { 
 

 
     long startTime = System.currentTimeMillis(); 
 
     long endTime = (long)(startTime + DELAY); 
 
     long index = 0; 
 

 
     while (true) { 
 
     fizzString("TEST"); 
 
     //fizzString2("TEST"); 
 
     long now = System.currentTimeMillis(); 
 
     if (now >= endTime) { 
 
      break; 
 
     } 
 
     index++; 
 
     } 
 

 
     if (i != 0) { 
 
     if (DELAY != 1000) { 
 
      if (DELAY/1000 % 1 == 0) { 
 
      System.out.printf("Test %.0f. %,.0f loops in %.0f seconds.\n", (float) i, (float) index, (float) DELAY/1000); 
 
      } else if ((DELAY/100) % 1 == 0) { 
 
      System.out.printf("Test %.0f. %,.0f loops in %.1f seconds.\n", (float) i, (float) index, (float) DELAY/1000); 
 
      } else if ((DELAY/10) % 1 == 0) { 
 
      System.out.printf("Test %.0f. %,.0f loops in %.2f seconds.\n", (float) i, (float) index, (float) DELAY/1000); 
 
      } else if (DELAY % 1 == 0) { 
 
      System.out.printf("Test %.0f. %,.0f loops in %.3f seconds.\n", (float) i, (float) index, (float) DELAY/1000); 
 
      } 
 
     } else { 
 
      System.out.printf("Test %.0f. %,.0f loops in %.0f second.\n", (float) i, (float) index, (float) DELAY/1000); 
 
     } 
 
     loopCount[i] = index; 
 
     } 
 
    } 
 
    Arrays.sort(loopCount); 
 
    System.out.printf("Least loops: %,.0f\n", (loopCount[1])); 
 
    System.out.printf("Most loops: %,.0f\n", loopCount[loops]); 
 

 
    for (int d = 1; d < loopCount.length; d++) { 
 
     sum += loopCount[d]; 
 
    } 
 
    double averageLoopCount = 1.0f * sum/(loopCount.length - 1); 
 
    System.out.printf("Average loops: %,.1f", averageLoopCount); 
 
    } 
 

 
    public static String fizzString(String str) { 
 
    if (str.startsWith("f") && str.endsWith("b")) return "FizzBuzz"; 
 
    if (str.startsWith("f")) return "Fizz"; 
 
    if (str.endsWith("b")) return "Buzz"; 
 

 
    return str; 
 
    } 
 

 
    public static String fizzString2(String str) { 
 
    String sum = ""; 
 

 
    if (str.startsWith("f")) sum += "Fizz"; 
 
    if (str.endsWith("b")) sum += "Buzz"; 
 

 
    return (sum == "") ? str : sum; 
 
    } 
 
}

自分のために試してみてください:)

+0

私はちょうど何度も何度もやり直しました、あなたが正しいです、それは速いです...私は理解していません、なぜ他の人はソリューション#2が一番速かったと言いましたか? – CaffeinatedSynapse

+0

@CoffeeAddict本当の理由:わかりません。私は言うことができます:*ここに "理論対実践"引用符を挿入する* – Kaelinator

+4

まず、このベンチマークは文字列としてTESTを使用します。これはfで始まらず、bで終わらないため。第2に、結果を無視し、ホットスポットがfizzbuzzへの呼び出しを完全に回避できるようにします。第3に、System.currentTimeMillis()を使用し、各繰り返しで呼び出すため、おそらくほとんどの時間が費やされます。 Javaでマイクロベンチマークを書くことは難しいです。 http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-javaを読んでください。 –

0

をこれは本当に、実行される実際のCPU命令に依存

が、一般的な考え方は、

    を持つことです
  • 実行された分岐の数が最も少ない(if-else)
  • 最小のメモリアクセス数
  • 動的割り当てなし。

このようなことは、提案されている解決策の両方よりも速くなければなりません。

public String fizzString(String str) 
{ 
    if (str.length() == 0) return str; 

    if (str.charAt(0) == 'f') { 
     if (str.charAt(str.length() - 1) == 'b') { 
      return "FizzBuzz"; 
     } 
     return "Fizz"; 
    } 
    if (str.charAt(str.length() - 1) == 'b') { 
     return "Buzz"; 
    } 
    return str; 
} 
関連する問題