dict: ハッシュテーブル
前回にErlangで作成したhashtrieをcommon lispに移植していたら、いつのまにかただのハッシュテーブルになっていた。
もともとはHAMTから始まったはずなのに...。
実装
キー衝突時にAMTを使わないで、リンクリストを使うHAMT。
初期テーブルを用意して、キーのハッシュ値を計算し、衝突が発生した場合はリンクリストでつないで、要素が一定数を越えたらリサイズする、というまあ普通のハッシュテーブル。
比較
一応簡単にsbclのhash-tableと比較(挿入のみ)。
※ 以下の関数で、挿入する要素の数を乱数で決定しているのは、dictの実装ではリサイズの直前と直後でパフォーマンスに結構差がでてしまい*1、要素数を特定の値に決め打ちするとたまたま良い(or 悪い)結果に偏ってしまう可能性があるため。
;;;; sbcl-1.0.40 ;;;; 比較用関数(要素挿入) (defun hash-time (loop-count entry-count-limit) (format t "~&;;; hash-table~%") #+SBCL (sb-ext:gc :full t) (time (loop REPEAT loop-count DO (loop WITH h = (make-hash-table) FOR i FROM 0 BELOW (random entry-count-limit) DO (setf (gethash i h) i)))) (format t "~&;;; dict~%") #+SBCL (sb-ext:gc :full t) (time (loop REPEAT loop-count DO (loop WITH h = (dict:make) FOR i FROM 0 BELOW (random entry-count-limit) DO (setf (dict:get i h) i)))) 'done)
;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; (random 100)を十万回 (hash-time 100000 100) ;;; hash-table Evaluation took: 2.067 seconds of real time 2.044128 seconds of total run time (2.016126 user, 0.028002 system) [ Run times consist of 0.024 seconds GC time, and 2.021 seconds non-GC time. ] 98.89% CPU 4,122,625,986 processor cycles 296,898,712 bytes consed ;;; dict Evaluation took: 1.954 seconds of real time 1.932121 seconds of total run time (1.928121 user, 0.004000 system) [ Run times consist of 0.028 seconds GC time, and 1.905 seconds non-GC time. ] 98.87% CPU 3,897,851,316 processor cycles 145,822,992 bytes consed --> DONE ;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; (random 10000)を千回 (hash-time 1000 10000) ;;; hash-table Evaluation took: 2.091 seconds of real time 2.056128 seconds of total run time (2.012125 user, 0.044003 system) [ Run times consist of 0.052 seconds GC time, and 2.005 seconds non-GC time. ] 98.33% CPU 4,171,704,252 processor cycles 299,852,976 bytes consed ;;; dict Evaluation took: 1.942 seconds of real time 1.924121 seconds of total run time (1.912120 user, 0.012001 system) [ Run times consist of 0.024 seconds GC time, and 1.901 seconds non-GC time. ] 99.07% CPU 3,875,434,860 processor cycles 106,428,544 bytes consed --> DONE ;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;; (random 1000000)を十回 (hash-time 10 1000000) ;;; hash-table Evaluation took: 2.662 seconds of real time 2.660166 seconds of total run time (2.476154 user, 0.184012 system) [ Run times consist of 0.348 seconds GC time, and 2.313 seconds non-GC time. ] 99.92% CPU 5,311,663,296 processor cycles 288,290,336 bytes consed ;;; dict Evaluation took: 3.024 seconds of real time 3.020188 seconds of total run time (2.900181 user, 0.120007 system) [ Run times consist of 1.164 seconds GC time, and 1.857 seconds non-GC time. ] 99.87% CPU 6,032,913,060 processor cycles 124,907,808 bytes consed DONE
