素数生成器的F#vs C#性能

Question

我注意到F#和C#中看似相同的代码不会执行相同的操作.F#的数量级更慢.作为一个例子,我提供的代码生成素数/给出F#和C#中的第n个素数.我的F#代码是:

let rec isprime x =
primes
|> Seq.takeWhile (fun i -> i*i <= x)
|> Seq.forall (fun i -> x%i <> 0)

and primes = 
    seq {
        yield 2
        yield! (Seq.unfold (fun i -> Some(i, i+2)) 3)
                |> Seq.filter isprime
    }


let n = 1000
let start = System.DateTime.Now
printfn "%d" (primes |> Seq.nth n)
let duration = System.DateTime.Now - start
printfn "Elapsed Time: "
System.Console.WriteLine duration

而C#看起来像这样:

class Program
{
    static bool isprime(int n)
    {
        foreach (int p in primes())
        {
            if (p * p > n)
                return true;
            if (n % p == 0)
                return false;
        }
        return true;
    }

    static IEnumerable<int> primes()
    {
        yield return 2;
        for (int i=3; ; i+=2)
        {
            if (isprime(i))
                yield return i;
        }
    }

    static void Main(string[] args)
    {
        int n = 1000;
        var pr = primes().GetEnumerator();
        DateTime start = DateTime.Now;
        for (int count=0; count<n; count++)
        {
            pr.MoveNext();
        }
        Console.WriteLine(pr.Current);
        DateTime end = DateTime.Now;
        Console.WriteLine("Duration " + (end - start));
    }
}

当我测量不同时,n我获得至少7倍的C#优势如下:

• n = 100:C#= 5毫秒F#= 64毫秒
• n = 1000:C#= 22毫秒F#= 180毫秒
• n = 5000:C#= 280毫秒F#= 2.05秒
• n = 10000:C#= 960milsec F#= 6.95sec

我的问题:

• 这两个程序是否相同？
• 如果是,为什么不将它们编译成相同/等效的CLI？
• 如果没有,为什么不呢？
• 我怎样才能/我可以改进我的F#素数生成器以执行更类似于C#的生成器？
• 通常,我(或者为什么我不能)总是模仿F#中的C#代码,所以我的F#代码表现同样快？

编辑1:我已经意识到算法本身可以通过仅遍历isprime中的奇数和非素数来改进,使其成为非递归的,但这对于提出的问题是一种垂直的事实:)

Answer 1

这个:

这两个程序是否相同？

这是一个哲学问题.

在我看来,C#和F#实现的输出isprime总是会同意任何给定的x,所以在这个意义上它们是等价的.但是,在如何实现它们方面存在许多差异(例如,Seq.unfold将创建一个中间IEnumerable<_>值,然后Seq.filter将创建另一个,因此您生成了更多的短期对象并使用了更多的函数调用F#代码),因此它们在各个编译器生成的低级指令方面不相同并不令人惊讶.

如果你愿意,你可以创建与C#代码更相似的F#代码,代价是更加迫切和不那么惯用:

let rec primes = 
    seq {
        yield 2
        let mutable x = 3
        while true do
            if isprime x then 
                yield x
            x <- x + 2
    }
and isprime x =
    use e = primes.GetEnumerator()
    let rec loop() =
        if e.MoveNext() then
            let p = e.Current
            if p * p > x then true
            elif x % p = 0 then false
            else loop()
        else true            
    loop()

primes |> Seq.item 5000使用此实现在我的机器上大约需要0.6秒,相比之下,实现大约需要2.7秒.我认为一般来说,F#seq表达式的代码生成通常比C#迭代器的代码生成稍差,所以如果C#运行得更快,我也不会感到惊讶.(但是请注意,有些成语在F#中比在C#中更快,所以F#并不总是更慢 - 根据我的经验,这两种语言总体上相当可比,而且我觉得编写F#代码更加愉快).

在任何情况下,我不建议如何使F#编译器的输出更接近C#编译器的细节,而是建议寻找算法改进.例如,简单地把一个电话Seq.cache在你原来的定义的结尾primes品牌primes |> Seq.item 5000把我的机器,这比原来的C#大大快于只0.062秒.