Ao criar um valor intermediário I deve armazená-lo?

Question

Eu estou tentando aprender F #, então eu pago uma visita a Projeto Euler e eu estou trabalhando atualmente em Problema 3 .

Os fatores primos de 13195 são 5, 7, 13 e 29.

O que é o maior primo fator do número 600851475143?

Algumas coisas a considerar:

1. A minha primeira prioridade é aprender bons hábitos funcionais.
2. A minha segunda prioridade é que eu gostaria que ele seja rápido e eficiente.

No seguinte código que eu ter marcado a seção esta pergunta é a respeito.

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) 

Atualizar

Baseado fora alguns dos comentários eu refatorado o código para ser 10 vezes mais 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)

Atualizar

Gostaria de agradecer a todos por lá conselho. Esta última versão é uma compilação de todos os conselhos que eu recebi.

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

A programação funcional torna-se mais fácil e automática com a prática, então não se preocupe se você não obtê-lo absolutamente certo na primeira tentativa.

Com isso em mente, vamos dar o seu código de exemplo:

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

A sua versão no variable é apenas estranho, não usá-lo. I como a sua versão com a ligação a deixar explícito.

Outra forma de escrevê-lo seria:

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

A sua OK e ocasionalmente útil para escrevê-lo como este, mas ainda vem transversalmente como um pouco estranho. Na maioria das vezes, usamos |> para caril valores sem a necessidade de nomear nossas variáveis ??(em "pointfree" estilo). Tente antecipar como sua função será usada, e se possível, reescrevê-lo para que você possa usá-lo com o operador pipe sem variáveis ??declaradas explícitas. Por exemplo:

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

args Não mais nomeados:)

---

Ok, agora que temos que fora do caminho, vamos olhar para a sua função isPrime:

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

Você provavelmente já ouviu a utilização recursão em vez de loops, e que muito está certo. Mas, sempre que possível, deve-se abstrato recursão afastado com dobras, mapas ou funções de ordem superior. Duas razões para isso:

1. é um pouco mais legível, e

2. recursão escrita incorrectamente irá resultar em um estouro de pilha. Por exemplo, sua função não é recursiva cauda, ??por isso vai explodir em grandes valores de n.

Eu reescrever isPrime assim:

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

Na maioria das vezes, se você pode abstrair sua looping explícito, então você está apenas aplicando transformações à sua sequência de entrada até chegar os seus 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

Nós nem sequer temos variáveis ??intermediárias nesta versão. Coolness!

---

A minha segunda prioridade é que eu gostaria que ele para ser rápido e eficiente.

Na maioria das vezes, F # vai ser bastante comparável com C #, em termos de velocidade, ou ele vai ser "suficientemente rápido". Se você encontrar o seu código leva um longo tempo para executar, isso provavelmente significa que você está usando a estrutura de dados errado ou um mau algoritmo. Para um exemplo concreto, leia os comentários sobre esta questão .

Assim, o código que eu escrevi é "elegante" no sentido de que a sua concisa, dá os resultados corretos, e não depende de nenhum truque. Infelizmente, não é muito rápido. Para início:

• que utiliza divisão de teste para criar uma seqüência de números primos, quando o Crivo de Eratóstenes seria muito mais rápido. [Edit: Eu escrevi uma versão um pouco ingênuo desta peneira que não funcionou para números maiores do que Int32.MaxValue, para que eu tenha removido o código.]

• leia o artigo da Wikipedia sobre o nobre contagem função , ele vai dar-lhe indicações sobre como calcular os primeiros números primos n, bem como estimar os limites superior e inferior para o primeiro-nth.

[Edit: Eu incluí um código com uma implementação pouco ingênuo de uma peneira de Eratóstenes. Ele só funciona para as entradas menos de Int32.MaxValue, por isso provavelmente não é adequado para Euler projeto.]

Answer 2

No que diz respeito "bom hábito funcional", ou melhor boas práticas Vejo três pequenas coisas. Utilizando o rendimento em sua seqüência é um pouco mais difícil de ler do que filtro apenas. anotações de tipo desnecessários em um tipo inferido leads língua para difícil refatoração e torna o código mais difícil de ler. Não ir ao mar e tentar remover cada tipo de anotação que se você está encontrando dificuldades. Por último fazendo uma função lambda que leva apenas um valor para uso como uma variável temporário reduz a legibilidade.

Quanto estilo pessoal vai prefiro mais espaços e usando apenas argumentos tupled quando as marcas dados sensoriais sendo agrupadas.

eu ia escrever o seu código original como esta.

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

O seu código atualizado é ideal para a sua abordagem. Você teria que usar um algoritmo diferente, como resposta Yin Zhu para ir mais rápido. Eu escrevi um teste para verificar se F # faz com que a "seleção" recursiva cauda função e ele faz.

Answer 3

variável p é realmente obrigatório um nome, não uma variável. Usando ligação nome não é um estilo ruim. E é mais legível. O preguiçoso estilo de nextPrime é bom, e ele realmente prime-testar cada número apenas uma vez durante todo o programa.

Meu Solução

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

Eu basicamente divide num de 2, 3, 4 .. e não consideram quaisquer números primos. Porque se divide todo 2 de num, então nós não vai ser capaz de dividi-lo por 4,8, etc.

neste número, a minha solução é mais rápida:

> 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

Eu acho que o código com a ligação temporária é significativamente mais fácil de ler. É bastante incomum para criar uma função anônima e logo em seguida aplicá-la a um valor como você faz no outro caso. Se você realmente quer evitar o uso de um valor temporário, eu acho que a maneira mais idiomática de fazer isso na F # seria usar o operador (|>) a tubulação o valor para a função anônima, mas eu ainda acho que este não é tão legível.