为什么在Racket代码中for循环如此缓慢

Question

我正在尝试找出数字的最小非约数（https://codegolf.stackexchange.com/questions/105412/find-the-smallest-number-that-doesnt-divide-n）。以下使用“命名 let”版本可以正常工作：

(define (f1 m)
  (let loop ((n 2))
    (cond
      [(= 0 (modulo m n))
       (loop (+ 1 n))]
      [else n])))

我正在进行测试：

(f 24)
(f 1234567)
(f 12252240)
(f 232792560)

以上版本输出：5 2 19 和 23。

然而，下面这个使用内置的 for 循环的版本非常慢，并且在处理更大的数字时会崩溃并出现内存不足的错误：

(define (f2 m)
  (for/first ((i (range 2 m))
              #:when (not (= 0 (modulo m i)))
              #:final (not (= 0 (modulo m i))))
    i))

第二个版本的代码是否存在错误，或者与Racket中的命名let相比，for循环效率较低？

- rnso

---

尝试将 range 替换为 in-range。 - Alexis King

我没想到range和in-range之间会有这么大的区别。除了名称更短以外，range函数有什么优点？为什么要有range函数呢？ - rnso

因为有时你需要一个列表，而不是一个序列。range 生成一个列表，in-range 生成一个序列（并且还与 for 协作以提高迭代性能）。也许 range 也可以进行调整，以便与 for 协作。 - Alexis King

Answer 1

range函数实际上会分配一个列表，所以你的函数时间主要花费在了巨大的列表分配上。使用in-range代替：

(define (f2 m)
  (for/first ([i (in-range 2 m)]
              #:when (not (= 0 (modulo m i)))
              #:final (not (= 0 (modulo m i))))
    i))

请参阅Racket指南中有关for性能部分，了解不同序列形式的相对速度的更多说明。

- Ryan Culpepper

---

差别很大！ - rnso

Answer 2

在我看来，递归通常比循环更适合Racket。我会这样解决问题...

(define start-counter 1)

(define (f number counter)
   (cond [(not (= (modulo number counter) 0)) counter]
         [else (f number (add1 counter))]))

(define (f2 number)
   (f number start-counter))

- Simar Chawla

---

您可以将主函数定义为：(define (f number (counter 1))...；这将为计数器(counter)设置默认值1，因此您不需要第一个和第三个define语句/fn。然而，我问题中的'for'循环之所以慢，显然是由于使用了'range'而不是'in-range'函数。 - rnso