読者です 読者をやめる 読者になる 読者になる

maphash-to-list

common lisp sbcl utility optimize

common lispではハッシュが使い難い(と思う)
その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。
ユーティリティ関数っぽくいろいろ装飾。
※ 宣言はsbcl(1.0.37)用に特化

(declaim (inline maphash-to-list))  ; sbclのmaphash関数にはinline宣言されているようなので、それに合わせる
(defun maphash-to-list (function-designator hash-table &aux acc)
"For each entry in HASH-TABLE, call the designated two-argument function on
 the key and value of the entry. Return list of the function return values."

  ;; 引数の型チェック等を行って欲しいため、safetyやdebugをここでは0にしない
  ;;
  ;; (/= safety 0)なら、関数呼び出し時に型チェックが行われる
  ;; - http://www.sbcl.org/manual/#Declarations-as-Assertions
  ;; 
  ;; (>= debug 1)なら、関数の引数情報が保持される => (describe ...)の結果が親切
  ;; - http://www.sbcl.org/manual/#Debugger-Policy-Control
  (declare (optimize (safety 1) (debug 1) (speed 3))
           (hash-table hash-table)
           ((or symbol function) function-designator))
  (locally
   ;; この時点では引数の型が正しいことが確定しているので、debug及びsafetyを0に設定
   (declare (optimize (debug 0) (safety 0)))
   (let ((fn (if (typep function-designator 'function)
                 function-designator
               (symbol-function function-designator))))
     (maphash
      (lambda (k v)
        (push (funcall fn k v) acc))
      hash-table))
   acc))

;;;;;;;
;;; 例
> (let ((hash (make-hash-table)))
    (setf (gethash :key hash) :value
          (gethash 1 hash) 2
          (gethash "a" hash) "b")
  
    ;; キーだけを集める
    (maphash-to-list (lambda (k v) k) hash))
--> ("a" 1 :KEY)

比較のために、型チェックを全く行わない版も定義。

(declaim (inline maphash-to-list-fast))
(defun maphash-to-list-fast (function-designator hash-table &aux acc)
  (declare (optimize (safety 0) (debug 0) (speed 3))
           (hash-table hash-table)
           (function function-designator))
  (maphash
   (lambda (k v)
     (push (funcall function-designator k v) acc))
   hash-table)
  acc)

比較。

;;;;;;;;;;;;;;;;;;
;;; 型チェック確認
> (maphash-to-list 1 1)
debugger invoked on a TYPE-ERROR in thread #<THREAD "initial thread" RUNNING
                                             {AA087C1}>:
  The value 1 is not of type (OR SYMBOL FUNCTION).  ; 型が違う

> (maphash-to-list-fast 1 1)
CORRUPTION WARNING in SBCL pid 9089(tid 3085166256):
Memory fault at 3b (pc=0xb61914a, sp=0xb7907b88)
The integrity of this image is possibly compromised.
Continuing with fingers crossed.

debugger invoked on a SB-SYS:MEMORY-FAULT-ERROR in thread #<THREAD
                                                            "initial thread" RUNNING
                                                            {AA087C1}>:
  Unhandled memory fault at #x3B.  ; Unhandled memory?

;;;;;;;;;;;;;
;;;; 処理速度
;; 要素数1000のハッシュを作成
> (defparameter *hash*
    (let ((hash (make-hash-table)))
      (loop FOR i FROM 0 BELOW 1000 DO
        (setf (gethash i hash) (random 10000000)))
      hash))
--> *HASH*

;; maphash関数の場合
> (time
   (dotimes (i 100000 'done)
     (declare (optimize (speed 3) (debug 0) (safety 0)))
     (let (acc)
       (maphash
         (lambda (k v)
           (declare (fixnum k v))
           (push (+ k v) acc))
         *hash*))))
Evaluation took:
  0.845 seconds of real time
  0.844052 seconds of total run time (0.844052 user, 0.000000 system)
  [ Run times consist of 0.060 seconds GC time, and 0.785 seconds non-GC time. ]
  99.88% CPU
  2,680,836,701 processor cycles
  800,000,936 bytes consed
--> DONE

;; maphash-to-list関数の場合
> (time
   (dotimes (i 100000 'done)
     (declare (optimize (speed 3) (debug 0) (safety 0)))
     (maphash-to-list 
      (lambda (k v)
        (declare (fixnum k v))
        (+ k v))
      *hash*)))
Evaluation took:
  0.849 seconds of real time
  0.848054 seconds of total run time (0.844053 user, 0.004001 system)
  [ Run times consist of 0.072 seconds GC time, and 0.777 seconds non-GC time. ]
  99.88% CPU
  2,693,672,940 processor cycles
  800,002,736 bytes consed
--> DONE

;; maphash-to-list-fast関数の場合
> (time
   (dotimes (i 100000 'done)
     (declare (optimize (speed 3) (debug 0) (safety 0)))
     (maphash-to-list-fast
      (lambda (k v)
        (declare (fixnum k v))
        (+ k v))
      *hash*)))
  Evaluation took:
  0.848 seconds of real time
  0.844052 seconds of total run time (0.836052 user, 0.008000 system)
  [ Run times consist of 0.064 seconds GC time, and 0.781 seconds non-GC time. ]
  99.53% CPU
  2,687,459,342 processor cycles
  800,005,176 bytes consed
--> DONE

どれもほとんど速度は変わらない。
今回のような関数の場合は、入り口部分で型チェックをしたからといってそこがボトルネックとなることもないので(inline化されているならなおさら)、安全性を高め文書化するために、適切な宣言を行った方が良い。
結構サボリがちだけど、今後ユーティリティ関数やライブラリを書く時には気をつけないと...。

*1:loopマクロを使えば出来ないことはないけど、これはこれで使い難いように思う。ハッシュのキーと値の両方を使いたい時は特に。