在创建中间值时,我应该存储它吗？

Question

我正在努力学习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

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绑定.

写它的另一种方法是:

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'

没有更多名称args :)

好的,现在我们已经完成了这个,让我们来看看你的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#相当,或者它会"足够快".如果您发现代码需要很长时间才能执行,则可能意味着您使用的是错误的数据结构或错误的算法.有关具体示例,请阅读有关此问题的评论.

所以,我写的代码是"优雅的",因为它简洁,给出了正确的结果,并且不依赖任何技巧.不幸的是,它不是很快.首先:

• 当Eratosthenes的Sieve速度更快时,它会使用试验分区创建一系列素数.[编辑:我写了一个有点天真的筛子版本,对于大于Int32.MaxValue的数字不起作用,所以我删除了代码.]

• 阅读维基百科关于素数计数函数的文章,它将为您提供有关计算第一个n素数以及估计素数的上限和下限的指示nth.

[编辑:我提供了一些代码,有点天真的eratosthenes筛子的实现.它仅适用于小于int32.MaxValue的输入,因此它可能不适合项目euler.]

Answer 2

关于"良好的功能习惯"或相当好的做法,我看到三件小事.使用序列中的yield比使用过滤器更难阅读.类型推断语言中不必要的类型注释会导致难以重构并使代码更难阅读.如果发现困难,请不要过分尝试删除所有类型的注释.最后,创建一个只使用一个值作为临时变量的lambda函数会降低可读性.

就个人风格而言,我更喜欢更多的空间,只有当数据组合在一起时才使用tupled参数.

我会写这样的原始代码.

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#是否使"检查"函数尾递归,它确实如此.