data.finger-tree: フィンガーツリー
(このエントリは Clojure Contrib Library Advent Calendar 13日目の記事です。)
はじめに
今回はdata.finger-treeについてです。data.finger-treeは名前が示すとおり,フィンガーツリーの実装を提供します。Wikipediaによれば,フィンガーツリーは以下のようなデータ構造です:
2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度つきキューや探索木などを実装できる。
2-3 フィンガーツリー - Wikipedia
data.finger-treeでは,先頭と末尾に定数時間でアクセス可能な「ダブルリスト」と呼ぶデータ構造とその亜種,およびフィンガーツリーを使って独自のデータ構造を作るためのインタフェースが提供されています。
今回は,ダブルリストとその亜種の使い方について見てみます。
インストール
data.finger-treeを使うには,Leiningenのproject.cljへ依存ライブラリとして以下を追加します。
[org.clojure/data.finger-tree "0.0.1"]
使い方
以下は各データ構造に関する特徴的な関数です。
- double-list
- (double-list & args): 引数に与えられた値を要素にもつダブルリストを生成します
- (consl s a): ダブルリストの先頭に要素を追加します
- (conjr s a): ダブルリストの末尾に要素を追加します
- (ft-concat t1 t2): 2つのダブルリストを連結します
- counted-double-list (定数時間のcountをサポートしたダブルリスト)
- (counted-double-list & args): 引数に与えられた値を要素にもつcounted double listを生成します
- (ft-split-at o k): ダブルリストをインデックスkの位置で分割します
- counted-sorted-set (counted double listに似たsorted set)
- (counted-sorted-set & args): 引数に与えられた値を要素にもつcounted sorted setを生成します
例
以下,実際の使用例です。
user=> (use 'clojure.data.finger-tree) nil user=> (def xs (double-list 1 2 3)) #'user/xs ; conslで先頭に要素を追加できる user=> (consl xs 0) (0 1 2 3) ; conjrで末尾に要素を追加できる user=> (conjr xs 4) (1 2 3 4) ; ft-concatで2つのダブルリストを連結できる user=> (ft-concat xs xs) (1 2 3 1 2 3) user=> (def ys (counted-double-list 1 2 3)) #'user/ys ; counted double listは定数時間のcountをサポート user=> (count ys) 3 ; ダブルリストと同様に,consl, conjr, ft-concatも適用できる user=> (consl ys 0) (0 1 2 3) user=> (conjr ys 4) (1 2 3 4) user=> (ft-concat ys ys) (1 2 3 1 2 3) ; ft-split-atでリストを分割できる user=> (ft-split-at ys 1) [(1) 2 (3)] user=>
おわりに
今回はdata.finger-treeが提供する種々のデータ構造について見てみました。
フィンガーツリー自体について,詳しく知りたい場合は以下が参考になります。
次回は,さらにデータ構造つながりでdata.priority-mapについて書きます。