プロジェクト オイラー問題 14 を「先読み」する遅延シーケンス

Question

解決しようとしています プロジェクトオイラー問題 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。

遅延リストはメモ化よりもオーバーヘッドがはるかに少ないため、さらに遅延した評価またはキューを介してこの種のことが何らかの方法で可能かどうか知りたいです。

Answer 1

以下は、コラッツ値の遅延シーケンスを示しています。私のマシンのマイクロベンチマークでは、メモ化されたソリューションをわずかに上回っています。欠点としては、再帰が深すぎて 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 など) に達するまで再帰を続け、その後巻き戻して、再帰が巻き戻されるときに遅延データ構造に実際の値を設定することでした。遅延シーケンスを遅延リンク リストと考えると、私が望んでいたのは、コラッツ ルールを使用してデータの依存関係を自動的に検出する遅延無限長のベクトルまたはツリーです。この問題にはハッシュマップで十分でしたが、これはある意味、私が望んでいたものの近似にすぎません。ベクトル内の要素を設定する方法にルールが適用された遅延データフロー ベクトル。

エクストラハードチャレンジ:ハッシュマップを使用せずにこのような遅延ツリー/ベクトルを簡単に表現する方法を誰かが考えられますか?

Answer 2

続編「未来を見つめて」

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

(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 Collat​​z チェーン内の は、どちらかのルール ( n / 2 に適用されるルール 20 または 3n + 1 から始まるルール 3）。また、チェーンを上向きに構築したい場合は、ルールを逆にして、次の値を乗算する必要があります。 2 または減算する 1 で割ります 3 (各ステップで、整数を生成するルールを適用します。あるいは、両方が生成する場合は両方とも適用します)。

もちろん、構築することもできます 木, 、怠惰なリストではなく、しかしそれは質問にあるコードスケッチとはまったく似ていないでしょうし、最終的にはそれをメモ化することになると思います。

上記は、どの「チェーン構築ルール」が次から始まる最長のチェーンを生成する可能性が高いかについての推測があるかもしれないというコメントで修飾されます。 1 ただし、最終エントリは指定された制限未満に留まります。その場合は、おそらく それが正しいことを証明する そしてそれを直接実装します( loop / recur から始まる 1);証拠がなければ、実際に問題を解決したと主張することはできません。

Answer 3

私は（このコードは、将来に見ていませんが）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)