Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-01-27

Getting Started in *LISP (3)

| 23:48 | Getting Started in *LISP (3) - わだばLisperになる を含むブックマーク はてなブックマーク - Getting Started in *LISP (3) - わだばLisperになる

*LISPのチュートリアルをさらってみることの3回目。

1.2.3 Defining a More Complex Automaton

この節では、もうちょっと複雑なオートマトン、"9ライフ"を作成してみるとのこと。

ルールは以下の通り

  1. 各々のセルの周囲の0でないセルの個数を数える。
  2. 上記の個数が、1より小さいか、3より大きい場合、セルの値から1引く
  3. 同様に、2個から3個の場合は、セルの値に1足す

周囲の定義には2種類あり、フォン・ノイマン型とムーア型があるそうな。

フォン・ノイマン型は、上下左右の4方向が隣人とみなされ、ムーア型は、8方向が隣人。

今回は9ライフなので、ムーア型を採用。

逐次型と並列型の違い

各々のセルを一世代、更新する関数を逐次実行で書くとすると、x軸とy軸のアレイをループ処理することになり、下記のようになるんじゃないかとのこと。

(defun serial-one-step (array-x-size array-y-size)
  (dotimes (x array-x-size)
    (dotimes (y array-y-size)
      (let ((neighbors (list	(get-cell (- x 1) y)
				(get-cell (+ x 1) y)
				(get-cell x (- y 1))
				(get-cell x (+ y 1))
				... )))
	(store-new-cell-value x y
			      (new-value neighbors)))))
  (update-grid))

内容としては、隣のセルの番地を計算して、その値を取得し結果を合計している。

隣のセルの値の取得については、*LISPには隣のグリッドの値を並列に取得するためのnews!!という関数が用意されているので、ループを回す必要はない。

newsは東西南北のn、e、w、sの意味。

(news!! x y)となるので、(news!! 1 0)の場合、自身の東の値となる。

東の値を自身の位置に表示すると結果として西にずれたように見える。

(let ((g (random!! 10)))
  (ppp g :end '(8 8))
  (ppp (news!! g 1 0) :end '(8 8))
;=>
;     DIMENSION 0 (X)  ----->
;
;3 4 0 0 3 3 2 2 
;4 0 1 8 3 4 5 9 
;5 2 0 0 5 3 7 2 
;6 1 5 7 1 0 4 6 
;0 5 8 9 8 6 4 8 
;1 3 8 3 8 0 8 6 
;9 0 5 6 3 6 8 2 
;3 2 7 8 4 6 0 9 
;
;     DIMENSION 0 (X)  ----->
;
;4 0 0 3 3 2 2 2 
;0 1 8 3 4 5 9 1 
;2 0 0 5 3 7 2 6 
;1 5 7 1 0 4 6 6 
;5 8 9 8 6 4 8 1 
;3 8 3 8 0 8 6 1 
;0 5 6 3 6 8 2 2 
;2 7 8 4 6 0 9 6 

news!!を使うと、フォン・ノイマン型の隣人を求める関数は、

(defun neumann-count (grid)
  (+!! (news!! grid  0 -1)	;; north
       (news!! grid  0  1)	;; south
       (news!! grid -1  0)	;; west
       (news!! grid  1  0)	;; east
       ))

のように定義できる。

ムーア型は、8方向なので、

(defun moore-count (grid)
  (+!!	(news!! grid  0 -1)			;; north
	(news!! grid  0  1)			;; south
	(news!! grid -1  0)			;; west
	(news!! grid  1  0)			;; east
	(news!! grid -1 -1)			;; northwest
	(news!! grid -1  1)			;; southwest
	(news!! grid  1 -1)			;; northeast
	(news!! grid  1  1)			;; southeast
	))

となる。

周囲の非ゼロのセルの個数の合計は、ノイマン型とムーア型を*neighborhood*で切り分けられるように定義するとすれば、

(defvar *neighborhood* :neumann)

(defun neighbor-count ()
  (*let ((grid (signum!! *automata-grid*)))
    (ecase *neighborhood*
      (:moore (moore-count grid))
      (:neumann (neumann-count grid)))))

のように書ける。signum!!はsignumのSIMD命令版。*LETは、pvarを扱うlet

;; ランダムな値で埋めて、ノイマン方式で隣人の数を勘定してみる
(progn
  (random-grid)
  (view 8 8)
  (ppp (neighbor-count) :end '(8 8)))

;=>
;     DIMENSION 0 (X)  ----->
;セルの値
;8 8 4 0 0 8 5 6 
;5 8 4 9 0 1 7 2 
;5 7 2 4 9 7 6 3 
;9 4 9 5 5 4 0 2 
;1 2 4 7 5 3 1 6 
;8 1 1 6 7 8 5 8 
;4 5 8 4 8 3 8 7 
;8 7 1 4 1 5 0 2 
;
;     DIMENSION 0 (X)  ----->
;隣人数
;4 4 3 3 2 3 4 4 
;4 4 4 2 3 3 4 4 
;4 4 4 4 3 4 3 3 
;4 4 4 4 4 3 4 3 
;4 4 4 4 4 4 3 4 
;4 4 4 4 4 4 4 4 
;4 4 4 4 4 4 3 4 
;4 4 4 4 3 3 4 3 
;

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20080127