2

私は F# を学ぼうとしているので、 Project Eulerを訪れ、現在問題 3に取り組んでいます。

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

考慮すべき事項:

  1. 私の最優先事項は、良い機能的な習慣を身につけることです。
  2. 私の 2 番目の優先事項は、高速で効率的であることです。

次のコード内で、この質問に関するセクションをマークしました。

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)

アップデート

いくつかのフィードバックに基づいて、コードをリファクタリングして 10 倍速くしました。

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)

アップデート

アドバイスをくれた皆さんに感謝します。この最新版は、私が受けたすべてのアドバイスをまとめたものです。

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
4

4 に答える 4

7

関数型プログラミングは練習を積むことでより簡単かつ自動化されるため、最初の試行で完全に正しく理解できなくても心配する必要はありません。

それを念頭に置いて、サンプルコードを見てみましょう：

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

あなたのno variableバージョンは奇妙です。使用しないでください。明示的な let バインディングを使用したバージョンが気に入っています。

別の書き方は次のようになります。

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

このように書くことは問題なく、時には便利ですが、それでも少し奇妙に感じられます。ほとんどの場合、変数に名前を付ける必要なく|>値をカリー化します (「ポイントフリー」スタイルで)。関数がどのように使用されるかを予測し、可能であれば、明示的に宣言された変数なしでパイプ演算子で使用できるように書き直してください。例えば：

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

名前付き引数はもうありません:)

isPrimeさて、これで邪魔にならなくなったので、関数を見てみましょう。

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

おそらく、ループの代わりに再帰を使用することを聞いたことがあるでしょう。ただし、可能な限り、フォールド、マップ、または高次関数を使用して再帰を抽象化する必要があります。これには 2 つの理由があります。

  1. もう少し読みやすく、

  2. 不適切に記述された再帰は、スタック オーバーフローを引き起こします。たとえば、関数は末尾再帰的ではないため、 の大きな値で爆発しますn。

私は次のように書き直しisPrimeます：

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

ほとんどの場合、明示的なループを抽象化できれば、結果が得られるまで入力シーケンスに変換を適用するだけです。

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

このバージョンには中間変数さえありません。かっこよさ！

私の 2 番目の優先事項は、高速で効率的であることです。

ほとんどの場合、F# は速度の点で C# に匹敵するか、「十分に高速」です。コードの実行に時間がかかる場合は、間違ったデータ構造または不適切なアルゴリズムを使用している可能性があります。具体的な例については、この質問に関するコメントをお読みください。

したがって、私が書いたコードは、簡潔で正しい結果が得られ、トリックに依存していないという意味で「エレガント」です。残念ながら、それほど速くはありません。はじめに:

  • 試行分割を使用して素数のシーケンスを作成しますが、エラトステネスのふるいの方がはるかに高速です。[編集: Int32.MaxValue より大きい数値では機能しないこのふるいのやや単純なバージョンを作成したため、コードを削除しました。]

  • 素数カウント関数に関するウィキペディアの記事を読むと、最初のn素数の計算と、素数の上限と下限の推定に関する指針が得られますnth。

[編集: エラトステネスのふるいのやや単純な実装を含むコードをいくつか含めました。int32.MaxValue 未満の入力に対してのみ機能するため、プロジェクト euler にはおそらく適していません。]

于 2010-01-10T06:30:19.373 に答える
5

「優れた機能的習慣」またはむしろ優れた実践に関して、私は 3 つの小さなことを見ています。シーケンスでyieldを使用すると、単にフィルタリングするよりも読みにくくなります。型推論言語に不要な型注釈があると、リファクタリングが難しくなり、コードが読みにくくなります。やり過ぎて、すべての型注釈を削除しようとしないでください。最後に、一時変数として使用する値のみを取るラムダ関数を作成すると、読みやすさが低下します。

個人的なスタイルに関する限り、私はより多くのスペースを好み、データをグループ化する意味がある場合にのみタプル引数を使用します。

私はあなたの元のコードをこのように書きます。

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

更新されたコードは、アプローチに最適です。より高速にするには、Yin Zhu answer のような別のアルゴリズムを使用する必要があります。F# が「チェック」関数を末尾再帰にするかどうかを確認するテストを作成しました。

于 2010-01-10T06:04:02.797 に答える
3

変数p は、実際には名前バインディングであり、変数ではありません。名前バインディングの使用は悪いスタイルではありません。そして、それはより読みやすいです。の怠惰なスタイルnextPrimeは優れており、実際にはプログラム全体で各数値を 1 回だけ素数テストします。

私の解決策

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

私は基本的に num を 2、3、4.. から除算し、素数は考慮しません。num から 2 をすべて割ると、4、8 などで割ることができないためです。

この数では、私の解決策はより迅速です:

> 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
于 2010-01-10T04:32:42.990 に答える
1

一時バインディングを使用したコードの方がはるかに読みやすいと思います。他の場合のように、匿名関数を作成してすぐに値に適用することは非常にまれです。一時的な値の使用を本当に避けたい場合、F# でそれを行う最も慣用的な方法は、(|>)演算子を使用して値を無名関数にパイプすることだと思いますが、それでもこれは読みにくいと思います。 .

于 2010-01-10T04:53:22.407 に答える