欧拉计划问题 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 的堆栈溢出，如果您考虑为什么需要在 n=3 处“展望未来”才能知道惰性列表中第十个元素的值，这是可以理解的，因为 (+ 1 (* 3 n)) = 10。

由于惰性列表的开销比记忆少得多，我想知道这种事情是否可以通过更延迟的评估或排队以某种方式实现？

Answer 1

下面给了我一个 collat​​z 值的惰性序列。在我的机器上的微基准测试中，它稍微击败了记忆的解决方案。缺点是，它递归得太深，无法找到 100 万条 collat​​z 链长度，并且堆栈在第 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），然后展开，在递归展开时用实际值填充惰性数据结构。如果我们将惰性序列视为惰性链表，那么我想要的是一个惰性无限长度向量或树，它可以使用 Collat​​z 规则自动找出其数据依赖性。哈希图足以解决这个问题，但从某种意义上说，它只是我想要的近似值：惰性数据流向量，其中应用了如何填充向量中的元素的规则。

超难挑战:有人能想出一种在不使用哈希图的情况下轻松表示这种惰性树/向量的方法吗？

Answer 2

一个seq“展望未来”

展望未来的时髦 seq 的示例可能如下所示：

(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 并向上走, ，您需要考虑分支：A 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)