2-3 フィンガーツリー

2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度付きキューや探索木などを実装できる。2006年にRalf HinzeとRoss Patersonが発表した^[1]^[2]。

関数型プログラミング言語などで使われる。Haskellでは、containersパッケージ^[3]に列に特化した実装のData.Sequence^[4]が含まれ、列に限定しない汎用の実装もfingertreeパッケージ^[5]として存在する。Scalaでは標準ライブラリには含まれていないが、scalaz^[6]などのライブラリなどで実装されている。その他、様々なプログラミング言語で実装されている。

構造

2-3フィンガーツリーは分岐数が2または3である木構造に対して「指(finger)」と呼ばれる構造^[7]を導入して作られる。通常の平衡木では葉に置いた要素にアクセスする際には根から参照を辿る必要があり、要素数に対して対数時間の計算量が必要となる。しかし多くの場合、頻繁にアクセスする要素は特定の場所やその周辺に偏っている。例えば両端キューの場合、ほとんどの演算は両端やその周辺に対する演算である。そのため毎回根から参照を辿るのは効率が悪い。そこで参照を辿る開始点を変更し、必要に応じてポインタを反転させておき頻繁にアクセスする部分に素早くアクセスできるようにする。この構造を指と言う。以下は完全二分木の両端に対して指を導入した例である(2-3フィンガーツリーではない)。

まず参照を辿る開始点を両端にする。親からそのノードへの参照を反転させる。そして親から親の親への参照も再帰的に反転させていく。すると両端に近い部分へは素早くアクセスできるようになる。完全二分木の両端に指を導入したものは最初の部分を除いて、2つの完全二分木を要素として持つリストとしても見られる。各完全二分木のサイズは2倍ずつに増えていく。

2-3フィンガーツリーは分岐数が2または3である木構造の両端に指を追加したものであり、分岐数が2または3である木のペアを要素として持つリストとしても見られる。ただしそれらの木の根のみは1から4つの子を持てるように条件を緩和する。これは追加と削除を交互に実行しても処理時間を償却定数時間に保つためである。なお根の分岐数は1から3まででもよい。その場合、計算量のオーダーは変わらないものの木は深くなる。2-3フィンガーツリーをリストとして見た場合、完全二分木に指を導入したときと同じように各要素の木は指数関数的に大きくなる。

2-3フィンガーツリーは形式的には次のように定義される。ここでは記法はHaskellを用いた。

-- 2-3フィンガーツリー
data FingerTree a = Empty -- 空の木
                  | Single a -- 1つだけ要素を持つ木
                  | Deep (Digit a) (FingerTree (Node a)) (Digit a) -- より深い木

-- 左右の木の根。1から4つの要素を持つ。
data Digit a = One a | Two a a | Three a a a | Four a a a a

-- 左右の木の根以外。2つまたは3つの要素を持つ。
data Node a = Node2 a a | Node3 a a a

フィンガーツリーは「空の木」「1つだけ要素を持つ木」「深い木」のいずれかである。深い木は列の最初の数要素・最後の数要素・それ以外を保持するフィンガーツリーからなる。Digitは左右の木の根であり、Nodeは分岐数が2または3である平衡木を表す。ただしDigitやNodeは木の深さによって異なる型を持つ。例えばNode Integerは整数を要素としてもつ深さ1の木であり、Node (Node Integer)は整数を要素として持つ深さ2の木である。この型付けは深いフィンガーツリーは左右に持つ木も深くなるという制約を強制し、アルゴリズムを強固で単純にする。左右の木をDigit(数字)と呼んでいるのはフィンガーツリーが数値表現を利用したデータ構造だからである。

演算

フィンガーツリーに対する要素の追加等の各種演算を示す。ここでは次のように図を混ぜた式でも表現する。

追加

木の右に要素を追加する演算について示す。左に追加する演算も同様である。

追加演算の演算子を▷で示す。空の木や、1つだけ要素を持つ木に対する追加は簡単である。

Empty ▷ a = Single a

(Single a) ▷ b = Deep (One a) Empty (One b)

深い木に対する追加に関してもDigitが4未満の場合は簡単である。例えば右のDigitが1の場合は次のようになる。

 (Deep pr m (One b)) ▷ c = Deep pr m (Two b c)

Digitが4の場合はより深い木に繰り上がり処理をする。

 (Deep pr m (Four b c d e)) ▷ f = Deep pr (m ▷ (Node3 b c d)) (Two e f)

より深い木の要素は1段深いNodeである点に注意。

削除

木を一番右の要素とその要素を削除した木に分割する演算popRについて示す。左側を分割する演算popLも同様である。

削除演算はほとんど追加演算の逆である。1つだけ要素を持つ木からの削除は単純である。

 popR (Single a) = (Empty, a)

深い木に関してもDigitが1以外のときは単純である。例えばの場合は次のようになる。

 popR (Deep pr m (Two b c)) = (Deep pr m (One b), c)

Digitが1の場合、繰り下がり処理をする。

 popR (Deep pr m (One b)) = (borrowR pr m, b)

繰り下がり処理はより深い木が空の場合と空でない場合で場合分けする。空の場合は次のようになる。

 borrowR pr Empty = toTree pr

ここでtoTreeは空の木にprの要素を順に追加する関数である。

より深い木が空でない場合は次のようになる。

 borrowR pr m
   = let
       (m', node) = popR m
     in
       Deep pr m' (toDigit node)

ここでtoDigitはNodeをDigitに変換する関数である。Nodeは2つまたは3つの要素を持つので、それらをTwoまたはThreeに変換する。より深い木の要素はNodeである点に注意。

popRで木を変形する様子を図で示す。ここではpopRとborrowRを合わせて1つの式で書いている。より深い木が空の場合は次のようになる。

より深い木が空でない場合は次のようになる。

追加および削除演算の計算量は式を遅延評価する処理系において償却定数時間である。

以下の図は空の木に右から要素を17個追加し、左から1つずつ削除していく様子である。ただし繰り上がりや繰り下がりの様子がわかりやすいようにDigitは3までに制限してある。

連結

2つの木を連結する演算は直接定義されるのではなく、2つの木の間に数個の要素を挟んで連結する演算appendを使って定義される。

どちらかの木が空、もしくは1つだけ要素を持つ場合は単純である。例えば右の木が1つだけ要素を持つ場合は次のようになる。

 append(pr, [a, b, c, d, e], Single f) = pr ▷ a ▷ b ▷ c ▷ d ▷ e ▷ f

両方の木が深い木である場合は、再帰的に要素を追加する。一例を示す。

 append(Deep pr m1 (Four a b c d), [e, f, g, h], Deep (Three i j k) m2 sf)
   = let
       m = append(m1, [Node3 a b c, Node3 d e f, Node3 g h i, Node j k], m2)
     in
       Deep pr m sf

分割

木を指定した位置で分割するためには、木の各部分に対してその部分が含む要素の数を計算する必要がある。

class SizeMeasured a where size :: a -> Integer

instance SizeMeasured FingerTree where
  size Empty = 0
  size (Single a) = size a
  size (Deep pr m sf) = size pr + size m + size sf

instance SizeMeasured Digit where
  size (One a) = size a
  size (Two a b) = size a + size b
  -- その他のDigitは省略

instance SizeMeasured Node where
  size (Node2 a b) = size a + size b
  size (Node3 a b c) = size a + size b + size c

newtype Leaf a = Leaf a -- 葉はLeafでくるんでおく。
instance SizeMeasured Leaf where
  size (Leaf _) = 1

実際には木の各部分に要素数のキャッシュを追加しておき、再計算しないようにする。

i番目の葉での分割演算は、i番目の葉を含む要素より左の要素からなる木・i番目の葉を含む要素・i番目の葉を含む要素より右の要素からなる木に分割する演算splitTreeAtを使って定義される。

木が要素を1つだけもつときは単純である。ここで、iは0以上、木のサイズ未満とする。

 splitTreeAt i (Single a) = (Empty, a, Empty)

深い木の場合はi番目の葉の位置により場合分けする。まずi番目の葉が左の木や右の木に含まれる場合は、それを分割すればよい。

 splitTreeAt i (Deep pr m sf)
   | i <= size pr -- i番目の葉は左に含まれる
     = let
         (pr1, a, pr2) = splitDigitAt i pr
       in
         (pr1, a, Deep pr2 m sf)
   | i > size pr + size m -- i番目の葉は右に含まれる
     = let
         (sf1, a, sf2) = splitDigitAt (i - size pr - size m) sf
       in
         (Deep pr m sf1, a, pr2)
   -- 続く

左右の木の分割は単純にi番目より左の要素と、i番目の要素と、i番目より右の要素に分ければよい。

 splitDigitAt i (One a) = (Empty, a, Empty)
 splitDigitAt i (Two a b) | i < size a = (Empty, a, Single b)
                          | otherwise = (Single a, b, Empty)
 -- 他のDigitについては略

i番目の葉が中央のより深い木に含まれる場合はひと手間多く必要となる。まず中央の木を分割する。するとi番目の葉を含むNodeが得られる。このNodeをさらに分割すると葉が得られる。

   -- 続き
   | otherwise -- i番目の葉はより深い木に含まれる
       = let
           -- m1とm3はFingerTree、m2はNode。
           (ml, xs, mr) = splitTreeAt (i - size pr) m
           -- lとrはMaybe (Digit a)とする。
           (l, a, r) = splitNodeAt (i - size pr - size ml) xs
         in
           -- deepR, deepLは、rやlがNothingの場合に繰り下がり処理をしてFingerTreeを作る関数
           (deepR pr ml l, a, deepL r mr sf)
 
 splitNodeAt i node = -- 省略
 
 deepR pr m Nothing = borrowR pr m
 deepR pr m (Just sf) = Deep pr m sf
 
 -- deepLは省略

分割の一般化

前述した分割演算では各ノードのサイズを計算してキャッシュし、位置がiとなる要素を探し、そこで分割した。これをさらに一般化すると様々なデータ構造を実装できる。

まず各ノードについて、サイズではなく実装するデータ構造に応じた値を計算し、キャッシュできるようにする。値は例えば通常の列を実装するのであればノードのサイズを計算し、優先順位付きキューを実装するのであればノード内の最大の優先順位を計算する。より詳しい例は#応用で示す。値はどのような値でもよいが、部分木の値からより大きな木の値を計算できるようにモノイドである必要がある。つまり結合則を満たす二項演算⊕とその単位元eを持っている必要がある。

次に、分割点となる要素を探すための述語が必要となる。列の例では「位置がiより大きい」という述語が使われる。分割演算ではこの述語が偽から真に変化する要素を探す。

列の例では分割する位置iを減少させながら再帰呼び出ししたが、一般化した状態ではモノイドを使うため減算はできない。そこでアキュムレータを用意し、再帰呼び出しに入る前に左側の部分木の値を累積していき、基準値と比べる。

述語pはアキュムレータの初期値では偽となり、木全体に対しては真となる必要がある。列の例では初期値として単位元0を使うので、この制限は「iは0以上、木のサイズ未満である」という制限となる。

以上の条件の元で、一般化した分割演算は次のように書ける。ここでmeasureはノードから値へ変換する関数である。初期値xから始めて値を累積しながらpを満たす要素を探していく。

 splitTreeAt p x (Single a) = (Empty, a, Empty)
 splitTreeAt p x (Deep pr m sf)
   | p (x ⊕ measure pr)
     = let
         (pr1, a, pr2) = splitDigitAt p x pr
       in
         (pr1, a, Deep pr2 m sf)
   | p (x ⊕ measure pr ⊕ measure m)
     = let
         (sf1, a, sf2) = splitDigitAt p (i ⊕ measure pr ⊕ measure m) sf
       in
         (Deep pr m sf1, a, pr2)
   | otherwise
       = let
           -- m1とm3はFingerTree、m2はNode。
           (ml, xs, mr) = splitTreeAt p (i ⊕ measure pr) m
           -- lとrはMaybe (Digit a)とする。
           (l, a, r) = splitNodeAt p (i ⊕ measure pr ⊕ measure ml) xs
         in
           -- deepR, deepLは、lやrがNothingの場合に繰り下がり処理をしてFingerTreeを作る関数
           (deepR pr ml l, a, deepL r mr sf)

通常はある要素までは述語は常に偽となり、それより先の要素では述語は常に真となるようにする。しかし述語の真偽は途中で何度も切り替わってもよい。その場合、このアルゴリズムは述語が偽から真に切り変わる要素のうち適当な1つで分割する。

実行時間

implicit recursive slowdown

2-3フィンガーツリーはimplicit recursive slowdownという構成手法に基づくデータ構造である。implicit recursive slowdownとは、recursive slowdownに遅延評価を導入し、計算量を最悪計算量から償却計算量ヘ緩めて簡略化したものである。recursive slowdownは親ノードをn回処理する間に子ノードをnより少ないm回処理する。そのため等比数列の性質により全体の計算量は親ノードの計算量のたかだか定数倍となる。この性質により2-3フィンガーツリーも要素の追加演算や削除演算の計算量が償却定数時間となっている。

応用

ここでは#分割の一般化で示した分割演算を使った応用例を示す。

優先度付きキュー

優先度付きキューを実装する場合、関数measureはその部分木が含む最大の優先度を返す。値は半群となるようにし、二項演算として優先度の大きい方を返す。かつてはHaskellやscalazの実装などは、半群ではなくモノイドが必要となっていて、その際は単位元として優先度が負の無限大を利用した。

優先順位最大の要素を取得する場合、優先度が木全体の最大の優先度と等しい要素で分割する。

探索木

探索木を実装する場合、関数measureはその部分木が含む最後のキーを返す。そして木にキーkを挿入する際は、木をkより小さい部分とk以上の部分に分割し、その間にkを入れて連結する。するとキーは昇順に並ぶようになり、平衡探索木を実装できる。

統計量の計算

より巧妙な例として、データ列の部分列に対する統計量(平均や分散)の効率的かつ安定な計算がある^[8]。

この場合、関数measureは「部分木が含む要素の数」・「平均」・「分散×要素の数」の組を返す。これらの値を合わせるとより大きな部分木に対する値を計算でき(en:Algorithms for calculating variance#Parallel algorithm)、モノイドとなる。

この値の組は要素の数を含んでいるため、位置を指定して木を分割できる。するとデータ列の部分列に対する統計量を計算できる。また、この計算方法はデータの和とデータの自乗の和から計算する単純な計算方法と比べて数値的に安定である。

参考文献

^ Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In Journal of Functional Programming Vol. 16, No. 2, 2006, pp. 197–217, doi:10.1017/S0956796805005769
^ Finger Trees: A Simple General-purpose Data Structure
^ containers: Assorted concrete container types
^ Data.Sequence
^ fingertree: Generic finger-tree structure, with example instances
^ FingerTree - scalaz-core_2.13 javadoc
^ Leo J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts, “A new representation for linear lists”, In Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77), New York, NY, USA: ACM, 1977, pp. 49–60. DOI=10.1145/800105.803395 http://doi.acm.org/10.1145/800105.803395
^ sigfpe, “Statistical Fingertrees”, A Neighborhood of Infinity, http://blog.sigfpe.com/2010/11/statistical-fingertrees.html 2011年6月5日アクセス

[finger_tree-1] Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”, In Journal of Functional Programming Vol. 16, No. 2, 2006, pp. 197–217, doi:10.1017/S0956796805005769

[2] Finger Trees: A Simple General-purpose Data Structure

[3] tainers: Assorted concrete container types

[4] Data.Sequence

[5] rtree: Generic finger-tree structure, with example instances

[6] FingerTree - scalaz-core_2.13 javadoc

[new_representation_for_linear_lists-7] Leo J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts, “A new representation for linear lists”, In Proceedings of the ninth annual ACM symposium on Theory of computing (STOC '77), New York, NY, USA: ACM, 1977, pp. 49–60. DOI=10.1145/800105.803395 http://doi.acm.org/10.1145/800105.803395

[statistical_fingertrees-8] sigfpe, “Statistical Fingertrees”, A Neighborhood of Infinity, http://blog.sigfpe.com/2010/11/statistical-fingertrees.html 2011年6月5日アクセス

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]