2

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

13195 的质因数是 5、7、13 和 29。

数字 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
4

4 回答 4

7

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

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

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 绑定的版本。

另一种写法是：

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

可以这样写，偶尔也有用，但仍然让人觉得有点奇怪。大多数时候，我们使用|>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

在这个版本中，我们甚至没有中间变量。酷！

我的第二个优先事项是我希望它快速高效。

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

所以，我写的代码是“优雅的”，因为它简洁，给出正确的结果，并且不依赖任何诡计。不幸的是，它不是很快。开始：

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

  • 阅读 Wikipedia 关于素数计数功能的文章，它将为您提供有关计算第一个n素数以及估计素数上限和下限的指示nth。

[编辑：我包含了一些代码，其中包含一个有点幼稚的eratosthenes筛子实现。它仅适用于小于 int32.MaxValue 的输入，因此它可能不适合项目 euler。]

于 2010-01-10T06:30:19.373 回答
5

关于“良好的功能习惯”或更确切地说是良好的实践，我看到了三件小事。在您的序列中使用产量比过滤器更难阅读。类型推断语言中不必要的类型注释会导致难以重构并使代码更难阅读。不要过分尝试删除每个类型注释，但如果您发现它很困难。最后制作一个仅将一个值用作临时变量的 lambda 函数会降低可读性。

就个人风格而言，我更喜欢更多的空间，并且仅在将数据组合在一起有意义时才使用元组参数。

我会这样写你的原始代码。

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

let greatestPrimeFactor n =
    let nextPrime prime = 
        seq {prime + 1L .. System.Int64.MaxValue}
        |> Seq.filter isPrime
        |> Seq.skipWhile (fun v -> n % v <> 0L) 
        |> Seq.head

    let rec findNextPrimeFactor number prime =
        if number = 1L then 
            prime 
        else 
            let p = nextPrime(prime)
            findNextPrimeFactor (number / p) p

    findNextPrimeFactor n 2L

您更新的代码最适合您的方法。您必须使用不同的算法，例如印珠答案才能走得更快。我编写了一个测试来检查 F# 是否使“检查”函数尾部递归并且确实如此。

于 2010-01-10T06:04:02.797 回答
3

变量p 实际上是名称绑定，而不是变量。使用名称绑定不是一种糟糕的风格。而且它更具可读性。懒惰的风格nextPrime很好，它实际上在整个程序中只对每个数字进行一次素数测试。

我的解决方案

let problem3 = 
    let num = 600851475143L
    let rec findMax (n:int64) (i:int64) =
        if n=i || n<i then
            n
        elif n%i=0L then
            findMax (n/i) i
        else
            findMax n (i+1L)
    findMax num 2L

我基本上将 num 从 2、3、4 中除以 .. 并且不考虑任何素数。因为如果我们将所有 2 与 num 相除，那么我们将无法将其除以 4,8 等等。

在这个数字上，我的解决方案更快：

> greatestPrimeFactor 600851475143L;;
Real: 00:00:01.110, CPU: 00:00:00.702, GC gen0: 1, gen1: 1, gen2: 0
val it : int64 = 6857L
> 
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val problem3 : int64 = 6857L
于 2010-01-10T04:32:42.990 回答
1

我认为带有临时绑定的代码更容易阅读。创建一个匿名函数然后立即将它应用到一个值是非常不寻常的，就像你在其他情况下所做的那样。如果您真的想避免使用临时值，我认为在 F# 中最惯用的方法是使用(|>)运算符将​​值通过管道传递到匿名函数中，但我仍然认为这不太可读.

于 2010-01-10T04:53:22.407 回答