12

Clojure での Sieve of Erathosthene の実装を次に示します (ストリームに関する SICP のレッスンに基づく)。

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

さて、最初の 100 個の素数を取れば問題ありません。

(take 100 primes)

しかし、最初の 1000 個の素数を取ろうとすると、スタック オーバーフローのためにプログラムが中断します。関数ふるいを何らかの方法で変更して末尾再帰になり、それでもアルゴリズムの「ストリームネス」を維持することが可能かどうか疑問に思っていますか?

助けて？

4

1 に答える 1

10

まず、これはエラトステネスのふるいではありません...詳細については私のコメントを参照してください。

第二に、あなたの質問は私が指摘したものの実際の複製ではないので、投票が締め切られたことをお詫びします...私の悪い。

何が起こっているのかの説明

違いはもちろん、インクリメンタルふるいを作成しようとしているという事実にあります。この場合、remove呼び出しが機能する範囲は無限であり、したがって、単にそれを包むことは不可能doallです。解決策は、私が最近かなり頻繁にリンクしているように見える論文からの「実際の」インクリメンタルSoEの1つを実装することです-メリッサE.オニールのエラトステネスの本物のふるい。

この種の特に美しいClojureふるいの実装は、Christophe Grandによって作成されており、興味を持っている可能性のあるすべての人を称賛するためにここで利用できます。読むことを強くお勧めします。

問題の原因については、私が最初にあなたの質問の複製であると思った質問には、あなたに役立つはずの説明が含まれています。こことここを参照してください。繰り返しになりますが、急いで投票が終了して申し訳ありません。

末尾再帰が役に立たない理由

質問では、可能な解決策としてふるい分け関数を末尾再帰にすることに具体的に言及しているので、ここで対処しようと思いました。怠惰なシーケンスを変換する関数は、一般に末尾再帰であってはなりません。

これは覚えておくべき非常に重要なポイントであり、経験の浅いClojure（またはHaskell）プログラマーの多くをつまずかせるポイントです。その理由は、必要な末尾再帰関数は、計算の最後に「準備ができた」ときにのみその値を返すためです。（反復プロセスは、特定の反復の終了時に、値を返すか、次の反復に進むことができます。）対照的に、レイジーシーケンスを生成する関数は、コードのビットをカプセル化するレイジーシーケンスオブジェクトをすぐに返す必要があります。必要に応じて、シーケンスのヘッドまたはテールを生成するように要求できます。

したがって、遅延変換をスタックする問題に対する答えは、末尾再帰を作成するのではなく、変換をマージすることです。この特定のケースでは、カスタムスキームを使用して、優先度付きキューまたはマップに基づいてフィルタリング操作を融合することで、最高のパフォーマンスを得ることができます（詳細については、前述の記事を参照してください）。

于 2010-06-07T19:18:01.863 に答える