SBCLのハッシュテーブルについて。
ハッシュテーブルのキーをなんでもいいから1つ消したいとする。ANSI CLのハッシュテーブルに該当する機能はない。しかし、そういう関数を定義するのは特に難しくなさそう:
(defun pophash (hash-table)
(maphash (lambda (key _)
(remhash key hash-table)
(return-from pophash key))
hash-table))
maphash
の中で受け取ったエントリを消去するのは許されているので、pophash
は意図通り動作する。しかし……
(defun test-pophash (size)
(let ((table (make-hash-table :size size)))
(dotimes (i size)
(setf (gethash i table) t))
(dotimes (i size)
(pophash table))))
(time (test-pophash 200000))
;; Evaluation took:
;; 15.268 seconds of real time
;; 15.265625 seconds of total run time (15.265625 user, 0.000000 system)
;; 99.99% CPU
;; 38,084,922,378 processor cycles
;; 5,848,704 bytes consed
たった回の操作に時間が掛かりすぎである。
もちろん、次のようにremhash
するだけなら計算量の問題はない。
(defun test-pophash2 (size)
(let ((table (make-hash-table :size size)))
(dotimes (i size)
(setf (gethash i table) t))
(dotimes (i size)
(remhash i table))))
(time (test-pophash2 200000))
;; Evaluation took:
;; 0.016 seconds of real time
;; 0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;; 100.00% CPU
;; 37,052,672 processor cycles
;; 5,848,704 bytes consed
そもそもchainingによるハッシュテーブルがキーをどう管理するか考えてみると、pophash
がだめなのはそれはそうという感じだった。以下、手短に動作を見てみる:
CL-USER> (let ((table (make-hash-table)))
(setf (gethash 3 table) 8
(gethash 5 table) 32
(gethash 7 table) 128)
(print (sb-impl::hash-table-pairs table))
(remhash 5 table)
(print (sb-impl::hash-table-pairs table))
(setf (gethash 11 table) 2048)
(print (sb-impl::hash-table-pairs table)))
#(3 0 3 8 5 32 7 128 #<unbound> #<unbound> ... #<unbound>
#(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0))
;; キー5を消す
#(3 0 3 8 #<unbound> #<unbound> 7 128 #<unbound> #<unbound> ... #<unbound>
#(0 60102308 60102306 60102304 0 0 0 0 0 0 0 0 0 0 0))
;; キー11を追加する
#(3 0 3 8 11 2048 7 128 #<unbound> #<unbound> ... #<unbound>
#(0 60102308 60102317 60102304 0 0 0 0 0 0 0 0 0 0 0))
上のように1、ハッシュテーブルの中身は単に配列に並んでいて、remhash
によって消されるとそこが消えるだけである。unbound
になったインデックスはうまく連鎖的に管理されていて、次に追加する時にはそこが埋まるようになっている。2
さて、maphash
だが、実装を見ればわかるように、pairs
を先頭から末尾まで走査するだけだ。つまり、上のpophash
は常に先頭から走査して見つけたキーを消すように動くので、全体ではになってしまう。
また、同じような理由で次のコードも計算量の問題がある:
(defun test-maphash (size)
(let ((table (make-hash-table :size size))
(sum 0))
(dotimes (i size)
(setf (gethash i table) t))
(dotimes (i (- size 1))
(remhash i table))
(dotimes (i size)
(maphash (lambda (x _) (incf sum x)) table))
sum))
(time (test-maphash 200000))
;; Evaluation took:
;; 34.567 seconds of real time
;; 34.562500 seconds of total run time (34.562500 user, 0.000000 system)
;; 99.99% CPU
;; 86,197,938,782 processor cycles
;; 5,848,704 bytes consed
ハッシュテーブルに個のキーを登録したあと個まで減らし、そのテーブルに対してmaphash
を回適用している。これも、同じ原理でになる。maphash
による走査は確かにだけれど、テーブルの今の要素数に対するではなく、過去に到達した最大要素数に対するなので、各エントリへのアクセスがになるとは限らないのだった。3
この最大要素数はSBCL内部ではhigh-water-mark
と呼ばれている。こういう実装になったのはバージョン1.5.5からで、それ以前は事前に確保したサイズに対するだったようだ。該当コミットはこれ。次のコードで違いがわかる:
(defun test-maphash2 (size)
(let ((table (make-hash-table :size size))
(sum 0))
(setf (gethash 0 table) t)
(dotimes (i size)
(maphash (lambda (x _) (incf sum x)) table))
sum))
(time (test-maphash2 200000))
;; SBCL 1.5.8, O(n)
;; Evaluation took:
;; 0.016 seconds of real time
;; 0.015625 seconds of total run time (0.015625 user, 0.000000 system)
;; 100.00% CPU
;; 16,126,752 processor cycles
;; 5,848,704 bytes consed
;; SBCL 1.4.14, O(n^2)
;; Evaluation took:
;; 47.615 seconds of real time
;; 47.625000 seconds of total run time (47.625000 user, 0.000000 system)
;; 100.02% CPU
;; 118,798,016,334 processor cycles
;; 8,497,264 bytes consed
ハッシュテーブルの要素数が大きくなるかもしれない場合に、リハッシュの回数を減らそうとして最初に:size
を大きめに取っておくという発想は普通っぽい感じだけど、1.5.5より前のバージョンでは逆に遅くなる可能性がある。
maphash
が今の要素数に対するになるような実装って可能かな? と少し考えていたけど、とりあえず既存のエントリ全体(と消したエントリ全体)のチェインをnext-vector
とは別に持てばできそう? 定数倍が重くなるわりに、できるようになることが大したことない感じだけど……