lje*_*osn 12 c++ math performance f# lazy-evaluation
这个F#代码试图解决Project Euler问题#58:
let inc = function
| n -> n + 1
let is_prime = function
| 2 -> true
| n when n < 2 || n%2=0-> false
| n ->
[3..2..(int (sqrt (float n)))]
|> List.tryFind (fun i -> n%i=0)
|> Option.isNone
let spir = Seq.initInfinite (fun i ->
let n = i%4
let a = 2 * (i/4 + 1)
(a*n) + a + (a-1)*(a-1))
let rec accum se p n =
match se with
| x when p*10 < n && p <> 0 -> 2*(n/4) + 1
| x when is_prime (Seq.head x) -> accum (Seq.tail x) (inc p) (inc n)
| x -> accum (Seq.tail x) p (inc n)
| _ -> 0
printfn "%d" (accum spir 0 1)
我不知道这个节目的运行时间,因为我拒绝等待它完成.相反,我在C++中强制编写了这段代码:
#include "stdafx.h"
#include "math.h"
#include <iostream>
using namespace std;
int is_prime(int n)
{
if (n % 2 == 0) return 0;
for (int i = 3; i <= sqrt(n); i+=2)
{
if (n%i == 0)
{
return 0;
}
}
return 1;
}
int spir(int i)
{
int n = i % 4;
int a = 2 * (i / 4 + 1);
return (a*n) + a + ((a - 1)*(a - 1));
}
int main()
{
int n = 1, p = 0, i = 0;
cout << "start" << endl;
while (p*10 >= n || p == 0)
{
p += is_prime(spir(i));
n++; i++;
}
cout << 2*(i/4) + 1;
return 0;
}
上面的代码在不到2秒的时间内运行并获得正确的答案.
是什么让F#代码运行得如此之慢？即使在使用旧的Stackoverflow帖子中提到的一些分析工具之后,我仍然无法弄清楚正在发生的昂贵操作.
有了rmunn的帖子,我能够提出一个不同的实现,在不到30秒的时间内得到答案:
let inc = function
| n -> n + 1
let is_prime = function
| 2 -> true
| n when n < 2 || n%2=0-> false
| n ->
[3..2..(int (sqrt (float n)))]
|> List.tryFind (fun i -> n%i=0)
|> Option.isNone
let spir2 =
List.unfold (fun state ->
let p = fst state
let i = snd state
let n = i%4
let a = 2 * (i/4 + 1)
let diag = (a*n) + a + (a-1)*(a-1)
if p*10 < (i+1) && p <> 0 then
printfn "%d" (2*((i+1)/4) + 1)
None
elif is_prime diag then
Some(diag, (inc p, inc i))
else Some(diag, (p, inc i))) (0, 0)
有了FuleSnabel的信息,他的is_prime功能使上面的代码在十分之一秒内运行,使其比C++代码更快:
let inc = function
| n -> n + 1
let is_prime = function
| 1 -> false
| 2 -> true
| v when v % 2 = 0 -> false
| v ->
let stop = v |> float |> sqrt |> int
let rec loop vv =
if vv <= stop then
if (v % vv) <> 0 then
loop (vv + 2)
else
false
else
true
loop 3
let spir2 =
List.unfold (fun state ->
let p = fst state
let i = snd state
let n = i%4
let a = 2 * (i/4 + 1)
let diag = (a*n) + a + (a-1)*(a-1)
if p*10 < (i+1) && p <> 0 then
printfn "%d" (2*((i+1)/4) + 1)
None
elif i <> 3 && is_prime diag then
Some(diag, (inc p, inc i))
else Some(diag, (p, inc i))) (0, 0)
rmu*_*unn 12
Seq.tail核心F#库中没有函数(UPDATE:是的,请参阅注释),所以我假设您正在使用FSharpx.Collections中的Seq.tail函数.如果你使用的是不同的实现,它可能是相似的 - 而且几乎可以肯定是你的问题的原因,因为它不像你认为的那样是O(1).获取List的尾部是O(1),因为List的实现方式(作为一系列缺点单元格).但是获得Seq的尾部最终会从原始的可枚举中创建一个全新的Seq,从中丢弃一个项目,并返回其余的项目.当你第二次进入循环时,你会调用"跳过1然后返回"seq.所以现在你有一个我称之为S2的,它要求S1获取IEnumerable,跳过S1的第一项,然后返回其余部分.S1,当被问及它的第一个项目时,向S0(原始Seq)询问可枚举,跳过其第一个项目,然后返回其余部分.因此,对于S2跳过两个项目,它必须创建两个seqs.现在,在你要求S2 的下一次运行时,你创建了S3,要求S2提供IEnumerable,它要求S1提供IEnumerable,它要求S0提供IEnumerable ......依此类推.当你认为你正在编写O(N)操作时,这实际上是O(N ^ 2).Seq.tailaccumSeq.tailSeqSeq.tail
我担心我现在没有时间为你找到解决方案; 使用List.tail无济于事,因为你需要一个无限的序列.但也许只是知道了Seq.tail问题就足以让你开始了,所以即使它没有完成,我现在也会发布这个答案.
如果您需要更多的帮助,在此答案评论,我会回来,当我有时间 - 但可能不是好几天,所以希望其他人也将回答你的问题.
编写高性能F#是非常有可能的,但需要了解在紧密循环中具有较高相对CPU成本的模式.我建议使用像ILSpy这样的工具来查找隐藏的开销.
例如,可以想象F#将此表达式扩展为有效的for循环:
[3..2..(int (sqrt (float n)))]
|> List.tryFind (fun i -> n%i=0)
|> Option.isNone
但它目前没有.相反,它List使用内部运算符创建一个跨越范围并将其传递给List.tryFind.与我们喜欢的实际工作(模数操作)相比,这是昂贵的.ILSpy将上面的代码反编译成如下代码:
public static bool is_prime(int _arg1)
{
switch (_arg1)
{
case 2:
return true;
default:
return _arg1 >= 2 && _arg1 % 2 != 0 && ListModule.TryFind<int>(new Program.Original.is_prime@10(_arg1), SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(3, 2, (int)Math.Sqrt((double)_arg1))))) == null;
}
}
这些操作符并不像它们那样高效(AFAIK目前正在改进),但无论如何有效地分配a List然后搜索它都不会超过for循环.
这意味着is_prime它没有尽可能有效.相反,人们可以这样做:
let is_prime = function
| 1 -> false
| 2 -> true
| v when v % 2 = 0 -> false
| v ->
let stop = v |> float |> sqrt |> int
let rec loop vv =
if vv <= stop then
(v % vv) <> 0 && loop (vv + 2)
else
true
loop 3
此版本is_prime依赖于F#中的尾调用优化,将循环扩展为高效的for循环(您可以使用ILSpy查看).ILSpy将循环反编译为如下所示:
while (vv <= stop)
{
if (_arg1 % vv == 0)
{
return false;
}
int arg_13_0 = _arg1;
int arg_11_0 = stop;
vv += 2;
stop = arg_11_0;
_arg1 = arg_13_0;
}
这个循环不分配内存,只是一个相当有效的循环.人们看到一些非感性的任务,但希望JIT:消除那些.我相信is_prime可以进一步改进.
Seq在高性能代码中使用时,必须记住它是惰性的,默认情况下它不使用memoization(请参阅参考资料Seq.cache).因此,人们可能很容易一遍又一遍地做同样的工作(参见@rmunn回答).
另外Seq由于IEnumerable/IEnumerator设计方式不是特别有效.更好的选择是例如Nessos Streams(在nuget上可用).
如果你感兴趣我做了一个快速的实现,依赖于一个看起来相当高效的简单Push Stream:
// Receiver<'T> is a callback that receives a value.
// Returns true if it wants more values, false otherwise.
type Receiver<'T> = 'T -> bool
// Stream<'T> is function that accepts a Receiver<'T>
// This means Stream<'T> is a push stream (as opposed to Seq that uses pull)
type Stream<'T> = Receiver<'T> -> unit
// is_prime returns true if the input is prime, false otherwise
let is_prime = function
| 1 -> false
| 2 -> true
| v when v % 2 = 0 -> false
| v ->
let stop = v |> float |> sqrt |> int
let rec loop vv =
if vv <= stop then
(v % vv) <> 0 && loop (vv + 2)
else
true
loop 3
// tryFind looks for the first value in the input stream for f v = true.
// If found tryFind returns Some v, None otherwise
let tryFind f (s : Stream<'T>) : 'T option =
let res = ref None
s (fun v -> if f v then res := Some v; false else true)
!res
// diagonals generates a tuple stream of all diagonal values
// The first value is the side length, the second value is the diagonal value
let diagonals : Stream<int*int> =
fun r ->
let rec loop side v =
let step = side - 1
if r (side, v + 1*step) && r (side, v + 2*step) && r (side, v + 3*step) && r (side, v + 4*step) then
loop (side + 2) (v + 4*step)
if r (1, 1) then loop 3 1
// ratio computes the streaming ratio for f v = true
let ratio f (s : Stream<'T>) : Stream<float*'T> =
fun r ->
let inc r = r := !r + 1.
let acc = ref 0.
let count = ref 0.
s (fun v -> (inc count; if f v then inc acc); r (!acc/(!count), v))
let result =
diagonals
|> ratio (snd >> is_prime)
|> tryFind (fun (r, (_, v)) -> v > 1 && r < 0.1)