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

dict: ハッシュテーブル

common lisp algorithm library

前回Erlangで作成したhashtriecommon lispに移植していたら、いつのまにかただのハッシュテーブルになっていた。
もともとはHAMTから始まったはずなのに...。

ソースコード等: dict-0.0.1

実装

キー衝突時に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

素数(の最大)が百万の場合にdictでのGC時間が長くなっているけど、それ以外は似たような感じ。

*1:リサイズの直前はキーのハッシュ値が衝突した要素をつないだリンクリストの長さが平均して4となっているが、リサイズ直後にはそれが1/4になる。そのため、成功検索の場合は平均して二倍程度、失敗探索の場合はそれ以上の差が生じるはず。