Mandelbrot Implementacja zestawu w Common Lisp

Question

Pracuję nad implementacją Mandelbrot Set w kilku różnych językach. Mam działającą implementację w C++, C#, Java i Python, ale implementacja Common Lisp zawiera kilka błędów, których nie mogę pojąć. Generuje zestaw, ale gdzieś w rurociągu zestaw zostaje zniekształcony. Przetestowałem i znam z w pobliżu pewność, że plik CLO wejścia/wyjścia nie jest problemem - jest to mało prawdopodobne, ale możliwe, przetestowałem to całkiem nieźle.

Należy pamiętać, że celem tych implementacji jest porównanie ich ze sobą - dlatego staram się, aby implementacja kodu była jak najbardziej zbliżona, aby były porównywalne.

Zbiór Mandelbrota (tutaj generowane przez realizację Python):

http://www.freeimagehosting.net/uploads/65cb71a873.png http://www.freeimagehosting.net/uploads/65cb71a873.png "Mandelbrot Set (Wygenerowane przez Python)"

ale mój wspólny program Lisp generuje to:

http://www.freeimagehosting.net/uploads/50bf29bcc9.png http://www.freeimagehosting.net/uploads/50bf29bcc9.png „Common Lisp zniekształcona wersja Mandelbrota "

Błąd jest identyczny zarówno w Clisp, jak i SBCL.

KOD:

Common Lisp:

(defun mandelbrot (real cplx num_iter) 
    (if (> (+ (* real real) (* cplx cplx)) 4) 
     1 
     (let ((tmpreal real) (tmpcplx cplx) (i 1)) 
     (loop 
      (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
      (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpcplx tmpcplx)) 
       real)) 
      (setq i (+ i 1)) 
      (cond 
       ((> (+ (* tmpreal tmpreal) 
        (* tmpcplx tmpcplx)) 4) (return i)) 
       ((= i num_iter) (return 0))))))) 

(defun floordiv (dend sor) (/ (- dend (mod dend sor)) sor)) 

(defclass xbm() (
    (data :accessor data :initarg :data) 
    (dim :reader dim :initarg :dim) 
    (arrsize :reader arrsize :initarg :arrsize))) 

(defmethod width ((self xbm)) (third (dim self))) 

(defmethod height ((self xbm)) (second (dim self))) 

(defun generate (width height) 
    (let ((dims (list 0 0 0)) (arrsize_tmp 0)) 
     (setq dims (list 0 0 0)) 
     (setf (second dims) height) 
     (setf (third dims) width) 
     (setf (first dims) (floordiv (third dims) 8)) 
     (unless (= (mod width 8) 0) (setf (first dims) (+ (first dims) 1))) 
     (setq arrsize_tmp (* (first dims) (second dims))) 
     (make-instance 'xbm 
     :data (make-array arrsize_tmp :initial-element 0) 
     :dim dims 
     :arrsize arrsize_tmp))) 

(defun writexbm (self f) 
    (with-open-file (stream f :direction :output :if-exists :supersede) 
     (let ((fout stream)) 
     (format fout "#define mandelbrot_width ~d~&" (width self)) 
     (format fout "#define mandelbrot_height ~d~&" (height self)) 
     (format fout "#define mandelbrot_x_hot 1~&") 
     (format fout "#define mandelbrot_y_hot 1~&") 
     (format fout "static char mandelbrot_bits[] = {") 
     (let ((i 0)) 
      (loop 
       (if (= (mod i 8) 0) 
        (format fout "~& ") 
        (format fout " ")) 
       (format fout "0x~x," (svref (data self) i)) 
       (unless (< (setf i (+ i 1)) (arrsize self)) 
        (return t))))))) 

(defmethod setpixel ((self xbm) (x integer) (y integer)) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-ior (svref (data self) val) (ash 1 (mod x 8))))))) 

(defmethod unsetpixel ((self xbm) (x integer) (y integer)) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-xor (boole boole-ior 
      (svref (data self) val) (ash 1 (mod x 8))) (ash 1 (mod x 8))))))) 

(defmethod draw_mandelbrot ((xbm xbm) (num_iter integer) (xmin number) 
    (xmax number) (ymin number) (ymax number)) 

    (let ((img_width (width xbm)) (img_height (height xbm)) (xp 0)) 
     (loop 
     (if (< xp img_width) 
      (let ((xcoord (+ (* (/ xp img_width) (- xmax xmin)) xmin)) (yp 0)) 
       (loop 
        (if (< yp img_height) 
        (let (
         (ycoord (+ (* (/ yp img_height) (- ymax ymin)) ymin))) 
         (let ((val (mandelbrot xcoord ycoord num_iter))) 
          (if (> val 0) (unsetpixel xbm xp yp) (setpixel xbm xp yp))) 
         (setq yp (+ yp 1))) 
        (return 0))) 
       (setq xp (+ xp 1))) 
      (return 0))))) 

(defun main() 
    (let ((maxiter 0) (xmin 0) (xmax 0) (ymin 0) (ymax 0) (file nil) (xsize 0) (ysize 0) (picture nil)) 
     (format t "maxiter? ") 
     (setq maxiter (read)) 
     (format t "xmin? ") 
     (setq xmin (read)) 
     (format t "xmax? ") 
     (setq xmax (read)) 
     (format t "ymin? ") 
     (setq ymin (read)) 
     (format t "ymax? ") 
     (setq ymax (read)) 
     (format t "file path: ") 
     (setq file (read-line)) 
     (format t "picture width? ") 
     (setq xsize (read)) 
     (format t "picture height? ") 
     (setq ysize (read)) 
     (format t "~&") 
     (setq picture (generate xsize ysize)) 
     (draw_mandelbrot picture maxiter xmin xmax ymin ymax) 
     (writexbm picture file) 
     (format t "File Written.") 
     0)) 

(main) 

a najbliżej do niej jest Python:

from xbm import * 

def mandelbrot(real_old,cplx_old,i): 
    real = float(real_old) 
    cplx = float(cplx_old) 
    if (real*real+cplx*cplx) > 4: 
     return 1 
    tmpreal = real 
    tmpcplx = cplx 
    for rep in range(1,i): 
     tmpb = tmpcplx 
     tmpcplx = tmpreal*tmpcplx*2 
     tmpreal = tmpreal*tmpreal - tmpb*tmpb 
     tmpcplx += cplx 
     tmpreal += real 
     tmpb = tmpcplx*tmpcplx + tmpreal*tmpreal 
     if tmpb > 4: 
     return rep+1 
    else: 
     return 0 

def draw_mandelbrot(pic, num_iter, xmin, xmax, ymin, ymax): 
    img_width = pic.width() 
    img_height = pic.height() 
    for xp in range(img_width): 
     xcoord = (((float(xp))/img_width) * (xmax - xmin)) + xmin 
     for yp in range(img_height): 
     ycoord = (((float(yp))/img_height) * (ymax - ymin)) + ymin 
     val = mandelbrot(xcoord, ycoord, num_iter) 
     if (val): 
      pic.unsetpixel(xp, yp) 
     else: 
      pic.setpixel(xp, yp) 

def main(): 
    maxiter = int(raw_input("maxiter? ")) 
    xmin = float(raw_input("xmin? ")) 
    xmax = float(raw_input("xmax? ")) 
    ymin = float(raw_input("ymin? ")) 
    ymax = float(raw_input("ymax? ")) 
    file = raw_input("file path: ") 
    xsize = int(raw_input("picture width? ")) 
    ysize = int(raw_input("picture height? ")) 
    print 
    picture = xbm(xsize, ysize) 
    draw_mandelbrot(picture, maxiter, xmin, xmax, ymin, ymax) 
    picture.writexbm(file) 
    print "File Written. " 
    return 0; 

main() 

[xbm.py] 

from array import * 

class xbm: 
    def __init__(self, width, height): 
     self.dim = [0, 0, 0] 
     self.dim[1] = height 
     self.dim[2] = width 
     self.dim[0] = self.dim[2]/8 
     if width % 8 != 0: 
     self.dim[0] += 1 
     self.arrsize = self.dim[0] * self.dim[1] 
     self.data = array('B', (0 for x in range(self.arrsize))) 
     self.hex = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'] 
    def __nibbletochar__(self, a): 
     if a < 0 or a > 16: 
     return '0' 
     else: 
     return self.hex[a] 
    def setpixel(self, x, y): 
     if x < self.dim[2] and y < self.dim[1]: 
     self.data[(x/8) + (y * self.dim[0])] |= 1 << (x % 8) 
    def unsetpixel(self, x, y): 
     if x < self.dim[2] and y < self.dim[1]: 
     self.data[(x/8) + (y * self.dim[0])] |= 1 << (x % 8) 
     self.data[(x/8) + (y * self.dim[0])] ^= 1 << (x % 8) 
    def width(self): 
     return self.dim[2] 
    def height(self): 
     return self.dim[1] 
    def writexbm(self, f): 
     fout = open(f, 'wt') 
     fout.write("#define mandelbrot_width ") 
     fout.write(str(self.dim[2])) 
     fout.write("\n#define mandelbrot_height ") 
     fout.write(str(self.dim[1])) 
     fout.write("\n#define mandelbrot_x_hot 1") 
     fout.write("\n#define mandelbrot_y_hot 1") 
     fout.write("\nstatic char mandelbrot_bits[] = {") 
     for i in range(self.arrsize): 
     if (i % 8 == 0): fout.write("\n\t") 
     else: fout.write(" ") 
     fout.write("0x") 
     fout.write(self.__nibbletochar__(((self.data[i] >> 4) & 0x0F))) 
     fout.write(self.__nibbletochar__((self.data[i] & 0x0F))) 
     fout.write(",") 
     fout.write("\n};\n") 
     fout.close(); 

mogę pisać C++, C#, lub kod Java, a także potrzebować.

Dzięki!

EDYCJA: Dzięki odpowiedzi Edmunda znalazłem błąd - Po prostu coś, co przeszło przez pęknięcia w portowaniu. Zmodyfikowany kod:

(defun mandelbrot (real cplx num_iter) 
    (if (> (+ (* real real) (* cplx cplx)) 4) 
     1 
     (let ((tmpreal real) (tmpcplx cplx) (i 1) (tmpb cplx)) 
     (loop 
      (setq tmpb tmpcplx) 
      (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
      (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpb tmpb)) 
       real)) 
      (setq i (+ i 1)) 
      (cond 
       ((> (+ (* tmpreal tmpreal) 
        (* tmpcplx tmpcplx)) 4) (return i)) 
       ((= i num_iter) (return 0))))))) 

(defun floordiv (dend sor) (/ (- dend (mod dend sor)) sor)) 

(defclass xbm() (
    (data :accessor data :initarg :data) 
    (dim :reader dim :initarg :dim) 
    (arrsize :reader arrsize :initarg :arrsize))) 

(defun width (self) (third (dim self))) 

(defun height (self) (second (dim self))) 

(defun generate (width height) 
    (let ((dims (list 0 0 0)) (arrsize_tmp 0)) 
     (setq dims (list 0 0 0)) 
     (setf (second dims) height) 
     (setf (third dims) width) 
     (setf (first dims) (floordiv (third dims) 8)) 
     (unless (= (mod width 8) 0) (setf (first dims) (+ (first dims) 1))) 
     (setq arrsize_tmp (* (first dims) (second dims))) 
     (make-instance 'xbm 
     :data (make-array arrsize_tmp :initial-element 0) 
     :dim dims 
     :arrsize arrsize_tmp))) 

(defun writexbm (self f) 
    (with-open-file (stream f :direction :output :if-exists :supersede) 
     (let ((fout stream)) 
     (format fout "#define mandelbrot_width ~d~&" (width self)) 
     (format fout "#define mandelbrot_height ~d~&" (height self)) 
     (format fout "#define mandelbrot_x_hot 1~&") 
     (format fout "#define mandelbrot_y_hot 1~&") 
     (format fout "static char mandelbrot_bits[] = {") 
     (let ((i 0)) 
      (loop 
       (if (= (mod i 8) 0) 
        (format fout "~& ") 
        (format fout " ")) 
       (format fout "0x~x," (svref (data self) i)) 
       (unless (< (setf i (+ i 1)) (arrsize self)) 
        (return t))))))) 

(defun setpixel (self x y) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-ior (svref (data self) val) (ash 1 (mod x 8))))))) 

(defun unsetpixel (self x y) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-xor (boole boole-ior 
      (svref (data self) val) (ash 1 (mod x 8))) (ash 1 (mod x 8))))))) 

(defun draw_mandelbrot (xbm num_iter xmin xmax ymin ymax) 

    (let ((img_width (width xbm)) (img_height (height xbm)) (xp 0)) 
     (loop 
     (if (< xp img_width) 
      (let ((xcoord (+ (* (/ xp img_width) (- xmax xmin)) xmin)) (yp 0)) 
       (loop 
        (if (< yp img_height) 
        (let (
         (ycoord (+ (* (/ yp img_height) (- ymax ymin)) ymin))) 
         (let ((val (mandelbrot xcoord ycoord num_iter))) 
          (if (> val 0) (unsetpixel xbm xp yp) (setpixel xbm xp yp))) 
         (setq yp (+ yp 1))) 
        (return 0))) 
       (setq xp (+ xp 1))) 
      (return 0))))) 

(defun main() 
    (let ((maxiter 0) (xmin 0) (xmax 0) (ymin 0) (ymax 0) (file nil) (xsize 0) (ysize 0) (picture nil)) 
     (format t "maxiter? ") 
     (setq maxiter (read)) 
     (format t "xmin? ") 
     (setq xmin (read)) 
     (format t "xmax? ") 
     (setq xmax (read)) 
     (format t "ymin? ") 
     (setq ymin (read)) 
     (format t "ymax? ") 
     (setq ymax (read)) 
     (format t "file path: ") 
     (setq file (read-line)) 
     (format t "picture width? ") 
     (setq xsize (read)) 
     (format t "picture height? ") 
     (setq ysize (read)) 
     (format t "~&") 
     (setq picture (generate xsize ysize)) 
     (draw_mandelbrot picture maxiter xmin xmax ymin ymax) 
     (writexbm picture file) 
     (format t "File Written.") 
     0)) 

(main) 

Chociaż kod nie jest bardzo LISP-owski (czy to słowo?) Działa. Dziękujemy wszystkim, którzy napisali/skomentował/odpowiedziało :)

Answer 1

Nie jestem pewien, ta część jest poprawna:

 (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
     (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpcplx tmpcplx)) 
      real)) 

nieprawdaż t tempcplx zostanie nadpisany nową wartością w pierwszym wierszu, co oznacza, że ​​druga linia używa nowej wartości, a nie oryginalnej?

W wersji Pythona Unikasz tego problemu za pomocą TMPB:

tmpb = tmpcplx 
    tmpcplx = tmpreal*tmpcplx*2 
    tmpreal = tmpreal*tmpreal - tmpb*tmpb 
    tmpcplx += cplx 
    tmpreal += real 

Wydaje mi się wersja Lisp powinna zrobić coś podobnego, to znaczy najpierw zapisać oryginalną wartość tmpcplx i użyć tego sklepu do obliczenia tmpreal:

 (setq tmpb cplx) 
     (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
     (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpb tmpb)) 
      real)) 

Answer 2

Kilka uwag o kodzie:

• mandelbrot: brakuje deklaracji, kwadraty są obliczane dwa razy w pętli

• Mandelbrot: w obliczeniach dla TMPREAL używasz nowej wartości TMPCLX, a nie starej wartości:

• Nie chcesz używać METOD do ustawiania pikseli. POWOLNY.

• FLOORDIV jest jednym podłogi lub skrócenia (w zależności od tego, co chcesz) w Common Lisp, patrz (podłoga 10 3)

• deklaracje typu użycie

• w writexbm nie wielokrotnie transmisji danych i ARRSIZE

• setPixel, unsetpixel wygląda bardzo drogie, ponownie wielokrotnie odwołania do struktury

• draw-Mandelbrota ma dużo r epeated obliczenia, które można zrobić raz

• Common Lisp ma 2d tablice upraszczających kod

• Common Lisp ma liczb zespolonych, które również uproszczenie kodu

• nazwa zmiennej „ja” nie udziela żadnych sens w Common Lisp. Nazwij go tym, czym jest.

Generalnie kod jest pełen odpadów. Nie ma sensu porównywać twojego kodu, ponieważ jest napisany w stylu, który - mam nadzieję - nikt nie używa w Common Lisp. Common Lisp został zaprojektowany z doświadczeniem dużego oprogramowania matematycznego, takiego jak Macsyma i pozwala na pisanie kodu matematycznego w prosty sposób (bez obiektów, tylko funkcje nad liczbami, tablice, ...). Lepsze kompilatory mogą korzystać z typów pierwotnych, operacji pierwotnych i deklaracji typów. W związku z tym styl różni się od tego, co można napisać w Pythonie (który zazwyczaj to obiektowy Python lub wywołania jakiegoś kodu C) lub Ruby. W ciężkim kodzie liczbowym zwykle nie jest dobrym pomysłem, aby mieć dynamiczną wysyłkę, jak przy CLOS. Ustawianie pikseli w bitmapach za pomocą wywołań CLOS w ciasnej pętli LOOP jest naprawdę czymś, czego chce się uniknąć (chyba, że ​​wiesz, jak ją zoptymalizować).

Lepsze kompilatory Lisp skompilują funkcje numeryczne do bezpośredniego kodu maszynowego. Podczas kompilacji podają wskazówki, które operacje są ogólne i nie można ich zoptymalizować (dopóki programista nie doda więcej informacji o typie). Deweloper może również "ROZBIERAĆ" funkcje i sprawdzać, czy kod jest ogólny, czy też niepotrzebnie wywołuje funkcje. «W kodzie numerycznym consing z« „TIME” podaje informacje wykonania, a także informuje programistę o ilości pamięci»consed pływa» to zwykły problem z wydajnością

Tak więc, aby podsumować:

• jeśli piszesz kod i myślisz, że robi to samo w różnych językach, gdy kod wygląda podobnie lub ma podobną strukturę, może to nie być prawdą - chyba, że ​​naprawdę znasz oba języki i obydwa języki:

• jeśli napiszesz kod w jednym języku i przeniesiesz go w stylu podobnym do innego, możesz pominąć wh z istniejącą kulturą, aby pisać rozwiązania tego rodzaju problemów w inny sposób. Na przykład można napisać kod w C++ w stylu obiektowym i przenieść go w sposób podobny do FORTRAN. Ale nikt nie pisze takiego kodu w FORTRAN. Napisane w FORTRAN-u, zazwyczaj skutkuje szybszym kodem - zwłaszcza, że ​​kompilatory są mocno zoptymalizowane pod kątem idiomatycznego kodu FORTRAN.

• "gdy w Rzymie mówi jak rzymskiego"

przykład:

w setPixel jest wywołanie (pierwszy (wymiar siebie)). Dlaczego nie uczynić tej wartości szczeliną w strukturze, zamiast robić cały czas dostęp do listy? Ale wtedy wartość jest stała podczas obliczeń. Mimo to struktura jest przekazywana, a wartość jest pobierana przez cały czas. Dlaczego nie uzyskać wartości poza główną pętlą i przekazać ją bezpośrednio? Zamiast robić wiele obliczeń tego?

Aby dać ci pojęcie jak można pisać kod (z deklaracjami typu, pętli, liczb zespolonych, ...), tutaj jest nieco inna wersja obliczeń mandelbrota.

Algorytm Rdzeń:

(defvar *num-x-cells* 1024) 
(defvar *num-y-cells* 1024) 
(defvar *depth* 60) 


(defun m (&key (left -1.5) (top -1.0) (right 0.5) (bottom 1.0) (depth *depth*)) 
    (declare (optimize (speed 3) (safety 0) (debug 0) (space 0))) 
    (loop with delta-x-cell float = (/ (- right left) *num-x-cells*) 
     and delta-y-cell float = (/ (- bottom top) *num-y-cells*) 
     and field = (make-array (list *num-x-cells* *num-y-cells*)) 
     for ix fixnum below *num-x-cells* 
     for x float = (+ (* (float ix) delta-x-cell) left) 
     do (loop for iy fixnum below *num-y-cells* 
       for y = (+ (* (float iy) delta-y-cell) top) 
       do (loop for i fixnum below depth 
          for z of-type complex = (complex x y) 
          then (+ (complex x y) (* z z)) 
          for exit = (> (+ (* (realpart z) (realpart z)) 
              (* (imagpart z) (imagpart z))) 
             4) 
          finally (setf (aref field ix iy) i) 
          until exit)) 
     finally (return field))) 

powyższa funkcja zwraca 2d tablicy numerów.

Pisanie plik xbm:

(defun writexbm (array pathname &key (black *depth*)) 
    (declare (fixnum black) 
      (optimize (speed 3) (safety 2) (debug 0) (space 0))) 
    (with-open-file (stream pathname :direction :output :if-exists :supersede) 
    (format stream "#define mandelbrot_width ~d~&" (array-dimension array 0)) 
    (format stream "#define mandelbrot_height ~d~&" (array-dimension array 1)) 
    (format stream "#define mandelbrot_x_hot 1~&") 
    (format stream "#define mandelbrot_y_hot 1~&") 
    (format stream "static char mandelbrot_bits[] = {") 
    (loop for j fixnum below (array-dimension array 1) do 
      (loop for i fixnum below (truncate (array-dimension array 0) 8) 
       for m fixnum = 0 then (mod (1+ m) 8) do 
       (when (zerop m) (terpri stream)) 
       (format stream "0x~2,'0x, " 
         (let ((v 0)) 
          (declare (fixnum v)) 
          (dotimes (k 8 v) 
          (declare (fixnum k)) 
          (setf v (logxor (ash (if (= (aref array 
                   (+ (* i 8) k) j) 
                 black) 
                1 0) 
               k) 
              v))))))) 
    (format stream "~&}~&"))) 

Powyższa funkcja pobiera tablicę i ścieżki i zapisuje jako plik XBM tablicę. Jeden numer „czarna” będzie „czarny”, a pozostałe numery są „białe”

połączeń

(writexbm (m) "/tmp/m.xbm")