9

F＃2.0がVS2010の一部になっているので、私はF＃に興味を持っています。それを使う意味は何だろうと思いました。少し読んで、関数呼び出しを測定するためのベンチマークを作成しました。私はアッカーマン関数を使用しました:)

C＃

sealed class Program
{
    public static int ackermann(int m, int n)
    {
        if (m == 0)
            return n + 1;
        if (m > 0 && n == 0)
        {
            return ackermann(m - 1, 1);
        }
        if (m > 0 && n > 0)
        {
            return ackermann(m - 1, ackermann(m, n - 1));
        }
        return 0;
    }

    static void Main(string[] args)
    {

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();
        Console.WriteLine("C# ackermann(3,10) = " + Program.ackermann(3, 10));
        stopWatch.Stop();

        Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");
        Console.ReadLine();
    }
}

C ++

class Program{
public:
static inline int ackermann(int m, int n)
{
  if(m == 0)
       return n + 1;
  if (m > 0 && n == 0)
  {
      return ackermann(m - 1, 1);
  }
  if (m > 0 && n > 0)
  {
      return ackermann(m - 1, ackermann(m, n - 1));
  }
  return 0;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 clock_t start, end;

  start = clock();
 std::cout << "CPP: ackermann(3,10) = " << Program::ackermann(3, 10) << std::endl;
 end = clock();
 std::cout << "Time required for execution: " << (end-start) << " ms." << "\n\n";
 int i;
 std::cin >> i;
 return 0;
}

F＃

// Ackermann
let rec ackermann m n  =
  if m = 0 then n + 1
  elif m > 0 && n = 0 then ackermann (m - 1) 1
  elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
  else 0

open System.Diagnostics;
let stopWatch = Stopwatch.StartNew()
let x = ackermann 3 10 
stopWatch.Stop();

printfn "F# ackermann(3,10) = %d"  x
printfn "Time required for execution: %f"  stopWatch.Elapsed.TotalMilliseconds

Java

public class Main 
{
 public static int ackermann(int m, int n)
 {
 if (m==0) 
   return n + 1;
if (m>0 && n==0)
{
 return ackermann(m - 1,1);
}
if (m>0 && n>0)
{
  return ackermann(m - 1,ackermann(m,n - 1));
 }
 return 0;
}

  public static void main(String[] args)
  { 
   System.out.println(Main.ackermann(3,10));
  }
}

その後、
C＃= 510ms
c ++ = 130ms
F＃= 185ms
Java = Stackoverflow :)

.Netを使用して実行を少し速くしたい場合、それはF＃の力ですか（少量のコードを除く）？これらのコード（特にF＃）のいずれかを最適化できますか？

更新。Console.WriteLineを削除し、デバッガーなしでC＃コードを実行しました：C＃= 400ms

4

4 に答える 4

14

この場合、C＃とF＃の違いは、末尾呼び出しの最適化のおかげだと思います。

末尾呼び出しとは、関数の「最後のこと」として実行される再帰呼び出しがある場合です。この場合、F＃は実際には呼び出し命令を生成しませんが、代わりにコードをループにコンパイルします（呼び出しは「最後のもの」であるため、現在のスタックフレームを再利用して、メソッドの先頭にジャンプできます） 。

の実装ではackermann、2つの呼び出しが末尾呼び出しであり、そのうちの1つだけが末尾呼び出しではありません（結果が引数として別のackermann呼び出しに渡されるもの）。これは、F＃バージョンが実際に「呼び出し」命令を呼び出す頻度が（はるかに？）少ないことを意味します。

一般に、パフォーマンスプロファイルはC＃のパフォーマンスプロファイルとほぼ同じです。ここには、F＃とC＃のパフォーマンスに関連する投稿がかなりあります。

于 2010-07-13T22:20:18.863 に答える
6

これは、関数呼び出しを減らすための一般的な方法であるため、一種の関数呼び出しに関連しています。

このタイプの再帰関数は、メモ化（キャッシング）によって高速化できます。これはC＃でも実行できます（例）。18ミリ秒かかりました。

open System.Collections.Generic

let memoize2 f =
    let cache = Dictionary<_, _>()
    fun x y ->
        if cache.ContainsKey (x, y) then 
            cache.[(x, y)]
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// Ackermann
let rec ackermann =
    memoize2 (fun m n ->
        if m = 0 then n + 1
        elif m > 0 && n = 0 then ackermann (m - 1) 1
        elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
        else 0
    )
于 2010-07-14T00:21:30.170 に答える
4

質問に直接関係していませんが、言及するのに十分興味深いです：このバージョンを試してください

let rec ackermann2 m n  =
  match m,n with
  | 0,0 -> 0
  | 0,n -> n+1
  | m,0 -> ackermann2 (m-1) 1
  | m,n -> ackermann2 (m-1) (ackermann2 m (n-1))

私のPC（VS2010、F＃インタラクティブ）では、ackermann 3 12を計算するときに、バージョンよりもほぼ50％高速です。

なぜこのようなパフォーマンスの違いがあるのか​​、はっきりとは説明できません。これは、F＃コンパイラがmatch式を一連のifステートメントではなくswitchステートメントに変換することと関係があると思います。（m = 0、n = 0）テストを最初に置くことも助けになったかもしれません。

于 2010-07-14T07:22:02.050 に答える
1

F＃の場合は、インラインキーワードを試してみてください。

また、前のポスターで述べたように、C＃とF＃のバージョンは、Console.WriteLineステートメントのために異なります。

于 2010-07-13T22:37:40.850 に答える