val it: α → α = fun

ふと SkipList を作ってみた。最初は pure scheme for Gauche で書いて、試してみたらあまりにも遅かったので、ついカッとなって Gauche の拡張モジュールとして実装した。

通常の整数比較とし、ランダムな数値をキーとして挿入し、10000回ほどランダムなキーで探索するという単純なベンチマークで treemap と比較してみた。比較結果は、

SkipList 1000 ;(time (times size (lambda (x) (skip-list-put! list-bench (mt-random-int … ; real 0.032 ; user 0.020 ; sys 0.010 ;(time (times 10000 (lambda a (skip-list-get list-bench (mt-random-integ … ; real 0.386 ; user 0.280 ; sys 0.110 10000 ;(time (times size (lambda (x) (skip-list-put! list-bench (mt-random-int … ; real 0.556 ; user 0.390 ; sys 0.160 ;(time (times 10000 (lambda a (skip-list-get list-bench (mt-random-integ … ; real 0.587 ; user 0.420 ; sys 0.160

treemap
1000
;(time (times size (lambda (x) (tree-map-put! tree-bench (mt-random-inte ...
; real   0.021
; user   0.010
; sys    0.010
;(time (times 10000 (lambda a (tree-map-get tree-bench (mt-random-intege ...
; real   0.252
; user   0.190
; sys    0.070
10000
;(time (times size (lambda (x) (tree-map-put! tree-bench (mt-random-inte ...
; real   0.333
; user   0.240
; sys    0.090
;(time (times 10000 (lambda a (tree-map-get tree-bench (mt-random-intege ...
; real   0.358
; user   0.250
; sys    0.100

こんな感じ(数値はリストの要素数)。うーむ、ちっと遅いな。ちなみにベンチマークを測ってみたところ、

Profiler statistics (total 27 samples, 0.27 seconds) num time/ total Name calls call(ms) samples ---------------------------------------------------+------+-------+----------- (#f #f) 518310 0.0004 19( 70%) (#f #f) 218019 0.0003 7( 26%) call-macro-expander 86 0.1163 1( 4%) (make-skip-list #f) 695229 0.0000 0( 0%) < 695229 0.0000 0( 0%) = 332868 0.0000 0( 0%)

となっているのだが、この (#f #f) てのはなんだろう。 static な C 関数のなか、とかかなあ。 (make-skip-list #f) は、 make-skip-list 内で作っている比較関数か。

ところで、 SkipList って乱数を使うとされているのだけど、実際には乱数の乱雑さは実はそんなに重要じゃないということがわかった。統計的にうまくバラけてくれればいい。実際、さいしょは math.mt-random を使っていたのだが、上のベンチマークはそうじゃないが、性能劣化はない(むしろ乱数生成よりずっと単純な処理なので性能は微増しているかも)。