ハッシュ作ってみた
グラフ理論で使うデータ構造にリストを使うと検索コストが高いので、ハッシュを使いたい。
SRFI 69: Basic hash tablesを眺めてみたら、ハッシュの実装例が載ってたので、簡単に写経してみた。
SRFI-69の実装例では、ベクタ + alistの二次元構造。alistをハッシュテーブルに分割することによって検索速度の向上を図ると。ハッシュはハッシュでもO(1)では無くO(n/テーブルサイズ)くらい。テーブルサイズを大きくすればまぁまぁ早い感じ。
(define *default-bound* (- (expt 2 29) 3)) (define *table-size* 10) (define (make-hash) (make-vector *table-size* '())) (define (get-hash key) (letrec ((iter (lambda (l) (if (null? l) 31 (modulo (+ (char->integer (car l)) (* 37 (iter (cdr l)))) *default-bound*))))) (modulo (iter (string->list (symbol->string key))) *table-size*))) (define (hash-value hash key) (let ((a (assq key (vector-ref hash (get-hash key))))) (and a (cdr a)))) (define (hash-set! hash key value) (let ((index (get-hash key))) (hash-delete! hash key) (vector-set! hash index (cons (cons key value) (vector-ref hash index))))) (define (hash-delete! hash key) (letrec ((index (get-hash key)) (iter (lambda (l) (cond ((null? l) '()) ((eq? (caar l) key) (cdr l)) (else (cons (car l) (iter (cdr l)))))))) (vector-set! hash index (iter (vector-ref hash index)))))
テスト。
(define my-hash (make-hash)) (hash-set! my-hash 'hello "Hello, Hash World!!") (hash-set! my-hash 'hi "Hi, Hash.") (hash-value my-hash 'hello) ; Hello, Hash World!! (hash-value my-hash 'hi) ; Hi, Hash. (hash-delete! my-hash 'hello) (hash-value my-hash 'hello) ; #f
案外簡単に作れたけど、自作はあんまり・・・
ぬはぁ、そうか
全然早くないじゃないかと思ってたら、ここからがハッシュの凄いところで、
「再配置」
テーブルサイズが許容範囲を超えたら、テーブルサイズを増やして再配置してやれば、約O(1)をキープすることが出来るのか。
かなり改造が必要だけど、実装してみるか。
テーブルの再配置を実装
テーブルサイズが2個になっているので、2個を超えたら倍のサイズのテーブルを用意して、元のデータをコピーしながら再配置していくことにする。
(define *default-bound* (- (expt 2 29) 3)) (define *table-size* 2) (define (make-hash) (let ((size 0) (table (make-vector *table-size* '()))) (lambda (m) (case m ('table table) ('table-set! (lambda (t) (set! size 0) (set! table t))) ('size size) ('inc! (set! size (+ size 1))) ('dec! (set! size (- size 1))) ('length (vector-length table)))))) (define (get-hash key len) (letrec ((iter (lambda (l) (if (null? l) 31 (modulo (+ (char->integer (car l)) (* 37 (iter (cdr l)))) *default-bound*))))) (modulo (iter (string->list (symbol->string key))) len))) (define (hash-value hash key) (let ((a (assq key (vector-ref (hash 'table) (get-hash key (hash 'length)))))) (and a (cdr a)))) (define (hash-set! hash key value) (let ((index (get-hash key (hash 'length))) (table (hash 'table))) (if (hash-delete! hash key) (hash 'dec!)) (vector-set! table index (cons (cons key value) (vector-ref table index))) (hash 'inc!) (if (> (hash 'size) (hash 'length)) (hash-resize! hash)))) (define (hash-delete! hash key) (letrec ((index (get-hash key (hash 'length))) (table (hash 'table)) (iter (lambda (l) (cond ((null? l) #f) ((eq? (caar l) key) (cdr l)) (else (let ((res (iter (cdr l)))) (and res (cons (car l) res)))))))) (let ((res (iter (vector-ref table index)))) (and res (vector-set! table index res) (hash 'dec!))))) (define (%hash-fold f seed table) (vector-fold (lambda (i acc v) (fold (lambda (a acd) (f (car a) (cdr a) acd)) acc v)) seed table)) (define (hash-fold f seed hash) (%hash-fold f seed (hash 'table))) (define (hash-resize! hash) (let* ((size (* 2 (hash 'length))) (new-table (make-vector size '())) (old-table (hash 'table))) ((hash 'table-set!) new-table) (%hash-fold (lambda (key value acc) (hash-set! hash key value)) #f old-table)))
テスト。
(define my-hash (make-hash)) (hash-set! my-hash 'hello "Hello, Hash World!!") (hash-set! my-hash 'hi "hi, Hash.") (my-hash 'table) ; #(((hi . hi, Hash.)) ((hello . Hello, Hash World!!))) (hash-set! my-hash 'resize "Hash Sugeeeeeeeeeeeee!!") ; ← ここら辺で再配置してる。 (hash-set! my-hash 'hoge "hoge hoge") (my-hash 'table) ; #(((resize . Hash Sugeeeeeeeeeeeee!!) (hi . hi, Hash.)) () ; ((hoge . hoge hoge)) ((hello . Hello, Hash World!!)))
検索はほぼO(1)となった。
ハッシュスゲー。