Lors de la création d'une valeur intermédiaire dois-je stocker?

Question

Je suis en train d'apprendre F #, donc je visitai Projet Euler et je travaille actuellement sur problème 3 .

  

Les facteurs premiers de 13195 sont 5, 7,   13 et 29.

     

Quel est le plus grand nombre premier   facteur du nombre 600851475143?

Il y a des choses à considérer:

1. Ma première priorité est d'apprendre de bonnes habitudes fonctionnelles.
2. Ma deuxième priorité est que je voudrais que ce soit rapide et efficace.

Dans le code suivant j'ai marqué la section cette question concerne.

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) 

Mise à jour

D'après une partie de la rétroaction que j'ai refondus le code à 10 fois plus rapide.

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)

Mise à jour

Je voudrais remercier tout le monde pour y obtenir des conseils. Cette dernière version est une compilation de tous les conseils que je recevais.

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

Programmation fonctionnelle devient plus facile et plus automatique avec la pratique, alors ne pas transpirer si vous ne l'obtenez pas tout à fait raison sur le premier essai.

Dans cet esprit, nous allons prendre votre exemple de code:

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

Votre version no variable est juste bizarre, ne l'utilisez pas. J'aime votre version avec l'explicite laisser la liaison.

Une autre façon d'écrire serait:

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

Son ok et de temps en temps utile de l'écrire comme ça, mais vient encore apparaître comme un peu bizarre. La plupart du temps, nous utilisons |> au curry valeurs sans avoir besoin de nommer nos variables (dans le style de "Pointfree"). Essayez d'anticiper la façon dont votre fonction sera utilisée, et si possible, ré-écrire afin que vous puissiez l'utiliser avec l'opérateur de conduite sans variables déclarées explicites. Par exemple:

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

Plus nommé args:)

---

Ok, maintenant que nous avons que de la route, regardons votre fonction isPrime:

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

Vous avez probablement entendu utiliser la récursivité au lieu de boucles, et que beaucoup est juste. Mais, chaque fois que possible, vous devriez abstraire récursion avec des plis, des cartes ou des fonctions d'ordre supérieur. Deux raisons à cela:

1. est un peu plus lisible, et

2. récursion mal écrit entraînera un débordement de pile. Par exemple, votre fonction n'est pas récursive queue, donc ça va sauter sur les grandes valeurs de n.

Je réécris isPrime comme ceci:

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

La plupart du temps, si vous le pouvez abstraire votre boucle explicite, alors vous êtes juste d'appliquer des transformations à votre séquence d'entrée jusqu'à ce que vous obtenez vos résultats:

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

Nous n'avons même pas des variables intermédiaires dans cette version. Coolness!

---

  

Ma deuxième priorité est que je le voudrais   pour être rapide et efficace.

La plupart du temps, F # va être assez comparable à C # en termes de vitesse, ou il va être « assez vite ». Si vous trouvez votre code prend beaucoup de temps pour exécuter, cela signifie probablement que vous utilisez la structure de données erronées ou un mauvais algorithme. Pour un exemple concret, lisez les commentaires sur cette question.

Alors, le code que j'ai écrit est « élégante » dans le sens que son concis, donne les bons résultats, et ne repose sur aucune supercherie. Malheureusement, ce ne est pas très rapide. Pour commencer:

• il utilise la division d'essai pour créer une séquence de nombres premiers, quand serait beaucoup plus rapide la Sieve d'Eratosthène. [Edit:. J'ai écrit une version quelque peu naïve de ce tamis qui ne fonctionne pas pour un plus grand nombre que Int32.MaxValue, donc je l'ai supprimé le code]

• lire l'article de Wikipédia sur le première fonction comptage , il va vous donner des indications sur le calcul de la première n nombres premiers, ainsi que l'estimation des limites supérieure et inférieure pour la prime nth.

[Edit: J'inclus un code avec une mise en œuvre un peu naïve d'un tamis d'Eratosthène. Il ne fonctionne que pour les entrées de moins que Int32.MaxValue, il est donc probablement pas adapté pour euler du projet.]

Answer 2

En ce qui concerne la « bonne habitude fonctionnelle » ou plutôt une bonne pratique, je vois trois choses mineures. En utilisant le rendement dans la séquence est un peu plus difficile à lire que simplement filtrer. annotations de type non nécessaires dans une langue de type inféré conduit à refactoring difficile et rend plus difficile à lire le code. Ne pas aller trop loin et essayer de supprimer toutes les annotations de type mais si vous trouvez qu'il est difficile. Enfin faire une fonction lambda qui ne prend que la valeur à utiliser comme une variable de température réduit la lisibilité.

En ce qui concerne le style personnel va, je préfère plus d'espaces et seulement en utilisant des arguments uplées lorsque les données est logique étant regroupées.

J'écrire votre code original comme celui-ci.

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

Votre code mis à jour est optimale pour votre approche. Vous devez utiliser un algorithme différent comme Yin Zhu répondre à aller plus vite. J'ai écrit un test pour vérifier si F # fait la queue de fonction « vérifier » récursive et il fait.

Answer 3

variable p est en fait un nom obligatoire, pas une variable. nom à l'aide de liaison est pas un mauvais style. Et il est plus facile à lire. Le style paresseux de nextPrime est bon, et il en fait le premier test chaque numéro qu'une seule fois au cours de l'ensemble du programme.

Ma solution

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

Je divise essentiellement num de 2, 3, 4 .. et ne considère pas les nombres premiers. Parce que si l'on divise tous les deux de num, nous ne serons pas en mesure de le diviser par 4,8, etc.

sur ce numéro, ma solution est plus rapide:

> 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

Je pense que le code avec la liaison temporaire est beaucoup plus facile à lire. Il est assez rare de créer une fonction anonyme puis l'appliquer immédiatement à une valeur comme vous le faites dans l'autre cas. Si vous voulez vraiment éviter d'utiliser une valeur temporaire, je pense que la façon la plus idiomatiques de le faire en F # serait d'utiliser l'opérateur de (|>) à la conduite de la valeur dans la fonction anonyme, mais je pense toujours que c'est pas tout à fait lisible.