f# - 在创建中间值时，我应该存储它吗？

Question

我正在尝试学习 F#，所以我访问了 Project Euler我目前正在研究 Problem 3 .

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

一些需要考虑的事情:

1. 我的首要任务是养成良好的工作习惯。
2. 我的第二要务是我希望它快速高效。

在下面的代码中，我标记了这个问题所涉及的部分。

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

let greatestPrimeFactor(n:int64) =
    let nextPrime(prime:int64):int64 = 
        seq { for i = prime + 1L to System.Int64.MaxValue do if isPrime(i) then yield i }  
        |> Seq.skipWhile(fun v -> n % v <> 0L) 
        |> Seq.hd
    let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************
    findNextPrimeFactor(n, 2L) 

更新

根据一些反馈，我重构了代码，使其速度提高了 10 倍。

module Problem3

module private Internal =
    let execute(number:int64):int64 = 
        let rec isPrime(value:int64, current:int64) = 
            current > value / 2L or (value % current <> 0L && isPrime(value, current + 1L))   
        let rec nextPrime(prime:int64):int64 = 
            if number % prime = 0L && isPrime(prime, 2L) then prime else nextPrime(prime + 1L)       
        let rec greatestPrimeFactor(current:int64, prime:int64):int64 =
            if current = 1L then prime else nextPrime(prime + 1L) |> fun p -> greatestPrimeFactor(current / p, p)
        greatestPrimeFactor(number, 2L)


let execute() = Internal.execute(600851475143L)

更新

我要感谢大家的建议。这个最新版本是我收到的所有建议的汇编。

module Problem3

module private Internal =
    let largestPrimeFactor number = 
        let rec isPrime value current = 
            current > value / 2L || (value % current <> 0L && isPrime value (current + 1L))   
        let rec nextPrime value =
            if number % value = 0L && isPrime value 2L then value else nextPrime (value + 1L) 
        let rec find current prime =
            match current / prime with
            | 1L -> prime
            | current -> nextPrime (prime + 1L) |> find current
        find number (nextPrime 2L)            

let execute() = Internal.largestPrimeFactor 600851475143L

Answer 1

函数式编程通过练习变得更容易和更自动化，所以如果您在第一次尝试时没有完全正确，请不要担心。

考虑到这一点，让我们来看看您的示例代码:

let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************

您的no variable 版本很奇怪，不要使用它。我喜欢带有显式 let 绑定(bind)的版本。

另一种写法是:

nextPrime(prime) |> fun p -> findNextPrimeFactor(number / p, p)

ok 像这样写它偶尔也很有用，但仍然让人觉得有点奇怪。大多数时候，我们使用|> 来curry 值而不 需要命名我们的变量(以“pointfree”风格)。尝试预测你的函数将如何被使用，如果可能的话，重写它，这样你就可以在没有显式声明变量的情况下与管道运算符一起使用它。例如:

let rec findNextPrimeFactor number prime =
    match number / prime with
    | 1L -> prime
    | number' -> nextPrime(prime) |> findNextPrimeFactor number'

不再有命名参数 :)

---

好的，现在我们已经解决了这个问题，让我们看看您的 isPrime 函数:

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

您可能听说过使用递归而不是循环，这是对的。但是，只要有可能，您应该使用折叠、映射或高阶函数抽象掉递归。这样做的两个原因:

1. 它更具可读性，并且

2. 递归写得不当会导致栈溢出。例如，您的函数不是尾递归的，因此它会在 n 的大值上爆炸。

我会像这样重写 isPrime:

let isPrime n = seq { 2L .. n / 2L } |> Seq.exists (fun i -> n % i = 0L) |> not

大多数时候，如果您可以抽象出显式循环，那么您只需对输入序列应用转换，直到获得结果:

let maxFactor n =
    seq { 2L .. n - 1L }                        // test inputs
    |> Seq.filter isPrime                       // primes
    |> Seq.filter (fun x -> n % x = 0L)         // factors
    |> Seq.max                                  // result

我们在这个版本中甚至没有中间变量。凉爽!

---

My second priority is I would like it to be fast and efficient.

大多数时候，F# 在速度方面与 C# 相当，或者说“足够快”。如果您发现您的代码需要很长时间才能执行，这可能意味着您使用了错误的数据结构或错误的算法。有关具体示例，请阅读评论 on this question .

因此，我编写的代码在某种意义上是“优雅”的，因为它简洁明了，给出了正确的结果，并且不依赖于任何诡计。不幸的是，它不是很快。开始:

• 它使用试除法创建素数序列，而埃拉托色尼筛法要快得多。 [编辑:我写了一个有点天真的版本的这个筛子，它不适用于大于 Int32.MaxValue 的数字，所以我删除了代码。]

• 阅读维基百科关于 prime counting function 的文章，它将为您提供有关计算第一个 n 素数以及估计 nth 素数的上限和下限的指导。

[编辑:我包含了一些代码，其中包含了埃拉托色尼筛法的一些天真的实现。它仅适用于小于 int32.MaxValue 的输入，因此它可能不适合欧拉项目。]