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

爪哇

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，其中两个调用是尾调用，只有一个不是尾调用（结果作为参数传递给另一个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# 编译器将匹配表达式转换为 switch 语句而不是一系列 if 语句有关。首先进行 (m=0,n=0) 测试也可能有所帮助。

于 2010-07-14T07:22:02.050 回答
1

对于 F#，您可能想尝试使用 inline 关键字。

此外，正如之前的海报所提到的，C# 和 F# 版本由于 Console.WriteLine 语句而有所不同。

于 2010-07-13T22:37:40.850 回答