如何在 Clojure 中构建惰性完美数序列？

Question

我试图通过这种方式找到完全数列表：

(defn classify [num] 
  (let [factors (->> (range 1 (inc num))
                     (filter #(zero? (rem num %))))
        sum (reduce + factors)
        aliquot-sum (- sum num)]
    (cond
      (= aliquot-sum num) :perfect
      (> aliquot-sum num) :abundant
      (< aliquot-sum num) :deficient)))

(defn is-p [n] 
  (= :perfect (classify n)))

(defn list-perfect [n]
  (filter is-p (range 1 (inc n))))

问题：

如何构建惰性完全数序列，以便我可以使用 (take n ...) 轻松获得列表。
这段代码是否地道且高效？有什么改进吗？

提前致谢。

Answer 1

list-perfect 由于您使用 filter:

已经很懒了

(filter pred coll)

Returns a lazy sequence of the items in coll for which (pred item) returns true. pred must be free of side-effects.

代码是否惯用可能是一个见仁见智的问题（因此是题外话），但从我的角度来看它看起来已经足够好了。

Answer 2

你的算法效率很低，是O(n)。

为了快速获胜，您可以立即将范围缩小一半，因为您永远不会有大于您正在测试的数字除以 2 的因子。

所以改成：

(defn classify [num] 
  (let [factors (->> (range 1 (max 2 (inc (quot num 2))))
  ;; ...

但是... 您可以将其更改为 O(sqrt n)，这样速度会快很多。请参阅下面的时间安排。

真正的效率是注意到因子成对 [x (quot num x)] 然后只检查第一个 (sqrt num) （或稍微超过）：

(defn perfect? [n]
  (let [r (range 2 (+ 2 (int (Math/sqrt n))))
        s (set (mapcat #(if (zero? (rem n %))
                          [% (quot n %)])
                       r))
        t (reduce + 1 s)]
    (= n t)))

我已将其拆分为单独的计算，以便您可以验证每个阶段。

范围可以从 2..((sqrt n) + 2) 减少，并用 1 初始化减少（它始终是一个因子）。

这将问题从 O(n) 更改为 O(sqrt n)，因此，如果您检查的是大数字，则会产生巨大差异。

这里有一些例子，我的 MBP 上的 n 值较大：

         n            "n/2"      "sqrt n"
      33550336       1,172.5ms     2.85ms
    8589869056     274,346.6ms    16.76ms
  137438691328     didn't time    44.27ms

因此，对于第 6 个完全数，使用根版本的速度提高了 16,369 倍。有关详细信息，请参阅 http://en.wikipedia.org/wiki/List_of_perfect_numbers。

编辑：

为什么是 (int (root n)) + 2？为什么是`[x (quot n x)]?

当你计算出一个数n的因数时，如果你找到一个（比如，a），那么n/a也是一个因数（称之为b）因为 n = a * b

例如查看 28，第一个相关因子是 2，显然 28/2 = 14 也是一个因子。所以你不需要检查 14，你已经知道这是一个因素，因为 2 是。

当我们从 2 开始逐步检查数字时，我们偶然发现更高的数字在下降：

2 is a factor, 28 / 2 = 14 -> [a, b] = [2, 14]
4 is a factor, 28 / 4 = 7  -> [a, b] = [4,  7]
7 is a factor, 28 / 7 = 4  -> [a, b] = [7,  4] - wait a minute...

这里的[a,b]对是mapcat函数中的[% (quot n %)]，例如当范围当前正在迭代值 2 时，则 % 在函数内部是 2，因此 (quot n %) 是 (quot 28 2)，即 14，因此 [% (quot n %)] 只是向量 [2 14]，然后在将其展平为 2 和 14 作为值后添加到集合中。后来，当范围值为 4 时，[% (quot n %)] 就是 [4 (quot 28 4)] 即 [4 7]，并且再次被 mapcat 扁平化为数字 4 和 7.

所以我们将每对数字（通过 mapcat 展平）添加到我们的集合中，包括数字 1，最后得到 #{1 2 14 4 7}，它们是 28 的因数。（实际上，我不知道将 1 放入集合中，因为我不需要，而是从 1 开始求和减少，这是相同的效果）。

但他们在什么时候转身？即我们什么时候知道 [7,4] 已经包含在集合中作为 [4,7]?

很明显是a > b，因为在找最小数的时候总是找最大数，所以到这里就可以结束了。

但这一点是什么？很简单，如果一个完全数是一个平方数，那么a和b就会相等，即a*a = n，所以a = sqrt(n).

因此我们需要检查的a的最大值是大于n的根的整数。

例如对于 28，sqrt(28) = 5.292，所以我们必须检查 6 以确保我们包含了可能是具有成对因子的因子的最小数字。

所以我们需要 (int (sqrt n)) + 1.

我总是这样做，以防根计算为 1.9999999999... 并以错误的方式舍入，因此再添加 1 可确保消除任何舍入错误。

但是在一个范围内，如果你想包括那个数字，你必须再给它加 1（范围降低高数字，（范围 6）=（0 1 2 3 4 5）），这就是为什么将 2 添加到值：1 表示范围，1 以确保它在向下舍入的根之上。

不过，在说完这些之后，我已经测试了最大为 2305843008139952128 的完美数字，它使用 +1 而不是 +2，但这并不是一个巨大的节省。可能是因为我检查的完美数字中没有一个接近完美平方，所以 (int (sqrt n)).

中没有舍入误差

如果您对完全数感兴趣，我建议您阅读 http://britton.disted.camosun.bc.ca/perfect_number/lesson1.html

如何在 Clojure 中构建惰性完美数序列？

How to build a lazy sequence of perfect number in Clojure?

clojure