f# - 计算完美数时出现F#并行化问题？

我正在尝试优化一个小程序，该程序可以根据给定的指数计算出完美的数值。

该程序(几乎)完美运行，但是当我打开任务管理器时，它仍在单个线程上运行。这意味着我必须做错了什么，但是我对F＃的了解仍处于“开始”阶段。

我会尽力澄清这个问题，但是如果我没有这样做，请告诉我。

完美数是一个数字，其中所有除数的总和(数字本身除外)等于数字本身(例如6是完美的，因为其除数1、2和3的总和为6)。

我使用质数来加快计算速度，也就是说，我对存储所有除数的(巨大)列表不感兴趣。为此，我使用Euclid证明是正确的公式:(2 *(num的幂-1))*(2 *(num的幂-1))，其中后者是梅森素数。我使用来自stackoverflow的非常快速的算法(通过@Juliet)来确定给定的数字是否为质数。

当我在Internet上阅读了几篇文章(我还没有购买好书，太可惜了)时，我发现序列的表现比列表更好。因此，这就是为什么我首先开始创建一个生成一系列完美数字的函数的原因:

   let perfectNumbersTwo (n : int) =
    seq { for i in 1..n do
           if (PowShift i) - 1I |> isPrime
           then yield PowShift (i-1) * ((PowShift i)-1I)
        }

辅助功能PowShift的实现如下:

    let inline PowShift (exp:int32) = 1I <<< exp ;;

我使用一位移位运算符，因为所有功效计算的基数都是2，因此这可能是一种简单的方法。当然，对于在以下问题上所做出的贡献，我仍然深表感激:F＃电源问题接受两个参数均为bigints> F# Power issues which accepts both arguments to be bigints

朱丽叶创建的函数(borrowed here)如下:

let isPrime ( n : bigint) =
    let maxFactor = bigint(sqrt(float n))
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0I then false
        else loop (testPrime + tog) (6I - tog)
    if n = 2I || n = 3I || n = 5I then true
    elif n <= 1I || n % 2I = 0I || n % 3I = 0I || n % 5I = 0I then false
    else loop 7I 4I;;

使用此代码而无需并行处理，在我的笔记本电脑上大约需要9分钟才能找到第9个完美的数字(该数字由37位数字组成，并且可以找到指数值为31的数字)。由于我的笔记本电脑的CPU具有两个内核，并且只有一个内核以50％的速度运行(一个内核的满负载)，因此我可以通过并行计算结果来加快计算速度。

因此，我将我的perfectnumber函数更改如下:

//Now the function again, but async for parallel computing
let perfectNumbersAsync ( n : int) =
    async {
        try
            for x in 1.. n do
                if PowShift x - 1I |> isPrime then
                    let result = PowShift (x-1) * ((PowShift x)-1I)
                    printfn "Found %A as a perfect number" result
        with
            | ex -> printfn "Error%s" (ex.Message);
    }

要调用此函数，我使用一个小的辅助函数来运行它:

 let runPerfects n =
    [n]
        |> Seq.map perfectNumbersAsync
        |> Async.Parallel
        |> Async.RunSynchronously
        |> ignore

异步计算的结果被忽略的地方，因为我将其显示在
perfectNumbersAsync函数。

上面的代码可以编译并运行，但是它仍然仅使用一个内核(尽管在计算第9个完美数字时运行速度快了10秒)。恐怕它必须与辅助函数PowShift和isPrime做些事情，但是我不确定。我是否必须将这些辅助函数的代码放入perfectNumbersAsync的异步块中？它不会提高可读性...

我玩F＃的次数越多，就会越了解这种语言，但是像这种情况下，有时我需要一些专家:)。

在此先感谢您阅读本文，我只希望自己能清楚一点...

罗伯特

最佳答案

@Jeffrey Sax的评论绝对很有趣，所以我花了一些时间做一个小实验。 Lucas-Lehmer测试的编写方式如下:

let lucasLehmer p =
    let m = (PowShift p) - 1I
    let rec loop i acc =
        if i = p-2 then acc
        else loop (i+1) ((acc*acc - 2I)%m)
    (loop 0 4I) = 0I

通过Lucas-Lehmer检验，我可以很快得到前几个完美的数字:

let mersenne (i: int) =
    if i = 2 || (isPrime (bigint i) && lucasLehmer i) then
        let p = PowShift i
        Some ((p/2I) * (p-1I))
    else None

let runPerfects n =
    seq [1..n]
        |> Seq.choose mersenne
        |> Seq.toArray

let m1 = runPerfects 2048;; // Real: 00:00:07.839, CPU: 00:00:07.878, GC gen0: 112, gen1: 2, gen2: 1

Lucas-Lehmer测试有助于减少检查素数的时间。代替测试采用O(sqrt(2^p-1))的2 ^ p-1的除数，我们使用最多为O(p^3)的素数测试。
使用n = 2048，我可以在7.83秒内找到前15个梅森数字。第15个梅森号码是带有i = 1279的号码，它由770位数字组成。

我尝试使用F# Powerpack中的PSeq模块并行化runPerfects。 PSeq不会保留原始序列的顺序，因此，公平地说，我对输出序列进行了排序。由于素数检验在各个指标之间相当平衡，因此结果令人鼓舞:

#r "FSharp.Powerpack.Parallel.Seq.dll"
open Microsoft.FSharp.Collections

let runPerfectsPar n =
    seq [1..n]
        |> PSeq.choose mersenne
        |> PSeq.sort (* align with sequential version *)
        |> PSeq.toArray

let m2 = runPerfectsPar 2048;; // Real: 00:00:02.288, CPU: 00:00:07.987, GC gen0: 115, gen1: 1, gen2: 0

在相同的输入下，并行版本花费了2.28秒，相当于我的四核计算机上的3.4倍加速。我相信，如果您使用Parallel.For构造并合理地划分输入范围，则可以进一步改善结果。

关于f# - 计算完美数时出现F#并行化问题？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8368107/