Scheme 中的 Mandelbrot 集实现非常慢
Mandelbrot set implementation in Scheme is very slow
我正在努力学习 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
那么,是什么让这段代码 运行 这么慢?
提前致谢
这是一个 Common Lisp 变体:
(defun print-brot (zr zc)
(write-char (if (< (+ (* zr zr)
(* zc zc))
2.0d0)
#\@
#\.)))
(defun brot (zr zc cr cc i)
(loop repeat i
for z2r = (- (* zr zr) (* zc zc))
for z2c = (* 2.0d0 zr zc)
until (or (> (abs zr) 1.0d50)
(> (abs zc) 1.0d50))
do (setf zr (+ z2r cr)
zc (+ z2c cc)))
(print-brot zr zc))
(defun linspace (i w)
(/ (- i (/ w 2.0d0)) (/ w 4.0d0)))
(defun brot-grid (w h n)
(terpri)
(loop for i from 0.0d0 by 1.0d0
repeat w do
(loop for j from 0.0d0 by 1.0d0
repeat h do
(brot 0.0d0 0.0d0 (linspace i w) (linspace j h) n))
(terpri)))
注意双浮点常量的使用。同时迭代双浮点数和整数。
运行 它在 SBCL 中未经优化,但已编译为本机代码:
* (time (brot-grid 20 40 20))
........................................
....................@...................
....................@...................
....................@...................
...................@@@..................
.................@@@@@@@................
...................@@@..................
................@@@@@@@@@...............
..............@@@@@@@@@@@@@.............
............@@@@@@@@@@@@@@@@@...........
..............@@@@@@@@@@@@@.............
...............@@@@@@@@@@@..............
..................@...@.................
........................................
........................................
........................................
........................................
........................................
........................................
........................................
Evaluation took:
0.003 seconds of real time
0.002577 seconds of total run time (0.001763 user, 0.000814 system)
100.00% CPU
6,691,716 processor cycles
2,064,384 bytes consed
优化代码意味着:
- 更高的编译器优化设置
- 可能会添加一些类型声明
- 去掉浮动consing
查看您的代码,我认为您正在使用有理数对其进行测试。这意味着非常准确的算术,缺点是您很快就会使用具有巨大大数的有理数作为分子和分母。
确保使用浮点数(我建议使用双浮点数)的一种方法是使用一个中间函数,将所有输入转换为双精度值,以便更容易地输入(比如)0
而不是 0d0
.
一旦您确定使用双精度使其更快,您就可以开始在整个过程中散布类型声明,以使编译器能够为您生成更好的代码。
我正在努力学习 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
那么,是什么让这段代码 运行 这么慢?
提前致谢
这是一个 Common Lisp 变体:
(defun print-brot (zr zc)
(write-char (if (< (+ (* zr zr)
(* zc zc))
2.0d0)
#\@
#\.)))
(defun brot (zr zc cr cc i)
(loop repeat i
for z2r = (- (* zr zr) (* zc zc))
for z2c = (* 2.0d0 zr zc)
until (or (> (abs zr) 1.0d50)
(> (abs zc) 1.0d50))
do (setf zr (+ z2r cr)
zc (+ z2c cc)))
(print-brot zr zc))
(defun linspace (i w)
(/ (- i (/ w 2.0d0)) (/ w 4.0d0)))
(defun brot-grid (w h n)
(terpri)
(loop for i from 0.0d0 by 1.0d0
repeat w do
(loop for j from 0.0d0 by 1.0d0
repeat h do
(brot 0.0d0 0.0d0 (linspace i w) (linspace j h) n))
(terpri)))
注意双浮点常量的使用。同时迭代双浮点数和整数。
运行 它在 SBCL 中未经优化,但已编译为本机代码:
* (time (brot-grid 20 40 20))
........................................
....................@...................
....................@...................
....................@...................
...................@@@..................
.................@@@@@@@................
...................@@@..................
................@@@@@@@@@...............
..............@@@@@@@@@@@@@.............
............@@@@@@@@@@@@@@@@@...........
..............@@@@@@@@@@@@@.............
...............@@@@@@@@@@@..............
..................@...@.................
........................................
........................................
........................................
........................................
........................................
........................................
........................................
Evaluation took:
0.003 seconds of real time
0.002577 seconds of total run time (0.001763 user, 0.000814 system)
100.00% CPU
6,691,716 processor cycles
2,064,384 bytes consed
优化代码意味着:
- 更高的编译器优化设置
- 可能会添加一些类型声明
- 去掉浮动consing
查看您的代码,我认为您正在使用有理数对其进行测试。这意味着非常准确的算术,缺点是您很快就会使用具有巨大大数的有理数作为分子和分母。
确保使用浮点数(我建议使用双浮点数)的一种方法是使用一个中间函数,将所有输入转换为双精度值,以便更容易地输入(比如)0
而不是 0d0
.
一旦您确定使用双精度使其更快,您就可以开始在整个过程中散布类型声明,以使编译器能够为您生成更好的代码。