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-04-17

C.I.CLを眺める(9) HASHED-INTERSECTION

| 18:23 | C.I.CLを眺める(9) HASHED-INTERSECTION - わだばLisperになる を含むブックマーク はてなブックマーク - C.I.CLを眺める(9) HASHED-INTERSECTION - わだばLisperになる

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

(DEFUN HASHED-INTERSECTION (SET1 SET2)
  "
AUTHORS: Paul F. Dietz <dietz@dls.net>
         Thomas A. Russ <tar@sevak.isi.edu>
"
  (DECLARE (OPTIMIZE SPEED (SAFETY 0) (DEBUG 0))
           (LIST SET1 SET2))
  (LET ((TABLE (MAKE-HASH-TABLE :SIZE (LENGTH SET2)))
        (RESULT NIL))
    (DOLIST (E SET2) (SETF (GETHASH E TABLE) T))
    (DOLIST (E SET1) (WHEN (GETHASH E TABLE)
                       (PUSH E RESULT)
                       (SETF (GETHASH E TABLE) NIL)))
    RESULT))

となっています。

コメントからするとオリジナルの作者は、Paul F. Dietz、 Thomas A. Russの両氏のようです。

仕組みとしては、ハッシュテーブルを利用して共通する部分を抜き出すというもの。

動作は、

(import 'com.informatimago.common-lisp.list:hashed-intersection)

(hashed-intersection '(1 2 3 4)
                     '(1 2 3 4))
;=> (4 3 2 1)

(hashed-intersection '(1 2 3 4 5 6)
                     '(1 2 3 4))
;=> (4 3 2 1)

(hashed-intersection '("1" "2" "3" "4" "5" "6")
                     '("1" "2" "3" "4") )
;=> NIL

というところ。ハッシュの一致判定にデフォルトのEQLが使われているため文字列はスルーされてしまいます。