3

IE、

私はここで何が間違っているのですか？リスト、シーケンス、配列、および制限の仕組みと関係がありますか？

これがセットアップです：私はいくつかの素数を生成しようとしています。10億の素数の10億のテキストファイルがあることがわかります。問題は理由ではありません...問題は、Pythonを使用している人がこの投稿でミリ秒単位で1,000,000未満のすべての素数をどのように計算しているのか...そして次のF＃コードで何が間違っているのですか？

let sieve_primes2 top_number = 
    let numbers = [ for i in 2 .. top_number do yield i ]
    let sieve (n:int list) = 
        match n with
        | [x] -> x,[]
        | hd :: tl -> hd, List.choose(fun x -> if x%hd = 0 then None else Some(x)) tl
        | _ -> failwith "Pernicious list error."
    let rec sieve_prime (p:int list) (n:int list) =  
        match (sieve n) with
        | i,[] -> i::p
        | i,n'  -> sieve_prime (i::p) n'
    sieve_prime [1;0] numbers

FSIでタイマーをオンにすると、100000で4.33秒相当のCPUを取得します...その後、すべてが爆発します。

4

4 に答える 4

5

までの合成数を除外しようとしたため、ふるい機能が遅くなりますtop_number。sqrt(top_number)Sieve of Eratosthenesを使用すると、残りの数が本質的に素数になるまで、そうする必要があります。があるとするとtop_number = 1,000,000、関数は78498フィルタリングのラウンド（までの素数の数1,000,000）を実行しますが、元のふるいはその168回数（までの素数の数1,000）のみを実行します。

最初から素数にできない2を除いて、偶数の生成を避けることができます。さらに、sieve再帰sieve_prime関数にマージすることができます。List.filterまた、の代わりに軽量を使用することもできますList.choose。

上記の提案を組み込む：

let sieve_primes top_number = 
    let numbers = [ yield 2
                    for i in 3..2..top_number -> i ]
    let rec sieve ns = 
        match ns with
        | [] -> []
        | x::xs when x*x > top_number -> ns
        | x::xs -> x::sieve (List.filter(fun y -> y%x <> 0) xs)
    sieve numbers

私のマシンでは、更新されたバージョンは非常に高速で、0.6秒以内に完了しますtop_number = 1,000,000。

于 2012-08-17T23:58:25.037 に答える
4

ここの私のコードに基づく：stackoverflow.com/a/8371684/124259

fsiで22ミリ秒で最初の100万素数を取得します。重要な部分は、おそらくこの時点でコードをコンパイルしていることです。

#time "on"

let limit = 1000000
//returns an array of all the primes up to limit
let table =
    let table = Array.create limit true //use bools in the table to save on memory
    let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
    let mutable curfactor = 1;
    while curfactor < tlimit-2 do
        curfactor <- curfactor+2
        if table.[curfactor]  then //simple optimisation
            let mutable v = curfactor*2
            while v < limit do
                table.[v] <- false
                v <- v + curfactor
    let out = Array.create (100000) 0 //this needs to be greater than pi(limit)
    let mutable idx = 1
    out.[0]<-2
    let mutable curx=1
    while curx < limit-2 do
        curx <- curx + 2
        if table.[curx] then
            out.[idx]<-curx
            idx <- idx+1
    out
于 2012-08-18T00:54:42.893 に答える
2

リスト（@pad）を使用した一般的な試行除算アルゴリズムと、エラトステネスのふるい（SoE）（@JohnPalmerおよび@JonHarrop）を使用したふるい分けデータ構造の配列の選択の両方に関して、いくつかの良い答えがあります。ただし、@ padのリストアルゴリズムは特に高速ではなく、ふるい分け範囲が広い場合は「爆発」します。@ John Palmerの配列ソリューションはやや複雑で、必要以上にメモリを使用し、外部の可変状態を使用するため、プログラムは、C＃などの命令型言語で作成されました。

EDIT_ADD： 以下のコード（行コメント付きの古いコード）を編集して、「イテレータースタイル」をより反映するように一部の関数呼び出しを回避するようにシーケンス式を変更しましたが、速度を20％節約しましたが、それでも反映されません。 「独自の列挙子をロールする」最終的なF＃コードとほぼ同じ速度の真のC＃イテレーターの速度に近づきます。それに応じて、以下のタイミング情報を変更しました。 END_EDIT

次の真のSoEプログラムは、64 Kバイトのメモリを使用して最大100万までの素数をふるいにかけます（奇数を考慮し、パックされたビットBitArrayを使用するため）。 i7 2700K（3.5 GHz）で100万、数行のコードのみ：

open System.Collections
let primesSoE top_number=
  let BFLMT = int((top_number-3u)/2u) in let buf = BitArray(BFLMT+1,true)
  let SQRTLMT = (int(sqrt (double top_number))-3)/2
  let rec cullp i p = if i <= BFLMT then (buf.[i] <- false; cullp (i+p) p)
  for i = 0 to SQRTLMT do if buf.[i] then let p = i+i+3 in cullp (p*(i+1)+i) p
  seq { for i = -1 to BFLMT do if i<0 then yield 2u
                               elif buf.[i] then yield uint32(3+i+i) }
//  seq { yield 2u; yield! seq { 0..BFLMT } |> Seq.filter (fun i->buf.[i])
//                                          |> Seq.map (fun i->uint32 (i+i+3)) }
primesSOE 1000000u |> Seq.length;;

シーケンスランタイムライブラリの非効率性と、関数呼び出しごとに約28クロックサイクルで自身を列挙し、約16の関数呼び出しで戻るため、検出された素数を列挙するために、経過時間のほとんどすべてが最後の2行で費やされます。反復ごと。これは、独自のイテレータをローリングすることで、反復ごとに数回の関数呼び出しに減らすことができますが、コードはそれほど簡潔ではありません。次のコードでは、シービング配列の内容と、オブジェクト式を使用したイテレーターの実装に必要な参照変数以外に、変更可能な状態が公開されていないことに注意してください。

open System
open System.Collections
open System.Collections.Generic
let primesSoE top_number=
  let BFLMT = int((top_number-3u)/2u) in let buf = BitArray(BFLMT+1,true)
  let SQRTLMT = (int(sqrt (double top_number))-3)/2
  let rec cullp i p = if i <= BFLMT then (buf.[i] <- false; cullp (i+p) p)
  for i = 0 to SQRTLMT do if buf.[i] then let p = i+i+3 in cullp (p*(i+1)+i) p
  let nmrtr() =
    let i = ref -2
    let rec nxti() = i:=!i+1;if !i<=BFLMT && not buf.[!i] then nxti() else !i<=BFLMT
    let inline curr() = if !i<0 then (if !i= -1 then 2u else failwith "Enumeration not started!!!")
                        else let v = uint32 !i in v+v+3u
    { new IEnumerator<_> with
        member this.Current = curr()
      interface IEnumerator with
        member this.Current = box (curr())
        member this.MoveNext() = if !i< -1 then i:=!i+1;true else nxti()
        member this.Reset() = failwith "IEnumerator.Reset() not implemented!!!"
      interface IDisposable with
        member this.Dispose() = () }
  { new IEnumerable<_> with
      member this.GetEnumerator() = nmrtr()
    interface IEnumerable with
      member this.GetEnumerator() = nmrtr() :> IEnumerator }
primesSOE 1000000u |> Seq.length;;

上記のコードは、反復ごとの関数呼び出しの数を約16から約3に大幅に減らすため、同じマシンで素数を100万にふるいにかけるのに約8.5ミリ秒かかります。これは、同じスタイルで記述されたC＃コードとほぼ同じ速度です。 。最初の例で使用したF＃のイテレータースタイルが、C＃イテレーターのようにIEnumerableボイラープレートコードを自動的に生成しないのは残念ですが、それがシーケンスの意図であると思います。シーケンス計算式として実装されているため。

現在、CPU時間をはるかに有効に活用するために、主要な結果を列挙するために費やされる時間は半分未満です。

于 2013-08-03T17:52:36.930 に答える
1

私はここで何が間違っているのですか？

%それぞれの可能な値を調べ、それを削除する必要があるかどうかを判断するために使用する異なるアルゴリズムを実装しました。あなたがしていることになっていることは、倍数を削除する固定増分でステップスルーすることです。それは漸近的になります。

リストはランダムアクセスをサポートしていないため、効率的にリストをステップスルーすることはできません。そのため、配列を使用してください。

于 2013-02-10T21:02:58.503 に答える