Skew Binary List

#Sequences

Operations

要素の列$$(a_0, a_1, \dots, a_{n-1})$$を扱う.

$$\mathtt{new}()$$

空の list を作成する

時間計算量$$\Theta(1)$$

$$\mathtt{is\_empty}()$$

list が空であるか判定する

時間計算量 $$\Theta(1)$$

$$\mathtt{cons}(x)$$

先頭に$$x$$を追加する

時間計算量$$\Theta(1)$$

$$\mathtt{head}()$$

$$a_0$$を取得する

時間計算量 $$\Theta(1)$$

$$\mathtt{tail}()$$

$$a_0$$を削除する

時間計算量$$\Theta(1)$$

$$\mathtt{lookup}(i)$$

$$a_i$$を取得する

時間計算量 $$\Theta(\log i)$$

$$\mathtt{update}(i,x)$$

$$a_i$$を$$x$$に変更する

時間計算量$$\Theta(\log i)$$

Summary

ねじれ二進数を用いた、list とarray の性質を併せ持つデータ構造

ねじれ二進数の$$k$$桁目は$$2^k-1$$を表しており、各桁は$$0,1,2$$のいずれかの値を取ることが出来る

ただし、ある桁が$$2$$であるならそれより小さい桁は全て$$0$$であるという条件を加える

この制限の元、全ての非負整数はねじれ二進数を用いて一意に表現することが可能である

ねじれ二進数に$$1$$を足し引きすると、通常の二進数とは異なり定数個の桁しか変化しない

この性質によって、効率的な$$\mathtt{cons}, \mathtt{tail}$$を実現している

ねじれ二進数の各桁は$$2^k-1$$の形であり、これを完全二分木に対応さたものの list を保持する

単純には可変長配列に劣るが構造が扱いやすく、path copying で永続化できるなどの特長を持つ

$$n=12$$に対して$$\mathtt{cons}$$を行った状態

$$112$$から$$120$$への繰上りに対応している

先頭への挿入により、元からあった要素の添え字は$$1$$大きくなる

References

Chris Okasaki. Purely Functional Data Structures

Notes

セグ木等と同様、モノイドを乗せることが出来る

永続化した際、以下の操作が実現できる

$$\mathtt{drop}(i)$$

先頭$$i$$要素を削除した list を作成する

時間計算量$$\Omicron(\log n)$$空間計算量$$\Omicron(\log n)$$

$$\mathtt{extend}(i,x)$$

先頭に$$i$$個$$x$$を追加した list を作成する

時間計算量$$\Omicron(\log (n+i))$$空間計算量$$\Omicron(\log (n+i))$$

片側柔軟配列とも呼ぶ

Implementations

Rust:niuez/persistent_skew_binary_list