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-03-29

ArcでL-99 (P49 グレイ・コード)

| 13:19 | ArcでL-99 (P49 グレイ・コード) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P49 グレイ・コード) - わだばLisperになる

グレイ・コードとは、一度に1ビットしか変化しないような二進符号のことだそうです。

去年Common Lispで解答を作成したときには、2進数を右シフトしてXORを取るという方法で解答しましたが、メモ化してみるという課題もあるので、今回は再帰で。

メモ化で効率はどう変化するかということですが、Arcには、defmemoというメモ化してくれるマクロがあるので安直にそれを利用。

キャッシュが効くと速くなります。

(gray 4)
;=> ("0000" "0001" "0011" "0010" "0110" "0111" "0101" "0100"
     "1100" "1101" "1111" "1110" "1010" "1011" "1001" "1000")

(def gray (n)
  (if (is 1 n)
      '("0" "1")
      (let g (gray (- n 1))
        (+ (map [+ "0" _] g)
           (map [+ "1" _] rev.g)))))

;; メモ化版
(defmemo graym (n)
  (if (is 1 n)
      '("0" "1")
      (let g (graym (- n 1))
        (+ (map [+ "0" _] g)
           (map [+ "1" _] rev.g)))))
(graym 12)(gray 12)
1time: 159 msec.time: 265 msec.
2time: 0 msec. time: 327 msec.
3time: 0 msec.time: 206 msec.