core.rrb-vector: 新しいベクタの実装
(このエントリは，Clojure Contrib Library Advent Calendar 12日目の記事です。)
はじめに
今回のネタはcore.rrb-vectorです。core.rrb-vectorは2013年1月にContribライブラリに入った比較的新しいライブラリです。
core.rrb-vectorが提供するのは，新しいベクタの実装です。core.rrb-vectorで実装されるベクタはRRB(Relaxed Radix Balanced)木に基づいています。
RRB木の特徴は，現在のClojureコアのベクタの実装である32分木のO(log(N))でのインデクシングや更新に加え，O(log(N))の連結操作とスライシングを備えていることです。
| 32分木 | RRB木 | |
| インデクシング | O(log(N)) | O(log(N)) |
| 更新 | O(log(N)) | O(log(N)) |
| 連結 | O(N) | O(log(N)) |
| スライシング | O(1) | O(log(N)) |
core.rrb-vectorが提供する連結およびスライシングのための関数は，Clojureコアのベクタを混在させて使用できるため，コアのベクタからrrb-vectorへシームレスに移行することができます。
このようなClojureコアとの互換性の高さや，Reducers方面への応用に対する期待から，将来コア側へ取り込まれることも視野に入れながらcore.rrb-vectorの開発は進められています。
インストール
core.rrb-vectorを実際に使ってみるには，Leiningenを使っている場合は:dependenciesに
[org.clojure/core.rrb-vector "0.0.9"]
を追加すればOKです。弱冠バージョン0.0.9ということで，位置づけとしてはまだアルファ版です。
使い方
では，core.rrb-vectorを使ってみましょう。
ベクタを生成するには，clojure.core.rrb-vector/vectorを使います。生成したベクタはClojureコアのベクタと同じように使うことができます。
user=> (require '[clojure.core.rrb-vector :as v]) nil user=> (def v (v/vector 1 2 3)) #'user/v user=> (class v) clojure.core.rrb_vector.rrbt.Vector user=> (first v) 1 user=> (next v) (2 3) user=> (conj v 4) [1 2 3 4] user=>
ベクタの連結とスライシングにはそれぞれclojure.core.rrb-vector/catvecおよびclojure.core.rrb-vector/subvecを使用します。
user=> (v/catvec (v/vector 1 2 3) (v/vector 4 5 6)) [1 2 3 4 5 6] user=> (v/subvec *1 2 5) [3 4 5] user=>
先述したように，catvecとsubvecはClojureコアのベクタを混ぜても使うことができます。
user=> (v/catvec [1 2 3] (v/vector 4 5 6)) [1 2 3 4 5 6] user=> (class *1) clojure.core.rrb_vector.rrbt.Vector user=> (v/subvec [1 2 3 4 5 6] 1 3) [2 3] user=> (class *1) clojure.core.rrb_vector.rrbt.Vector user=>
ベンチマーク
せっかくなので，ベンチマークもとってみましょう。以下のようなプログラムで，ベクタの連結にかかる時間を計測します。
(ns contrib-calendar.core.rrb-vector) (defn bench [vec concat] (doseq [n [100000 200000 500000 1000000 2000000 5000000]] (dotimes [_ 5] (let [v1 (vec (range n)), v2 (vec (range n))] (time (concat v1 v2)))) (newline)))
以下，ベンチマークの実行結果です。
user=> (require '[contrib-calendar.core.rrb-vector :refer [bench]]) nil user=> (require '[clojure.core.rrb-vector :as v]) nil user=> (bench vec into) "Elapsed time: 2.652 msecs" "Elapsed time: 2.643 msecs" "Elapsed time: 3.013 msecs" "Elapsed time: 2.605 msecs" "Elapsed time: 2.89 msecs" "Elapsed time: 5.589 msecs" "Elapsed time: 7.535 msecs" "Elapsed time: 5.539 msecs" "Elapsed time: 5.944 msecs" "Elapsed time: 5.659 msecs" "Elapsed time: 22.922 msecs" "Elapsed time: 16.553 msecs" "Elapsed time: 14.555 msecs" "Elapsed time: 14.104 msecs" "Elapsed time: 14.567 msecs" "Elapsed time: 28.71 msecs" "Elapsed time: 29.276 msecs" "Elapsed time: 30.195 msecs" "Elapsed time: 33.978 msecs" "Elapsed time: 27.959 msecs" "Elapsed time: 59.322 msecs" "Elapsed time: 58.319 msecs" "Elapsed time: 55.902 msecs" "Elapsed time: 57.206 msecs" "Elapsed time: 58.474 msecs" "Elapsed time: 145.583 msecs" "Elapsed time: 131.498 msecs" "Elapsed time: 130.354 msecs" "Elapsed time: 130.446 msecs" "Elapsed time: 130.875 msecs" nil user=> (bench v/vec v/catvec) "Elapsed time: 3.138 msecs" "Elapsed time: 0.586 msecs" "Elapsed time: 0.623 msecs" "Elapsed time: 0.624 msecs" "Elapsed time: 0.743 msecs" "Elapsed time: 0.7 msecs" "Elapsed time: 0.64 msecs" "Elapsed time: 0.669 msecs" "Elapsed time: 0.786 msecs" "Elapsed time: 0.685 msecs" "Elapsed time: 0.9 msecs" "Elapsed time: 0.919 msecs" "Elapsed time: 0.889 msecs" "Elapsed time: 1.031 msecs" "Elapsed time: 0.896 msecs" "Elapsed time: 1.035 msecs" "Elapsed time: 0.91 msecs" "Elapsed time: 0.906 msecs" "Elapsed time: 0.902 msecs" "Elapsed time: 0.901 msecs" "Elapsed time: 4.438 msecs" "Elapsed time: 0.913 msecs" "Elapsed time: 0.914 msecs" "Elapsed time: 0.945 msecs" "Elapsed time: 0.618 msecs" "Elapsed time: 0.807 msecs" "Elapsed time: 0.972 msecs" "Elapsed time: 0.76 msecs" "Elapsed time: 0.693 msecs" "Elapsed time: 0.726 msecs" nil user=>
Clojureコアのベクタの方は綺麗に線形に時間が増加しているのが分かります。一方，RRBベクタの方はほとんど連結にかかる時間が変わっていません。これだけ速いとちょっとどこか計測の仕方が間違ってるのかと心配になりますが，大丈夫でしょうか…？(^^;
