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 |

2011-01-19

C.I.CLを眺める(5) CIRCULAR-LENGTH

| 20:30 | C.I.CLを眺める(5) CIRCULAR-LENGTH - わだばLisperになる を含むブックマーク はてなブックマーク - C.I.CLを眺める(5) CIRCULAR-LENGTH - わだばLisperになる

今回は、C.I.CLのlist.lispから CIRCULAR-LENGTH です。

名前のとおり循環リストの長さ(というか要素数)を数えるものです.

定義は、

(defun circular-length (list)
  "LIST must be either a proper-list or a circular-list, not a dotted-list.
RETURN: the total length ; the length of the stem ; the length of the circle.
"
  (let ((indexes (make-hash-table)))
    (loop
       :for i :from 0
       :for current :on list
       :do (let ((index (gethash current indexes)))
             (if index
                 ;; found loop
                 (return (values i index (- i index)))
                 (setf (gethash current indexes) i)))
       :finally (return (values i)))))

となっていて、コンスセルを先頭から一つずつ位置と一緒に記録しておいて、同じものが現われたら結果を返す、というようになっています。

結果は多値で返して、1値目は、全体の長さ、2値目は、循環が始まるところまでの長さ、3値目は、循環しているリストの長さです。

動作は、

(import 'com.informatimago.common-lisp.list:circular-length)

(circular-length '(1 2 3 4))
;=> 4

(circular-length '#0=(1 2 3 . #0#))
;=> 3
;   0
;   3

(circular-length '(1 . #0=(2 3 . #0#)))
;=> 3
;   1
;   2

というところ