recursion - Scheme 中的 Mandelbrot 集实现非常慢

Question

我正在尝试学习 Lisp/Scheme，我尝试在其中实现一个非常简单的 mandelbrot 集来练习。我遇到的问题是代码运行非常非常慢。起初我以为这是因为我使用的是递归而不是命令式循环，但我尝试在 python 中重写或多或少相同的代码(包括递归)(它甚至没有尾调用优化)，它运行了非常流畅

所以我想知道我的代码中是否缺少明显的东西，以及我可以做些什么来让它运行得更快。

这是 Scheme (racket) 中的代码片段。我也在 SBCL 中做了几乎相同的事情，而且速度相当

#lang racket

(define-syntax dotimes 
   (syntax-rules () 
     ((_ (var n res) . body) 
      (do ((limit n) 
           (var 0 (+ var 1))) 
          ((>= var limit) res) 
        . body)) 
     ((_ (var n) . body) 
      (do ((limit n) 
           (var 0 (+ var 1))) 
          ((>= var limit)) 
        . body))))

(define (print-brot zr zc)
  (if (< (+ (* zr zr) (* zc zc)) 2)
      (display "@")
      (display ".")))

(define (brot zr zc cr cc i)
  (if (= i 0)
      (print-brot zr zc)
      (let ((z2r (- (* zr zr) (* zc zc))) (z2c (* 2 zr zc)))
        (brot (+ z2r cr) (+ z2c cc) cr cc (- i 1)))))

(define (linspace i w)
  (/ (- i (/ w 2)) (/ w 4)))

(define (brot-grid w h n)
  (dotimes (i w)
           (dotimes (j h)
                    (let ((x (linspace i w)) (y (linspace j h)))
                      (brot 0 0 x y n)))
           (newline)))

(brot-grid 40 80 20)

(我希望代码块不要太密集，很难把它剥离成更简单的东西)

此外，我知道 Scheme 和 Common Lisp 内置了复数，但我想使用常规实数对其进行测试，我认为这不是它运行如此缓慢的原因。

brot函数的参数“i”是迭代次数，brot-grid的参数“n”也是每个点使用的迭代次数。当我将它设置为大于 10 时，代码需要永远运行，这似乎不正常。所用时间的增加似乎也不是线性的，例如在我的机器上 n = 10 只需要大约一秒钟，但 n = 15 需要几分钟，甚至在 n = 20 时还没有完成

那么，是什么让这段代码运行如此缓慢？

提前致谢

Answer 1

查看您的代码，我认为您正在使用有理数对其进行测试。这意味着非常准确的算术，缺点是您很快就会使用具有巨大大数的有理数作为分子和分母。

确保使用 float (我建议使用双 float )的一种方法是使用一个中间函数将所有输入转换为 double 值，以便更轻松地键入(比如)0 而不是 0d0。

一旦确定使用 double 使其更快，您就可以开始在整个过程中散布类型声明，以使编译器能够为您生成更好的代码。