7

我正在尝试以一种懒惰的方式解决Project Euler 问题 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。

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

4

3 回答 3

5

一个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 向上，则需要进行分支考虑到：10Collat​​z 链中的 a 可能通过应用任一规则（n / 2应用到20的规则或3n + 1从 开始的规则3）得到。此外，如果您希望向上构建链，您应该颠倒规则并乘以2或减去1并除以3（在每一步应用产生整数的规则 - 或者如果两者都这样做，则可能两者兼而有之）。

当然，您可以构建一个tree，而不是一个惰性列表，但这看起来不像问题中的代码草图，我希望您最终能记住这件事。

上面要说明的是，您可能会猜想哪个“链构建规则”可能会从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

下面给了我一个懒惰的 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])))

然而，这仍然不是我想要的：没有 hashmap 的相同功能。考虑到 Michal 的出色评论和构建递归树的概念，我想我在这里想要的不是惰性序列，而是某种惰性递归数据结构，可能是一棵树。是否存在这样的数据流技术？

我最初的想法是从未知值 (n) 构建“延迟”链，该链继续递归，直到它们达到已知数字（如 1），然后展开，在递归展开时用实际值填充惰性数据结构。如果我们将惰性序列视为惰性链表，我想要的是一个惰性无限长度向量或树，它可以使用 Collat​​z 规则自动找出其数据依赖关系。哈希图足以解决这个问题，但在某种意义上它只是我想要的一个近似值：一个惰性数据流向量，其规则应用于如何填充向量中的元素。

额外的困难挑战：任何人都可以想出一种方法来轻松表示这种惰性树/向量而不使用哈希图吗？

于 2010-06-10T12:45:15.527 回答