Al crear un valor intermediario debería almacenarlo?

Question

Estoy tratando de aprender F # así que hice una visita a Proyecto Euler y actualmente estoy trabajando en Problema 3 .

  

Los factores primos de 13195 son 5, 7,   13 y 29.

     

¿Cuál es el mayor número primo   el factor del número 600851475143?

Algunas cosas a tener en cuenta:

1. Mi primera prioridad es aprender buenos hábitos funcionales.
2. Mi segunda prioridad es que me gustaría que sea rápido y eficiente.

En el siguiente código que han marcado la sección de esta pregunta es con respecto.

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) 

Actualizar

Basado de algunos de los comentarios que he rediseñado el código a ser 10 veces más rápido.

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)

Actualizar

Me gustaría agradecer a todos por allí consejo. Esta última versión es una recopilación de todos los consejos que he recibido.

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

La programación funcional se vuelve más fácil y automática con la práctica, por lo que no se preocupe si no lo consigue toda la razón en el primer intento.

Con esto en mente, vamos a tomar el ejemplo de código:

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) 
            //*************

Su versión no variable es simplemente extraño, no lo use. Me gusta su versión con la explícita deje de unión.

Otra manera de escribir sería:

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

Su Aceptar y, en ocasiones, resulta útil escribir como este, pero todavía aparece como un poco raro. La mayoría de las veces, se utiliza |> de ganarse valores sin necesidad de nombrar las variables (en el estilo de "pointfree"). Trate de anticipar cómo se utilizará su función, y si es posible, volver a escribir para que pueda usarlo con el operador de la tubería sin explícita variables declaradas. Por ejemplo:

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

No más argumentos con nombre:)

---

Ok, ahora que hemos que fuera del camino, vamos a ver su función isPrime:

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

Usted ha oído probablemente a utilizar la recursividad en lugar de bucles, y eso está bien. Sin embargo, siempre que sea posible, debe recursividad abstraer con pliegues, mapas o funciones de orden superior. Dos razones para esto:

1. es un poco más fácil de leer, y

2. recursión incorrectamente escrita dará lugar a un desbordamiento de pila. Por ejemplo, su función no es recursivo de cola, lo que va a volar en grandes valores de n.

Me reescribir isPrime como esto:

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

La mayoría de las veces, si se puede abstraer su bucle explícita, a continuación, usted es justo aplicar transformaciones a su secuencia de entrada hasta que obtenga sus resultados:

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

Ni siquiera tenemos variables intermedias en esta versión. Frescor!

---

  

Mi segunda prioridad es que me gustaría   para ser rápido y eficiente.

La mayoría de las veces, F # va a ser bastante comparables con C # en términos de velocidad, o que va a ser "lo suficientemente rápido". Si encuentra que su código toma un largo tiempo para ejecutar, probablemente significa que está utilizando la estructura de datos incorrecto o una mala algoritmo. Para un ejemplo concreto, leer los comentarios sobre esta cuestión .

Por lo tanto, el código que he escrito es "elegante" en el sentido de que su concisa, da los resultados correctos, y no se basa en ningún engaño. Por desgracia, no es muy rápido. Para el arranque:

• se utiliza la división de prueba para crear una secuencia de números primos, cuando la criba de Eratóstenes sería mucho más rápido. [Editar:. Me escribió una versión un tanto ingenua de esta criba, que no funcionaba para un número mayor de Int32.MaxValue, por lo que he eliminado el código]

• leer el artículo de Wikipedia sobre el primer conteo función , que va le dará indicaciones sobre el cálculo del primer n ceba, así como la estimación de los límites superior e inferior para el primer nth.

[Editar: He incluido un código con una aplicación un tanto ingenua de una criba de Eratóstenes. Sólo funciona para las entradas de menos de Int32.MaxValue, por lo que probablemente no es adecuado para Euler proyecto.]

Answer 2

En cuanto a "buen hábito funcional" o más bien una buena práctica que ver tres cosas de menor importancia. Usando el rendimiento en su secuencia es un poco más difícil de leer que simplemente filtrar. anotaciones de tipo innecesarias en un lenguaje inferido tipo conduce a refactorización difícil y hace que el código sea más difícil de leer. No vaya al agua y tratar de eliminar todo tipo de anotación, aunque si usted está teniendo dificultades. Por último hacer una función lambda que sólo toma un valor para su uso como una variable de temperatura reduce la legibilidad.

En lo que va estilo personal prefiero más espacios y sólo utilizando argumentos tupled cuando los datos tiene sentido ser agrupados juntos.

Me gustaría escribir el código original como éste.

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

Su código actualizado es óptimo para su enfoque. Usted tendría que utilizar un algoritmo diferente, como Yin Zhu responder a ir más rápido. Escribí una prueba para comprobar para ver si F # hace que la función recursiva cola "marcar" y lo hace.

Answer 3

variables p es en realidad un nombre vinculante, no una variable. El uso de la unión nombre no es un mal estilo. Y es más fácil de leer. El estilo flojo de nextPrime es bueno, y que en realidad prime-test cada número sólo una vez durante todo el programa.

Mi Solución

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

Me divide básicamente num de 2, 3, 4 .. y parece que ninguna números primos. Porque si nos divide a todos los 2 de num, entonces no vamos a ser capaces de dividirlo por 4,8, etc.

en este número, mi solución es más rápido:

> 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

Answer 4

Creo que el código con la unión temporal es mucho más fácil de leer. Es bastante inusual para crear una función anónima y luego aplicarlo inmediatamente a un valor como lo hace en el otro caso. Si realmente desea evitar el uso de un valor temporal, creo que la forma más idiomática para hacer eso en Fa # sería utilizar el operador (|>) a la tubería el valor en la función anónima, pero sigo pensando que esto no es tan legible.