Quando si crea un valore intermedio dovrei conservarla?

Question

Sto cercando di imparare F # così ho pagato una visita a Project Euler e attualmente sto lavorando su Problema 3 .

  

I fattori primi di 13195 sono 5, 7,   13 e 29.

     

Qual è il più grande primo   fattore del numero 600851475143?

Alcune cose da considerare:

1. La mia prima priorità è quella di imparare le buone abitudini funzionali.
2. La mia seconda priorità è vorrei che fosse veloce ed efficiente.

Nel codice seguente mi hanno segnato la sezione di questa domanda è per quanto riguarda.

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) 

Aggiorna

In base al largo alcuni dei commenti che ho refactoring il codice per essere 10 volte più veloce.

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)

Aggiorna

Vorrei ringraziare tutti per lì un consiglio. Questa ultima versione è una raccolta di tutti i consigli che ho ricevuto.

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 programmazione funzionale diventa più facile e più automatico con la pratica, quindi non preoccupatevi se non si ottiene assolutamente giusto al primo tentativo.

Con questo in mente, diamo il vostro codice di esempio:

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

La versione no variable è proprio strano, non ne fanno uso. Mi piace la tua versione con la esplicita lascia vincolante.

Un altro modo di scrivere che sarebbe stato:

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

La OK e di tanto in tanto utile scrivere in questo modo, ma ancora si presenta come un po 'strano. La maggior parte del tempo, usiamo |> di accattivarsi i valori senza la necessità di nominare le nostre variabili (in stile "pointfree"). Cercare di anticipare come verrà utilizzato la funzione, e, se possibile, ri-scrivere in modo da poter utilizzare con l'operatore tubo senza esplicito variabili dichiarate. Ad esempio:

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

Non più di nome args:)

---

Ok, ora che abbiamo che fuori del modo, diamo un'occhiata a vostra funzione isPrime:

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

Probabilmente avete sentito parlare di usare la ricorsione invece di loop, e che molto è giusto. Ma, per quanto possibile, si dovrebbe ricorsione astrarre con pieghe, mappe o funzioni di ordine superiore. Due motivi per questo:

1. è un po 'più leggibile, e

2. ricorsione impropriamente scritto si tradurrà in un overflow dello stack. Ad esempio, la funzione non è ricorsiva di coda, in modo che sarà saltare in aria su grandi valori di n.

Mi piacerebbe riscrivere isPrime in questo modo:

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

La maggior parte del tempo, se è possibile astrarre tuo esplicito loop, allora si sta solo applicando trasformazioni alla sequenza di ingresso fino ad ottenere i risultati:

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

non abbiamo nemmeno variabili intermedie in questa versione. Coolness!

---

  

La mia seconda priorità è lo vorrei   di essere veloce ed efficiente.

La maggior parte del tempo, F # sta per essere abbastanza confrontabili con C # in termini di velocità, o sta andando essere "abbastanza veloce". Se si trova il codice richiede molto tempo per l'esecuzione, probabilmente significa che si sta utilizzando la struttura dati sbagliato o un cattivo algoritmo. Per un esempio concreto, leggere i commenti su questa questione .

Quindi, il codice che ho scritto è "elegante", nel senso che la sua concisa, dà i risultati corretti, e non si basa su alcun inganno. Purtroppo, non è molto veloce. Per l'avvio:

• utilizza divisione di prova per creare una sequenza di numeri primi, quando il crivello di Eratostene sarebbe molto più veloce. [Edit:. Ho scritto una versione un po 'ingenua di questo vaglio che non ha funzionato per i numeri più grandi di Int32.MaxValue, così ho rimosso il codice]

• leggere l'articolo di Wikipedia sulla primo conteggio funzione , sarà dare indicazioni su calcolo del primo n innesca così come la stima dei limiti superiori e inferiori per il primo nth.

[Edit: ho incluso un codice con un'implementazione un po 'ingenua di un setaccio di Eratostene. Funziona solo per gli ingressi in meno rispetto Int32.MaxValue, quindi probabilmente non è adatto per Project Euler.]

Answer 2

Per quanto riguarda "buona abitudine funzionale", o meglio le buone pratiche vedo tre cose minori. Utilizzando il rendimento nella sequenza è un po 'più difficile da leggere non solo filtrare. annotazioni di tipo non necessarie in un linguaggio dedotto tipo porta a refactoring difficile e rende il codice più difficile da leggere. Non andare in mare e cercare di rimuovere ogni tipo di annotazione anche se si sta trovando difficile. Infine facendo una funzione lambda che richiede solo un valore da utilizzare come variabile temperatura riduce la leggibilità.

Per quanto riguarda lo stile personale va preferisco più spazi e solo usando argomenti tupled quando i dati ha senso essere raggruppati insieme.

mi piacerebbe scrivere il codice originale come questo.

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

Il tuo codice aggiornato è ottimale per il vostro approccio. Si dovrà usare un algoritmo diverso, come Yin Zhu rispondere per andare più veloce. Ho scritto un test per verificare se F # rende la funzione ricorsiva di coda "check" e lo fa.

Answer 3

variabile p è in realtà legando un nome, non una variabile. Utilizzando vincolante nome non è un cattivo stile. Ed è più leggibile. Lo stile pigro di nextPrime è buono, ed è in realtà il primo test ogni numero una sola volta durante l'intero programma.

La mia soluzione

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

Io fondamentalmente divide num da 2, 3, 4 .. e non considerano eventuali numeri primi. Perché se ci divide tutte 2 dal num, quindi non saremo in grado di dividerlo per 4,8, ecc.

su questo numero, la mia soluzione è più veloce:

> 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

Penso che il codice con il legame temporanea è significativamente più facile da leggere. E 'piuttosto insolito per creare una funzione anonima e poi subito applicarlo a un valore come si fa in altri casi. Se davvero si vuole evitare di utilizzare un valore temporaneo, penso che il modo più idiomatico per farlo in F # sarebbe quella di utilizzare l'operatore (|>) al tubo di valore nella funzione anonima, ma io continuo a pensare che questo non è abbastanza leggibile.