Implementacja zestawu Mandelbrota w Scheme jest bardzo powolna.

Question

Próbuję nauczyć się Lisp/Scheme i próbowałem wdrożyć bardzo prostą wersję zestawu mandelbrot, aby uzyskać praktykę. Problemem, który napotkałem, jest to, że kod działa bardzo, bardzo wolno. Na początku myślałem, że to dlatego, że używałem rekursji zamiast imperatywnych pętli, ale próbowałem przepisać mniej więcej ten sam kod (rekurencję) w pythonie (który nie miał nawet optymalizacji wywołań) i działał bardzo gładka

Zastanawiam się, czy w moim kodzie brakuje czegoś oczywistego i co mogę zrobić, aby działał szybciej.

Oto fragment kodu w Scheme (rakieta). Zrobiłem też prawie to samo w SBCL a prędkość była porównywalna

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

(mam nadzieję, że blok kodu nie jest zbyt clustery, trudno było się rozebrać go na coś bardziej prostego)

Również Wiem, że Scheme i Common Lisp mają wbudowane liczby zespolone, ale chciałem przetestować je przy użyciu zwykłych liczb rzeczywistych, nie sądzę, że to jest powód, dla którego działa tak wolno.

Parametr "i" funkcji brota to liczba iteracji, a parametr "n" brot-grid to również liczba iteracji, które należy zastosować dla każdego punktu. Kiedy ustawię go na więcej niż 10, kod będzie trwał wiecznie, co nie wydaje się normalne. Wydłużenie czasu również nie wydaje się być liniowe, na przykład zajmuje tylko sekundę na mojej maszynie z n = 10, ale zajmuje kilka minut z n = 15 i nie kończy się nawet n = 20

Co zatem sprawia, że ​​ten kod działa tak wolno?

góry dzięki

Answer 1

Patrząc na twój kod, myślę, że testujesz go za pomocą liczb wymiernych. Oznacza to dość dokładną arytmetykę, z tą niedogodnością szybko kończy się używanie racjonalnych rozwiązań z dużymi liczbami jako licznikiem i mianownikiem.

Jednym ze sposobów zapewnienia, że ​​używasz pływaków (sugerowałbym podwójne pływanie), jest posiadanie funkcji pośredniej, która konwertuje wszystkie wejścia do podwójnych, aby ułatwić po prostu wpisanie (powiedzmy) 0 zamiast 0d0.

Po ustaleniu, że użycie podwójnych powoduje, że jest szybszy, można rozpocząć deklaracje typu zraszania, aby umożliwić kompilatorowi wygenerowanie lepszego kodu.

Answer 2

Oto Common Lisp wariant:

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

Wskazówka stosowanie podwójnych stałych pływaka. Również iterowanie zarówno nad podwójnymi zmiennymi i liczbami całkowitymi.

Running go w SBCL niezoptymalizowanych, ale kompilowane do kodu natywnego:

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

Optymalizacja kodu wtedy myśli:

• wyższy optymalizacji kompilator ustawienie
• ewentualnie dodając pewne deklaracje typu
• pozbycie się pływającego elementu