Cài đặt Mandelbrot Cài đặt trong Common Lisp

Question

Tôi đã làm việc để triển khai Mandelbrot Set bằng nhiều ngôn ngữ khác nhau. Tôi có một thực hiện làm việc trong C + +, C#, Java, và Python, nhưng việc triển khai thực hiện thường gặp Lisp có một số lỗi mà tôi chỉ không thể tìm ra. Nó tạo ra các thiết lập nhưng một nơi nào đó trong các đường ống tập hợp bị bóp méo. Tôi đã thử nghiệm và biết với gần chắc chắn rằng các tập tin I/O CLO không phải là vấn đề - nó không chắc nhưng có thể, tôi đã thử nghiệm nó khá kỹ lưỡng.

Lưu ý rằng mục đích của những triển khai này là đánh giá chúng với nhau - vì vậy tôi đang cố gắng giữ cho việc triển khai mã càng giống nhau càng tốt để chúng có thể so sánh được.

Các Mandelbrot set (ở đây được tạo ra bởi việc thực hiện Python):

http://www.freeimagehosting.net/uploads/65cb71a873.png http://www.freeimagehosting.net/uploads/65cb71a873.png "Tập hợp Mandelbrot (Generated by Python)"

Nhưng chương trình Common Lisp tôi tạo này:

http://www.freeimagehosting.net/uploads/50bf29bcc9.png http://www.freeimagehosting.net/uploads/50bf29bcc9.png "Common Lisp Phiên bản Mandelbrot bị bóp méo của phiên bản "

Lỗi này giống hệt nhau trong cả Clisp và SBCL.

Mã sản phẩm:

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) 

Và gần nhất với nó là 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(); 

tôi có thể đăng C++, C#, hoặc mã Java cũng Cần được.

Cảm ơn!

CHỈNH SỬA: Nhờ phản ứng của Edmund tôi đã tìm thấy lỗi- Chỉ cần một cái gì đó trượt qua các vết nứt trên cổng. Mã đã sửa đổi:

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

Mặc dù mã không phải là rất LISP-ish (là một từ?) Nó hoạt động. Nhờ tất cả những ai gửi/nhận xét/trả lời :)

Answer 1

Tôi không chắc chắn phần này là đúng:

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

ISN' t tempcplx được ghi đè bằng giá trị mới của nó trên dòng đầu tiên, có nghĩa là dòng thứ hai đang sử dụng giá trị mới, không phải giá trị ban đầu?

Trong phiên bản Python bạn đang tránh vấn đề này bằng cách sử dụng tmpb:

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

Dường như với tôi phiên bản Lisp nên làm điều gì đó tương tự, tức là lưu trữ các giá trị ban đầu của tmpcplx đầu tiên, và sử dụng cửa hàng để tính tmpreal:

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

Answer 2

Một số nhận xét về mã của bạn:

• Mandelbrot: thiếu tờ khai, quảng trường được tính hai lần trong vòng lặp

• Mandelbrot: trong tính toán cho TMPREAL bạn đang sử dụng giá trị mới của TMPCLX, không phải giá trị cũ của

• Bạn không muốn sử dụng METHODS để đặt pixel. SLOW.

• FLOORDIV là một trong những sàn hoặc TRUNCATE (tùy thuộc vào những gì bạn muốn) trong Common Lisp, xem (TẦNG 10 3)

• loại sử dụng tờ khai

• trong writexbm không liên tục gọi DỮ LIỆU và ARRSIZE

• SetPixel, unsetpixel trông rất đắt tiền, một lần nữa lặp đi lặp lại dereferencing cấu trúc

• hòa-Mandelbrot có rất nhiều r tính toán epeated có thể được thực hiện một lần

• Common Lisp có mảng 2ngày mà đơn giản hóa mã

• Common Lisp có số phức, mà cũng đơn giản hóa mã

• một tên biến 'tự' làm cho không có ý thức trong Common Lisp. Đặt tên nó là gì.

Nói chung mã đầy chất thải. Nó làm cho ít ý nghĩa để chuẩn mã của bạn, vì nó được viết theo một phong cách mà hy vọng không ai sử dụng trong Common Lisp. Lisp phổ biến đã được thiết kế với kinh nghiệm của phần mềm toán học lớn như Macsyma và cho phép viết mã toán học theo cách thẳng về phía trước (không có đối tượng, chỉ hoạt động trên số, mảng, ...). Các trình biên dịch tốt hơn có thể tận dụng các kiểu nguyên thủy, các hoạt động nguyên thủy và các khai báo kiểu. Vì vậy, phong cách khác với những gì người ta có thể viết bằng Python (thường là Python hướng đối tượng hoặc gọi tới một số mã C) hoặc Ruby. Trong mã số nặng, thường không phải là một ý tưởng tốt để có được công văn động như với CLOS. Thiết lập pixel trong bitmap thông qua các cuộc gọi CLOS trong một LOOP chặt chẽ thực sự là thứ mà bạn muốn tránh (trừ khi bạn biết cách tối ưu hóa nó).

Trình biên dịch Lisp tốt hơn sẽ biên dịch các hàm số để trực tiếp mã máy. Trong quá trình biên dịch, chúng đưa ra gợi ý các hoạt động nào là chung chung và không thể được tối ưu hóa (cho đến khi nhà phát triển thêm thông tin kiểu khác). Nhà phát triển cũng có thể 'DISASSEMBLE' các chức năng và kiểm tra mã là chung hoặc thực hiện các cuộc gọi chức năng không cần thiết. 'Trong mã consing số của ' "TIME' cung cấp thông tin thời gian chạy và cũng thông báo cho các nhà phát triển về số lượng bộ nhớ' consed nổi' là một vấn đề hiệu suất thông thường

Vì vậy, để tổng hợp:

• nếu bạn viết mã và nghĩ rằng nó giống nhau ở các ngôn ngữ khác nhau, khi mã trông giống hoặc có cấu trúc tương tự, điều này có thể không đúng - trừ khi bạn thực sự biết cả hai ngôn ngữ và cả hai ngôn ngữ triển khai. nếu bạn viết mã bằng một ngôn ngữ và chuyển nó theo kiểu tương tự sang một ngôn ngữ khác, bạn có thể bỏ lỡ một ole văn hóa hiện có để viết giải pháp cho các loại vấn đề theo một cách khác. Ví dụ, người ta có thể viết mã trong C++ theo kiểu hướng đối tượng và chuyển nó theo cách tương tự như FORTRAN. Nhưng không ai viết mã như vậy trong FORTRAN. Được viết theo phong cách FORTRAN, thường sẽ dẫn đến mã nhanh hơn - đặc biệt là vì các trình biên dịch được tối ưu hóa rất nhiều cho mã FORTRAN thành ngữ.

• "When in Rome, nói như người La Mã"

Ví dụ:

trong SetPixel có một cuộc gọi đến (đầu tiên (dim tự)). Tại sao không làm cho giá trị đó một khe trong cấu trúc ở nơi đầu tiên, thay vì làm một danh sách truy cập tất cả các thời gian? Nhưng sau đó giá trị là không đổi trong quá trình tính toán. Tuy nhiên, cấu trúc được truyền và giá trị được truy lục mọi lúc. Tại sao không chỉ nhận được giá trị bên ngoài vòng lặp chính và vượt qua nó trực tiếp? Thay vì làm nhiều tính toán của nó?

Để cung cấp cho bạn ý tưởng về cách mã có thể được viết (với khai báo kiểu, vòng lặp, số phức, ...), đây là phiên bản hơi khác so với tính toán mandelbrot.

Thuật toán cốt lõi:

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

Trên hàm trả về một mảng 2ngày số.

Viết một tập tin 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 "~&}~&"))) 

Trên một hàm lấy một mảng và một tên đường dẫn và viết các mảng như tập tin XBM. Một số 'đen' sẽ là 'đen' và những con số khác là 'trắng'

Gọi

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