F# で素数を求める

以前に LINQ で素数を求める (C#) という記事を書きましたが、
その中にある GetPrimeNumbers 関数を F# で書いてみると、次のようになります。

 

Program.fs


open System
open System.Collections.Generic
open System.Diagnostics

module Seq2 =
    let do2 action source =
        seq {
            for x in source do
                action(x)
                yield x
        }

let getPrimeNumbers minValue maxValue =
    (
        new List<int64>(),
        Math.Max(minValue, 2L),
        Math.Max(maxValue, 0L),
        if maxValue >= 0L then (maxValue |> float |> Math.Sqrt |> int64) else 0L
    )
    |> Seq.singleton
    |> Seq.collect (fun (primes, min, max, root_max) ->
        (seq { 2L .. Math.Min(root_max, min  1L) }, seq { min .. max })
        ||> Seq.append
        |> Seq.map (fun i -> (primes, i, i |> float |> Math.Sqrt |> int64)))
    |> Seq.filter (fun (primes, i, root_i) ->
        primes
        |> Seq.takeWhile (fun p -> p <= root_i)
        |> Seq.forall (fun p -> i % p <> 0L))
    |> Seq2.do2 (fun (primes, i, _) -> primes.Add(i))
    |> Seq.map (fun (_, i, _) -> i)
    |> Seq.skipWhile (fun i -> i < minValue)

[<EntryPoint>]
let main argv = 
    let stopwatch = Stopwatch.StartNew()
    let result = (1000000000000L, 1000000001000L) ||> getPrimeNumbers |> Seq.toArray
    stopwatch.Stop()

    result |> Seq.iter (printfn "%A")
    stopwatch.Elapsed.TotalSeconds |> printfn "%A seconds"
    0


 

プログラムを実行します。

実行結果

結果は、C# よりも遅くなりました。
F# は構文糖衣が多く、コンパイル時にクラスに置き換わるものがあるため、
実行時に生成されるオブジェクトが多くなるのが原因であると予想されます。

 

作成したサンプル
PrimeNumbersConsoleF (GitHub)

バージョン情報
.NET Framework 4.5

参照
エラトステネスの篩 – Wikipedia
シーケンス (F#) (MSDN)
LINQ で素数を求める (C#)

カテゴリー: プログラミング言語. タグ: , . 1 Comment »

コメント / トラックバック1件 to “F# で素数を求める”

  1. LINQ で素数を求める (C#) | Do Design Space Says:

    […] F# 版も書きました: F# で素数を求める […]


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。