2

Sieve of eulerは、 Sieve of Eratosthenesよりも漸近的な複雑さを備えており、命令型言語で簡単に実装できます。

ストリームを使ってエレガントに実装する方法があるかどうか疑問に思っています。素数についてhaskellwikiを確認しましたが、2つの実装はそのwikiの他のふるい（試行除算でさえ！）よりも数百倍遅いです。

だから私は自分で書こうとします：

{-sieve of Euler-}
primesEU = 2:sieve [3,5 ..] where
    sieve (p:i:xt) = p:(sieve (i:xt) `minus` (lps i)) where
        lps i = map (i*) (takeWhile' (\p->(p<i)&&(mod i p /= 0)) primesEU)

takeWhile'::(t->Bool)->[t]->[t]
takeWhile' p [] = []
takeWhile' p (x:xs) = case (p x) of
    True  -> x:takeWhile' p xs
    False -> [x]

minus::(Ord t) => [t]->[t]->[t]
minus [] _ = []
minus xs [] = xs 
minus xs@(x:xt) ys@(y:yt) 
                      |x<y  = x:(minus xt ys)
                      |x==y = minus xt yt
                      |x>y  = minus xs yt

minusに似てminusいData.List.Ordます。

takeWhile'に似てtakeWhileいますが、わずかな違いがありtakeWhileます。述語を満たさない最初の要素を削除します。takeWhile'それを取るでしょう。

lsp iiの積の有限ストリームを返し、iの最小素因数以下を素数にします。

悲しいことに、私の実装は信じられないほど遅くなります...そして私は犯人を見つけることができません。

とにかく、ストリーム処理スタイルでオイラーの効率的なふるいを実装することは可能ですか？または、アルゴリズムには、ストリームの性質に対して固有の影響がありますか？

4

1 に答える 1

5 
primesEU = 2:sieve [3,5 ..] where
    sieve (p:i:xt) = p:(sieve (i:xt) `minus` (lps i)) where
        lps i = map (i*) (takeWhile' (\p->(p<i)&&(mod i p /= 0)) primesEU)

まず第一に、実装は正しくありません、それは9プライムを考慮します。私はあなたがsieve (i:xt) `minus` lps pそこを意味したのではないかと思います。

次に、ふるいにかけられたリストには奇数のみが含まれるためtail primesEU、inlpsに制限できます。これにより、わずかな違いが生じます。

では、ここで何が起こっているのでしょうか。

その要点（私はすぐに夕食に出かけます、私が戻ったときに拡大します）は、各素数が[よりも小さい奇数（）によって作成されたpすべての呼び出しをバブルする必要があるということです前]。それはレイヤーであり、それぞれが1ステップのコストがかかります。minus>= 3pminus(p-3)/2

したがって、一定の因子と合成はさておき、素数の<= nコストを生成しますO(∑ p)。ここで、合計は素数を超えて、以下になりnます。それはO(n²/log n)です。

の評価のいくつかのステップに従ってみましょうsieve [3,5 .. ]。簡潔にするために、私はs kリストsieve [k, k+2 ..]とminusで示し(\\)ます。修正された定義を使用します

sieve (k:ks) = k : (sieve ks `minus` lps k)

それは9プライムを考慮していません。倍数のリストをすぐに展開します。これにより、作業が多少削減されます。我々が得る

 (:)
 / \
3  (\\)
   /  \
 s 5  [9]

すぐに、そして3つは直接消費することができます。その後minus、右側のサブツリーをトッピングするには、s 5それが空であるかどうかを判断するのに十分な評価が必要です。

   (\\)
   /  \
 (:)  [9]
 / \
5  (\\)
   /  \
 s 7  [15,25]

それは1つのステップで行われます。（次に、空かどうかを判断する必要がありますlps 3。同様に後で、のメンバーごとにlps k1つのステップしかないため、無視できます。）次にminus、5を一番上にバブルして、

   (:)
   / \
  5  (\\)
     /  \
  (\\)  [9]
  /  \
s 7  [15,25]

さて、5が消費された後、トップの右の子を(:)拡張する必要があります

      (\\)
      /  \
   (\\)  [9]
   /  \
 (:)  [15,25]
 / \
7  (\\)
   /  \
 s 9  [21,35,49]

5の倍数を超えて7を移動するための1つの比較

     (\\)
     /  \
   (:)  [9]
   / \
  7  (\\)
     /  \
  (\\)  [15,25]
  /  \
s 9  [21,35,49]

そしてもう1つ、3の倍数を超えて持ち上げます

      (:)
      / \
     7  (\\)
        /  \
     (\\)  [9]
     /  \
  (\\)  [15,25]
  /  \
s 9  [21,35,49]

コンポジットの過去2つのリストを7つ移動した後、使用できるようになりました。その後、(:)ここのトップレベルの右側のサブツリーをさらに評価して、次のプライム（存在する場合）を決定する必要があります。評価は、次の候補を提供する(\\)に到達するために、ツリーの3つのレベルをステップダウンする必要があります。s 9

         (\\)
         /  \
      (\\)  [9]
      /  \
   (\\)  [15,25]
   /  \
 (:)  [21,35,49]
 / \
9  (\\)
   /  \
 s 11 [27]

その候補者は、最終的にそれを排除するminusに到達するために、2つのesを超えて持ち上げられる必要がありますminus

        (\\)
        /  \
     (\\)  [9]
     /  \
   (:)  [15,25]
   / \
  9  (\\)
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

        (\\)
        /  \
      (:)  [9]
      / \
     9  (\\)
        /  \
     (\\)  [15,25]
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

これで、minus缶は初めてその作業を行うことができ、

           (\\)
           /  \
        (\\)  []
        /  \
     (\\)  [15,25]
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

（xs `minus` []上部のは、最初の引数が空でないと判断された後にのみ空のリストを削除します。最初の2つの方程式を入れ替えるminusと変更されますが、必要な手順の違いはわずかです）。次に、評価はツリーの4つのレベルをステップダウンして、次の候補を生成する必要があります（11）。minusその候補者は、トップに達するまで4を超えて持ち上げる必要があります。その過程で1つminusがツリーから削除されるため、次の候補（13）は、5（）ではなく、ツリーの4レベル下でのみ生成されます。したがって、消費されるようにトップに移動する(13-3)/2ステップ数です。完全でpはありません(p-3)/2が、それほど多くはありません。

の最後の要素は、lps k常に最小の素因数の2乗で割り切れkます。これらはすべて奇数であるため、最大で

1/2*(n/3² + n/5² + n/7² + n/11² + ...) ~ n/10

到達時に削除できるリストn（平方プライム除数を持つすべての数と、複数回ある数をカウントするため、いくつか少なくなります）。

したがって、問題は、各プライムがツリーの奥深く、少なくともp*0.4上からレベルで生成されることです。つまりp、消耗品にするために上に持ち上げるには、少なくともp*0.4ステップが必要であり、倍数のリストを作成するために必要な作業を数えずに、基本的に2次の全体的な複雑さを与えます。

ただし、実際の動作は最初は悪く、100000から200000の間の領域で素数を計算すると、2次動作に近づきます。限界では、2次モジュロ対数因子になるはずですが、待つ忍耐力はないと思います。百万か二。

とにかく、ストリーム処理スタイルでオイラーの効率的なふるいを実装することは可能ですか？または、アルゴリズムには、ストリームの性質に対して固有の影響がありますか？

それが不可能であることを証明することはできませんが、それを効率的に実装する方法はわかりません。素数のストリームを生成することとしても、与えられた制限まで素数のリストを生成することとしても。

エラトステネスのふるいを効率的にするのは、それがすでに小さな素数の倍数として消されているかどうかを気にせずに、素数の次の倍数に到達するのは簡単です（インデックスに追加するだけです）p。2*p複数の交差点を回避するために必要な作業は、複数の交差点の作業よりもはるかに多くなります。

于 2012-12-16T17:17:04.530 に答える