PFDS(純粋関数型データ構造)を読んだ

手を動かしたい気分だったのでだいぶ後回しになっていたPFDS (Purely Functional Data Structure, 純粋関数型データ構造)を読みながらScalaで実装を後追いしてみた。*1

少し時間がかかったがRedBlackTreeやTrieといった有名な物から、HoodMelvilleQueueやそれを利用したCatenableListなどちょっとおしゃれ(?)なデータ構造についての実装・計算量についての考え方を学ぶことができた。

本の前半はストーリーがあって、「永続的なデータ構造だと計算効率が悪い場合が多い!・・・が!償却計算量の考え方を使いながら実装を工夫していくと短命なデータ構造と同じくらいの性能が出る。(全てではないが償却だけでなく最悪計算量についても同じくらいにできるケースも多い)」ことを確認する旅になる。 軽くまとめてみたので興味がある人はちら見しつつ、実際に本を購入して読んでみてほしい。 https://gist.github.com/matsu-chara/75dd80e36172569343738153d0123bf2

後半は様々なデータ構造を設計するための考え方がまとまっている。 こちらについても雑多になっているわけではなく、前半の考え方(実装方法・計算量の証明方法)を踏襲しつつ、一個ずつ積み重ねになっているので読み応えがある。

2進数のゼロ無し表現というものが途中に出てくる。 これは以下のように普通の2進数では {0,1}で書くところを {1,2}を使って書く記法のことだ。

1,2,3,4,5 は 1, 2, 11, 21, 12, 22, 111 となる。

- 各桁が2^iを表すのは普通の2進数と同じ。
- 0を使わないのが前提になるので、ある数を表す表現は一位に定まる

一見特に意味のない記法に思えるが、これが記数法表現に基づくデータ構造の計算量の削減に役立つというのはなかなか面白かった。 記数法表現が何かについては本を買って(ry

2-3 finger tree

2-3 finger treeといえばHaskellのData.Sequenceにも使われている(償却)計算量の優れたDequeだ。(追加・削除ともに償却定数時間で実行可能)

これはPFDSには載っていないが、ベースとなる 記数法表現暗黙再起減速 の考え方・実装の勘所はPFDSで学ぶ事ができる。*2

読み終わったあとにwikipediaを開いてみたら、以前なんとなく理解していた物よりはるかに解像度高く理解できたので勢い余って実装してみた。*3

https://github.com/matsu-chara/finger_scala

とはいえ、finger treeの実装は世界に一億個くらいありそうなので特に自慢にもならないし、パフォーマンスやメソッドの豊富さよりはわかりやすさを重視している。(が、やはりこういうのは自分で実装してみると理解度が違うと思う。)

ちなみに実用的なFingerTreeに関してはscalazの物などがおすすめ

wikipediaにあるシナリオ 通りのテストを書いてみたがいい感じな見た目になったので記念スクショを貼って終わりとする

f:id:matsu_chara:20190715172055p:plain
テスト

next

本を読むなかでscalaでの実装をいくつかあたっていたところ以下のように、いくつかの実装には論文へのリンクがついていた。

PFDSでカバーされている物もややありそうだけど面白そうなのでいつか読みたい。(けどパタヘネ読み始めた)

*1:ちなみに実装するときはcats.Evalを使うと便利 https://typelevel.org/cats/datatypes/eval.html

*2:このデータ構造の実装自体は多少腕力があればwikipediaを見れば実装できそうだが、一方でなんでDigitといった名前が出てくるのか、このようなデータ構造での計算量の考え方はある程度背景知識がないと理解が難しい気がする。(個人の感想です)

*3:ちなみにwikipediaは英語版より日本語版のほうが図が多くて実装しやすかった