15

そのため、このコードが素数を生成する方法を正確に解明するために何時間も費やしました。

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
   ps.takeWhile{j => j * j <= i}.forall{ k => i % k > 0});

私はいくつかのprintlnsなどを使用しましたが、明確にするものは何もありません。

これは私がコードが行うと思うことです：

/**
 * [2,3] 
 * 
 * takeWhile 2*2 <= 3 
 * takeWhile 2*2 <= 4 found match
 *      (4 % [2,3] > 1) return false.
 * takeWhile 2*2 <= 5 found match
 *      (5 % [2,3] > 1) return true 
 *          Add 5 to the list
 * takeWhile 2*2 <= 6 found match
 *      (6 % [2,3,5] > 1) return false
 * takeWhile 2*2 <= 7
 *      (7 % [2,3,5] > 1) return true
 *          Add 7 to the list
 */

しかしj*j、リストを2 * 2に変更すると、まったく同じように動作すると想定され、stackoverflowエラーが発生します。

私は明らかにここで根本的な何かを見逃しており、私が 5 歳のときのようにこれを説明してくれる人を実際に使うことができます。

どんな助けでも大歓迎です。

4

3 に答える 3

27

手続き的/命令的な説明を求めることが、ここで理解を得る最善の方法であるかどうかはわかりません。ストリームは関数型プログラミングに由来し、その観点から最もよく理解されます。あなたが与えた定義の重要な側面は次のとおりです。

  1. 怠け者です。ストリームの最初の要素以外は、要求されるまで何も計算されません。5 番目の素数を要求しないと、計算されません。

  2. 再帰的です。素数のリストは、それ自体で定義されます。

  3. 無限です。ストリームには、無限の数の要素を持つシーケンスを表すことができるという興味深い特性があります (それらは怠け者であるため)。Stream.from(3)はこの例です: リスト [3, 4, 5, ...] を表します。

あなたの定義が素数列を計算する理由を理解できるかどうか見てみましょう。

定義は で始まります2 #:: ...。これは、数列の最初の数が 2 であることを示しているだけです。

次の部分では、残りの素数を定義します。3 ( ) から始まるすべてのカウント数から始めることができますがStream.from(3)、これらの数の束 (つまり、すべての合成数) を除外する必要があることは明らかです。それでは、それぞれの数字について考えてみましょうi。iが小さい素数の倍数でない場合は、i素数です。つまり、未満の iすべての素数に対して、 の場合は素数です。Scala では、これを次のように表現できます。kii % k > 0

nums.filter(i => ps.takeWhile(k => k < i).forall(k => i % k > 0))

ただし、実際にはすべての小さい素数をチェックする必要はありません。実際にチェックする必要があるのは、平方が以下の素数だけですi(これは数論からの事実です*)。したがって、代わりに次のように書くことができます

nums.filter(i => ps.takeWhile(k => k * k <= i).forall(k => i % k > 0))

だから私たちはあなたの定義を導き出しました.

ここで、たまたま最初の定義 ( を使用k < i) を試した場合、うまくいかないことがわかります。なぜだめですか？これは再帰的な定義であるという事実に関係しています。

数列で 2 の後に来るものを決定しようとしているとします。この定義は、最初に 3 が属するかどうかを判断するように指示しています。そうするために、3 以上の最初の素数までの素数のリストを検討します ( takeWhile(k => k < i))。最初の素数は 2 で、これは 3 未満です。これまでのところ、問題ありません。しかし、まだ 2 番目の素数がわからないので、計算する必要があります。では、まず 3 が属しているかどうかを確認する必要があります... BOOM!

* nある数が合成数である場合、その因数のいずれかの 2 乗が より小さいか等しくなければならないことは簡単にわかりnます。が複合の場合n、定義によりn == a * b、ここで( 2 つの要素を適切にラベル付けするだけで1 < a <= b < n保証できます)。a <= bからa <= bということa^2 <= a * bになるので、 ということになりますa^2 <= n。

于 2013-03-24T07:11:19.517 に答える
3

あなたの説明はほとんど正しいですが、間違いは 2 つだけです。

takeWhile最後にチェックされた要素は含まれません:

scala> List(1,2,3).takeWhile(_<2)
res1: List[Int] = List(1)

psには常に 2 と 3 しか含まれていないと想定しますが、Streamは遅延しているため、新しい要素を追加することができます。実際、新しい素数が見つかるたびにそれが追加さpsれ、次のステップでtakeWhileこの新しく追加された要素が考慮されます。Streamここで、a の末尾は必要な場合にのみ計算されるため、true と評価されるtakeWhile前にそれを確認できないことを覚えておくことが重要です。forall

これら2つのことを念頭に置いてください。これを考え出す必要があります。

ps = [2]
i = 3
  takeWhile
    2*2 <= 3 -> false
  forall on []
    -> true
ps = [2,3]
i = 4
  takeWhile
    2*2 <= 4 -> true
    3*3 <= 4 -> false
  forall on [2]
    4%2 > 0 -> false
ps = [2,3]
i = 5
  takeWhile
    2*2 <= 5 -> true
    3*3 <= 5 -> false
  forall on [2]
    5%2 > 0 -> true
ps = [2,3,5]
i = 6
...

これらの手順はコードの動作を説明していますが、完全に正しいとは言えませんStream。これは、 falsexs.takeWhile(f)の時点まですべての値を呼び出すとf、一度に計算されるわけではないことを意味します-それらは、forallそれらを見たいときに計算されます(確実にtrueになる前にすべての要素を調べる必要があるのはここで唯一の関数であるため) 、 false の場合は早期に中止できます)。ここでは、どこでも怠惰が考慮される場合の計算順序を示します (例は 9 のみを参照)。

ps = [2,3,5,7]
i = 9
  takeWhile on 2
    2*2 <= 9 -> true
  forall on 2
    9%2 > 0 -> true
  takeWhile on 3
    3*3 <= 9 -> true
  forall on 3
    9%3 > 0 -> false
ps = [2,3,5,7]
i = 10
...

forallfalse と評価されると中止されるためtakeWhile、残りの可能な要素を計算しません。

于 2013-03-24T02:32:27.237 に答える
1

そのコードは、（少なくとも私にとっては）読みやすいように、いくつかの変数の名前を示唆的に変更した方が簡単です。

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
   ps.takeWhile{p => p * p <= i}.forall{ p => i % p > 0});

これは非常に自然に左から右に読みます。

素数は2であり、 2乗が を超えないすべての素数が均等に割り切れないi(つまり、ゼロ以外の剰余がない) 3以上の数です。 pii

真の再帰的なやり方で、この定義が増加し続ける素数の流れを定義するものであると理解するには、そうであると仮定します。その仮定から、矛盾は生じないことがわかります。つまり、定義の真実が成り立ちます。

ps その後の唯一の潜在的な問題は、ストリームが定義されているときにストリームにアクセスするタイミングです。最初のステップとして、どこかから魔法のように別の素数のストリームが提供されたと想像してください。次に、定義の真偽を確認した後、アクセスのタイミングが適切であることを確認します。つまり、ps定義される前の領域にアクセスしようとはしません。それは定義を行き詰まらせ、非生産的にします。

どこかで（どこかは覚えていませんが）次のような文章を読んだことを覚えています。生徒と魔法使いの会話です。

  • 生徒:素数はどれ?
  • 魔法使い: ええと、最初の素数は何ですか?
  • s:はい、それは2です。
  • w:わかりました (すぐに2を紙に書き留めます)。そして、次はどうですか？
  • s:そうですね、次の候補は3です。平方がそれを超えない素数で割られるかどうかを確認する必要がありますが、素数が何であるかはまだわかりません!
  • w:心配しないで、あげるよ。それは私が知っている魔法です。やっぱり私は魔法使いです。
  • s:では、最初の素数は何ですか?
  • w: (一枚の紙を一瞥する) 2 .
  • s:よし、その二乗は既に 3 よりも大きい...だまされた! .....

コードの疑似コード1翻訳を次に示します。部分的に右から左に読み、明確にするためにいくつかの変数の名前を再度変更します ( p「プライム」を使用)。

ps = 2 : filter (\i-> all (\p->rem i p > 0) (takeWhile (\p->p^2 <= i) ps)) [3..]

これも

ps = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p->p^2 <= i) ps]]

これは、リスト内包表記を使用すると、もう少し視覚的に明らかです。andブール値のリスト内のすべてのエントリが( 「for」、「 drawing from」、「that」、「lambda of 」とTrue読みます) であることを確認します。|<-,(\p-> ...)p

つまり、は 2 の遅延リストであり、そのようなストリームから引き出されたすべてのそのような から引き出された数については、それは真です。これは実際には最適な試行分割アルゴリズムです。:)ps i[3,4,5,...]ppsp^2 <= ii % p > 0

もちろん、ここには微妙な点があります。リストには制限がありませpsん。「肉付け」されたまま使用します（もちろん、怠け者だからです）。ps が から取得されるとps、その終わりを過ぎて実行される可能性があります。その場合、終了しない計算 (「ブラック ホール」) が発生します。上記の定義では、これは不可能であることが起こります (そして ⁄ は数学的に証明できる必要があります)。2 は無条件に入れpsられるので、そもそも何かが入っています。

しかし、「単純化」しようとすると、

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- takeWhile (\p->p < i) bad]]

2: 3 を候補として考えると、2takeWhile (\p->p < 3) badの次の数を要求しbadますが、そこにはまだ数がありません。それは「自分より先にジャンプ」します。

これは「固定」されています

bad = 2 : [i | i <- [3..], and [rem i p > 0 | p <- [2..(i-1)] ]]

しかし、それははるかに遅い試行分割アルゴリズムであり、最適なものからはほど遠いものです。

--

1 (実際には、 Haskell、その方が簡単です:))

于 2013-03-24T10:00:26.467 に答える