Mandelbrot-Set-Implementierung in Scheme ist sehr langsam

Question

Ich versuche, Lisp/Scheme zu lernen, und ich versuchte, eine sehr einfache Version des Mandelbrot-Set darin zu implementieren, um Praxis zu bekommen. Das Problem, auf das ich stieß, ist, dass der Code sehr, sehr langsam läuft. Zuerst dachte ich, es wäre, weil ich Rekursion anstelle von Imperativ-Schleifen verwendete, aber ich habe versucht, mehr oder weniger den gleichen Code (Rekursion eingeschlossen) in Python (der nicht einmal Tail-Call-Optimierung hat) zu schreiben, und es lief sehr glatt

So frage ich mich, ob es etwas offensichtlich ist, das ich in meinem Code vermisse und was ich tun könnte, um es schneller laufen zu lassen.

Hier ist das Code-Snippet in Scheme (Racket). Ich habe auch so ziemlich die gleiche Sache in SBCL und die Geschwindigkeit war vergleichbar

#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) 

(ich der Codeblock hoffen, nicht zu clustery ist, war es schwer, es zu etwas einfacher strippen)

Auch Ich weiß, Scheme und Common Lisp haben komplexe Zahlen eingebaut, aber ich wollte es mit regulären reellen Zahlen testen, ich glaube nicht, dass dies der Grund ist, warum es so langsam läuft.

Der Parameter "i" der Brot-Funktion ist die Anzahl der Iterationen, und der Parameter "n" von Brot-Grid ist auch die Anzahl der Iterationen für jeden Punkt. Wenn ich es auf mehr als 10 setze, dauert der Code für immer, was nicht normal erscheint. Die Zunahme der Zeit scheint auch nicht linear zu sein, zum Beispiel dauert es nur ungefähr eine Sekunde auf meiner Maschine mit n = 10, dauert aber mehrere Minuten mit n = 15 und endet nicht einmal mit n = 20

Also, was macht diesen Code so langsam?

Vielen Dank im Voraus

Answer 1

Mit Blick auf Ihren Code, ich denke, Sie testen es mit rationalen Zahlen. Dies bedeutet ziemlich genaue Arithmetik, mit dem Nachteil, dass Sie am Ende Rationale mit riesigen bignums als Zähler und Nenner verwenden. Typ (sagen wir) 0 statt 0d0

Eine Möglichkeit, die Sie verwenden Schwimmer (Ich würde vorschlagen, Doppel Floats), um sicherzustellen, ist eine Zwischenfunktion zu haben, die alle Eingaben verdoppelt wandelt, es einfacher, nur zu machen.

Sobald Sie festgestellt haben, dass die Verwendung von Doubles es schneller macht, können Sie damit beginnen, Typendeklarationen zu streuen, damit der Compiler besseren Code für Sie generieren kann.

Answer 2

Hier ist ein Common Lisp Variante:

(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))) 

Beachten Sie die Verwendung von Doppel-Schwimmer Konstanten. Iteration sowohl über Doppelschwimmer als auch über Ganzzahlen.

es in SBCL Lauf nicht optimierten, sondern nativen Code kompiliert:

* (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 

den Code optimieren würde dann bedeuten:

• höher Compiler optimize Einstellung
• möglicherweise einige Typdeklarationen Hinzufügen
• loswerden des schwimmers consing