Mandelbrot Common Lisp에서 구현 설정

Question

나는 여러 다른 언어로 Mandelbrot Set의 구현 작업을 해왔다. C++, C#, Java 및 Python으로 작동하는 구현이 있지만 Common Lisp 구현에는 파악할 수없는 몇 가지 버그가 있습니다. 그것은 세트를 생성하지만 파이프 라인 어딘가에 세트가 왜곡됩니다. 나는 근처에서 근처에있는 파일 I/O CLO가 문제가 아니라는 것을 테스트하고 알았습니다. 가능성은 희박하지만 가능합니다. 나는 그것을 철저히 테스트했습니다.

이러한 구현의 의도는 서로 벤치마킹한다는 점에 유의하십시오. 따라서 코드 구현을 가능한 비슷하게 유지하여 비교할 수 있도록하려고합니다.

(여기 파이썬 구현에 의해 생성) 만델 브로 집합 :

http://www.freeimagehosting.net/uploads/65cb71a873.png http://www.freeimagehosting.net/uploads/65cb71a873.png

하지만 내 커먼 리스프 프로그램이 생성 "만델 브로 세트 (파이썬에 의해 생성)"

http://www.freeimagehosting.net/uploads/50bf29bcc9.png http://www.freeimagehosting.net/uploads/50bf29bcc9.png "커먼 리스프를 버전의 왜곡 된 만델 브로 세트 "

버그는 Clisp 및 SBCL에서 모두 동일합니다.

CODE :

커먼 리스프 :

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

그리고 가장 가까운이 파이썬 :

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

나는뿐만 아니라 C++, C#, 또는 Java 코드를 게시 할 수 있습니다 필요합니다.

감사합니다.

편집 : 에드먼드의 응답 덕분에 버그를 발견했습니다. 이식시 균열을 뚫고 나온 것입니다. 수정 된 코드 :

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

코드는 LISP-ish가 아니지만 (즉,?) 작동합니다. 게시 된 사람/주석 모든 덕분에/대답 : 당신의 코드에 대한

Answer 1

: '

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

ISN t tempcplx가 첫 번째 줄에 새 값으로 덮어 쓰여집니다. 즉 두 번째 줄이 원래 값이 아닌 새 값을 사용하고 있습니까? 당신이 tmpb를 사용하여이 문제를 피할 수있는 파이썬 버전에서

:

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

그것은 리스프 버전, 비슷한 일을 즉 첫째 tmpcplx의 원래 값을 저장하고, 그 저장소를 사용합니다 날 것으로 보인다 tmpreal의 계산 :

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

Answer 2

일부 발언 :

• 만델 브로가 : 사각형이 루프에 두 번

• 만델 브로를 계산, 선언을 결여 : 계산에 TMPREAL의 경우 이전 값이 아닌 TMPCLX의 새 값을 사용합니다.

• 픽셀을 설정하는 데 METHODS를 사용하지 않으려합니다. 느린.

• FLOORDIV는 커먼 리스프에서 (당신이 원하는에 따라 다름)를 참조 FLOOR 또는 TRUNCATE 중 하나 (FLOOR 10 세) writexbm에서

• 반복적으로 데이터 호출하지 않는

• 사용 유형 선언이다 및

• 와 setPixel를 ARRSIZE, unsetpixel 다시 반복 구조를

• 무승부 - 만델 브로를 역 참조, 매우 비싼 보이는 R을 많이 가지고 한 번

• 커먼 리스프를 수행 할 수 있습니다 epeated 계산이

• 커먼 리스프는 또한 코드를 단순화 복잡한 번호를 가지고있는 코드를 단순화 차원 배열을 가지고

• 변수 이름 '자기'아무한다 Common Lisp에서의 감각. 그것이 무엇인지 이름을 지어 라.

일반적으로 코드에는 많은 양의 낭비가 있습니다. 코드를 벤치마킹하는 것은 의미가 없습니다. 왜냐하면 Common Lisp에서 아무도 사용하지 않는 스타일로 작성 되었기 때문입니다. Common Lisp은 Macsyma와 같은 대규모 수학 소프트웨어의 경험을 바탕으로 설계되었으며 직선적 인 방식으로 수학 코드를 작성할 수 있습니다 (객체가 없거나 숫자, 배열 등). 더 나은 컴파일러는 기본 유형, 원시 연산 및 유형 선언을 활용할 수 있습니다. 따라서 스타일은 Python (보통 객체 지향 Python 또는 C 코드 호출) 또는 Ruby에서 작성하는 것과 다릅니다. 무거운 숫자 코드에서는 일반적으로 CLOS처럼 동적 디스패치를하는 것이 좋지 않습니다. 단단한 LOOP에서 CLOS 호출을 통해 비트 맵의 ​​픽셀을 설정하는 것은 실제로 (최적화 방법을 알지 못한다면) 피하기를 원하는 것입니다.

더 나은 Lisp 컴파일러는 수치 함수를 컴파일하여 기계어를 지시합니다. 컴파일하는 동안 작업은 일반적이며 개발자가 더 많은 유형 정보를 추가 할 때까지 최적화 할 수없는 힌트를 제공합니다. 개발자는 또한 함수를 '해체'하고 일반 코드 또는 불필요한 함수 호출을 검사 할 수 있습니다. . 일반적인 성능 문제를 '시간은'런타임 정보를 제공하고 또한 메모리의 양에 대한 개발자 알려주는 '수레'.의 숫자 코드 consing에서 '은 consed을'이다

을 그래서, 요약하기 :

• 코드를 작성하고 다른 언어로 동일하게 취급한다고 생각하면 코드가 비슷하거나 유사한 구조를 가졌을 때 실제로 언어와 두 가지 언어 구현을 모르는 경우가 아니면 그렇지 않을 수도 있습니다.

• 한 언어로 코드를 작성하고 다른 언어와 비슷한 스타일로 이식하면 wh 기존 문화를 통해 이러한 종류의 문제에 대한 해결책을 다른 방식으로 작성합니다. 예를 들어, C++로 객체 지향 스타일로 코드를 작성하고 FORTRAN과 비슷한 방식으로 포팅 할 수 있습니다. 그러나 FORTRAN에 그런 코드를 쓰는 사람은 아무도 없습니다. FORTRAN 스타일로 작성된 컴파일러는 특히 관용적 인 FORTRAN 코드에 많이 최적화되어 있기 때문에 더 빠른 코드를 생성합니다.

• "로마 로마인 같이 말할 때"

예제에서와 setPixel

호출이있다 (제 1 (희미한 자체)). 항상 목록 액세스를하는 대신 그 값을 구조의 첫 번째 슬롯에 넣는 것이 어떻습니까? 그러나 계산 중 값은 일정합니다. 여전히 구조가 전달되고 값은 항상 검색됩니다. 왜 그냥 주 루프 바깥에서 값을 가져 와서 직접 전달하지 않는가? 그것의 여러 계산을하는 대신?

코드 작성 방법 (유형 선언, 루프, 복소수 등)을 알려면 여기에 약간 다른 버전의 만델 브로 계산이 있습니다.

핵심 알고리즘 : 기능 이상

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

숫자의 2 차원 배열을 반환합니다.

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 "~&}~&"))) 

배열과 경로 이름을 소요하고 XBM 파일로 배열을 기록합니다. 한 수 '블랙' '블랙'이 될 것이며, 다른 번호는 '흰색'이다

전화 나는이 부분이 올바른지 확실하지 않다

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