Wenn ein Zwischenwert zu schaffen soll ich es speichern?

https://stackoverflow.com/questions/2036073

19-09-2019
|

Frage

Ich versuche, F # zu lernen, so dass ich einen Besuch Projekt Euler bezahlt und ich gerade arbeite auf Problem 3 .

Die Primfaktoren von 13195 sind 5, 7,   13 und 29.

Was ist die größte Primzahl   Faktor der Anzahl 600851475143?

Einige Dinge zu beachten:

Meine erste Priorität ist gute funktionelle Gewohnheiten zu lernen.
Meine zweite Priorität ist Ich mag es würde schnell und effizient zu sein.

Im folgenden Code habe ich den Abschnitt markierte diese Frage in Bezug auf.

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)

Aktualisieren

Basierend off einige der Rückmeldungen ich den Code Refactoring haben 10-mal schneller sein.

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)

Aktualisieren

würde ich dort Rat zu danken allen gefallen. Diese neueste Version ist eine Zusammenstellung aller Ratschläge, die ich erhielt.

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

Lösung

Funktionale Programmierung wird einfacher und automatisch mit der Praxis so nicht schwitzen, wenn Sie es nicht unbedingt richtig machen beim ersten Versuch.

Mit dem im Verstand, lassen Sie sich Ihren Beispielcode nehmen:

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

Ihre no variable Version ist nur seltsam, verwenden Sie es nicht. Ich mag Ihre Version mit der expliziten let binden.

Eine andere Möglichkeit, es zu schreiben wäre:

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

Die ok und gelegentlich nützlich es so zu schreiben, kommt aber immer noch über ein wenig seltsam. Die meiste Zeit verwenden wir |> Werte Curry ohne , um unsere Variablen zu nennen (in „pointfree“ Stil). Versuchen Sie zu antizipieren, wie Sie Ihre Funktion verwendet wird, und wenn möglich, re-write es so können Sie es mit dem Rohr Operator ohne explizite deklarierten Variablen verwenden. Zum Beispiel:

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

Nicht mehr genannt argumente:)

Ok, jetzt, da wir, dass aus dem Weg haben, lassen Sie sie Blick auf Ihrer isPrime Funktion:

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

Sie haben wahrscheinlich zu verwenden Rekursion statt Schleifen zu hören, und so viel ist richtig. Aber, wo immer möglich, sollten Sie abstrahieren Rekursion mit Falten, Karten oder Funktionen höherer Ordnung. Zwei Gründe:

sein ein wenig mehr lesbar ist, und
falsch geschrieben Rekursion wird in einem Stapelüberlauf führen. Zum Beispiel ist Ihre Funktion nicht Schwanz rekursiv, so dass es auf große Werte von n sprengen werden.

Ich würde isPrime wie folgt umschreiben:

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

Die meiste Zeit, wenn Sie abstrakt können Ihr persönliches Vertrauen Looping weg, dann sind Sie nur Transformationen auf Ihre Eingangssequenz anwenden, bis Sie Ihre Ergebnisse erhalten:

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

Wir haben nicht einmal Zwischenvariablen in dieser Version. Kaltblütigkeit!

Meine zweite Priorität ist, würde ich es mag um schnell und effizient.

Die meisten der Zeit, F # wird ziemlich vergleichbar in Bezug auf die Geschwindigkeit, mit C # sein, oder es wird „schnell genug“ sein. Wenn Sie Ihren Code dauert eine lange Zeit für die Ausführung zu finden, bedeutet dies wahrscheinlich, bist du die falsche Datenstruktur oder einen schlechten Algorithmus. Für ein konkretes Beispiel, lesen Sie die Kommentare zu dieser Frage .

So ist der Code, den ich geschrieben habe, ist „elegant“ in dem Sinne, dass seine prägnante, die richtigen Ergebnisse liefert, und beruht nicht auf irgendeiner Betrügerei. Leider ist es nicht sehr schnell. Für den Start:

es Probedivision verwendet eine Folge von Primzahlen zu erzeugen, wenn das Sieb des Eratosthenes würde viel schneller sein. [Edit: Ich schrieb eine etwas naive Version dieses Sieb, das für Zahlen größer als Int32.MaxValue nicht funktioniert hat, so dass ich den Code entfernt haben.]

Wikipedia-Artikel auf der prime Zählfunktion , wird es geben Sie die Zeiger auf die ersten n Primzahlen Berechnung sowie die obere und untere Grenze für die nth prime schätzen.

[Edit: Ich enthalten einen Code mit einer etwas naiven Implementierung eines Sieb des Eratosthenes. Es funktioniert nur für Eingänge von weniger als Int32.MaxValue, so dass es wahrscheinlich nicht geeignet für Project Euler ist.]

Andere Tipps

In Bezug auf „gute funktionelle Gewohnheit“ oder eher gute Praxis sehe ich drei kleine Dinge. die Ausbeute in Ihrer Sequenz zu verwenden ist ein wenig schwieriger, als nur Filter zu lesen. Unnötige Typenannotationen in einer Art abgeleitet Sprache führt zu schwierigen Refactoring und macht den Code schwerer zu lesen. Gehen Sie nicht über Bord und versuchen, jede Art Anmerkung zu entfernen, obwohl, wenn Sie es schwierig sind zu finden. Schließlich eine Lambda-Funktion zu machen, die nur einen Wert zu verwenden, wie eine temporäre Variable nimmt reduziert die Lesbarkeit.

Was persönlicher Stil geht ziehe ich mehr Räume und nur fach vervielfachten Argumente zu verwenden, wenn die Daten Marken zusammen sense gruppiert werden.

würde ich Ihren ursprünglichen Code so schreiben.

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

Ihr aktualisierte Code ist optimal für Ihren Ansatz. Sie müßten einen anderen Algorithmus wie Yin Zhu Antwort verwenden, schneller zu gehen. Ich schrieb einen Test zu überprüfen, um zu sehen, ob F #, um den „Check“ -Funktion Schwanz rekursive macht und es funktioniert.

die Variable p ist eigentlich eine Namensbindung, keine Variable. Mit Namensbindung ist kein schlechter Stil. Und es ist besser lesbar. Der faule Stil nextPrime ist gut, und es tatsächlich Prime testen Sie jede Zahl nur einmal während des gesamten Programms.

Meine Lösung

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

I teilt sich grundsätzlich num von 2, 3, 4 .. und Sie alle Primzahlen nicht prüfen. Denn wenn wir alle 2 aus num teilen, dann werden wir nicht in der Lage sein, es zu teilen, um 4,8, etc.

auf dieser Nummer, meine Lösung ist schneller:

> 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

Ich denke, dass der Code mit der temporären Bindung ist wesentlich einfacher zu lesen. Es ist ziemlich ungewöhnlich, dass eine anonyme Funktion zu erstellen und dann sofort anwenden es auf einen Wert, wie Sie im anderen Fall zu tun. Wenn Sie wirklich mit einem temporären Wert vermeiden wollen, glaube ich, dass die meisten idiomatische Weise, dass # in F zu tun wäre, um den (|>) Operator den Wert in die anonyme Funktion Rohr zu verwenden, aber ich denke immer noch, dass dies nicht ganz so ist lesbar.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow