7

私はプロジェクトオイラー問題14を怠惰な方法で解決しようとしています。残念ながら、私は不可能なことをしようとしているかもしれません。両方とも怠惰な怠惰なシーケンスを作成しますが、まだ計算されていない値をどういうわけか「先読み」します。

正確さをテストするために私が書いた非遅延バージョンは次のとおりです。

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

これは機能しますが、本当に遅いです。もちろん、私はそれを覚えることができます：

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

しかし、私が本当にやりたかったのは、怠惰なシーケンスの限界を理解するためにかゆみを掻き、次のような関数を書くことでした。

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
                                 (+ 1 (nth lazy-chain (dec (/ n 2)))))
                               (chain (+ n 1)))))]
       (chain 1)))

これから要素をプルすると、n> 2のスタックオーバーフローが発生します。これは、レイジーリストの10番目の要素の値を知るためにn=3で「将来を見据える」必要がある理由を考えると理解できます。 1（* 3 n））=10。

怠惰なリストはメモ化よりもはるかにオーバーヘッドが少ないので、この種のことが、さらに遅延した評価またはキューイングによって何らかの形で可能かどうかを知りたいですか？

4

3 に答える 3

5

続編「未来を見据えて」

未来を見据えたファンキーなシーケンスの例は、次のようになります。

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

（これを壊さずに簡単にする人へのクッキー。:-)）

もちろん、要素の値を決定するために、それ自体がさらに遠い要素の計算を必要とする別の要素に依存する「将来の」要素を調べる必要がある場合は、大惨事は避けられません。

オイラー14

質問からのコードを「将来を見据える」というスキームの根本的な問題は脇に置いて、このアプローチは実際には問題を解決しません。なぜなら、最初から1 上に行くことにした場合は、分岐する必要があるからです。考慮に入れる：10コラッツチェーンのaは、いずれかのルール（にn / 2適用されるルール20または3n + 1から始まるルール3）を適用することで到達する可能性があります。また、チェーンを上向きに構築したい場合は、ルールを逆にして、乗算する2か、減算1して除算する必要があります3（各ステップで、整数を生成するルールを適用します。両方の場合は両方を適用します）。

もちろん、怠惰なリストではなくツリーを作成することもできますが、それは質問のコードスケッチのようには見えないので、最終的にはメモ化することになると思います。

1上記は、最終的なエントリが指定された制限を下回っている間に、どの「チェーン構築ルール」が開始して最長のチェーンを生成する可能性が高いかについて推測できる可能性があるという発言で修飾されます。その場合は、おそらくそれが正しいことを証明してから、直接実装する必要があります（からloop/recurで開始1）。証拠がなければ、問題を解決したとは言えません。

于 2010-06-10T06:25:40.587 に答える
1

私は考えiterateておりtake-while、いくつかの助けになる可能性があります（このコードは将来を見据えていませんが）：

(defn next-collatz [n]
  (cond
    (= n 1) 1
    (odd? n) (+ 1 (* 3 n))
    true (/ n 2)))

(defn collatz-seq [n]
  (iterate next-collatz n))

(defn collatz [n]
    (take-while #(not (= % 1)) (collatz-seq n)))

user> (collatz 100)
=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2)
于 2010-06-14T15:15:41.333 に答える
0

以下は、私にコラッツ値の怠惰なシーケンスを与えます。私のマシンのマイクロベンチマークでは、メモ化されたソリューションをわずかに上回っています。欠点としては、再帰が深すぎて100万のコラッツチェーンの長さを見つけることができず、スタックは100,000から1,000,000の要素の間のどこかでオーバーフローしますが、少しの作業とで解決できますrecur。

 (defn collatz [n cache]
   (if-let [v (cache n)]
     [v cache]
     (let [[p cache] (if (odd? n)
                       (collatz (+ 1 (* 3 n)) cache)
                       (collatz (/ n 2) cache))]
       [(inc p) (assoc cache n (inc p))])))

 (def lazy-collatz
      (map first (iterate (fn [[v cache n]]
                            (concat (collatz n cache) [(inc n)]))
                          [1 {1 1} 2])))

それでも、それはまだ私が望んでいたものではありません。ハッシュマップなしのこれと同じ機能です。Michalの優れたコメントと再帰ツリーを構築するという概念を考えると、ここで私が望んでいたのは、怠惰なシーケンスではなく、ある種の怠惰な再帰データ構造、おそらくツリーでした。そのようなデータフロー技術は存在しますか？

私の当初のアイデアは、未知の値（n）から「遅延」のチェーンを構築し、既知の数（1など）に達するまで再帰を続け、その後、再帰がほどけるにつれて、レイジーデータ構造に実際の値を入力することでした。レイジーシーケンスをレイジーリンクリストと考えると、私が欲しかったのは、コラッツのルールを使用してデータの依存関係を自動的に検出するレイジー無限長のベクトルまたはツリーでした。この問題にはハッシュマップで十分ですが、ある意味では、私が望んでいたものの近似にすぎません。つまり、ベクトル内の要素にデータを入力する方法にルールが適用された遅延データフローベクトルです。

非常に難しい課題：ハッシュマップを使用せずに、このような怠惰なツリー/ベクトルを簡単に表現する方法を誰かが考えられますか？

于 2010-06-10T12:45:15.527 に答える