Skew Binary Random-Access Lists

OCaml

Linuxの環境整備に熱中していて、すっかり忘れていたけれど、http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf の 6.4.1章について。


これは何かというと、Skew Binary Numbers - komamitsu.logとBinary Random-Access List - komamitsu.logを合わせたランダムアクセス向けリストです。


もの凄くあっさりと言うと以下のような特徴を持っています。

  • 二分木の要素数（Node含む）がSkew Binary Numberとなる
  • 繰り上げ・繰り下げの際の挙動もSkew Binary Numberと同じとなる
  • ランダムアクセス時の計算量はO(min(i, log n))でBinary Random-Access Listより少し性能が良いとのこと

内部的な構造について例をあげると…

  • [100; 101] => [(1, Leaf 101); (1, Leaf 100)]
  • [100; 101; 102] => [(3, Node (102, Leaf 101, Leaf 100))]
  • [100; 101; 102; 103] => [(1, Leaf 103); (3, Node (102, Leaf 101, Leaf 100))]
  • [100; 101; 102; 103; 104; 105] => [(3, Node (105, Leaf 104, Leaf 103)); (3, Node (102, Leaf 101, Leaf 100))]

というように、要素を保持していきます（当然、詳細は上記のPDF参照）。


で、いつもの如くこれを実装してみました => http://github.com/komamitsu/ocaml-skew-binary-random-access-list


どうも元の論文（79P: line 23 & 29）のStandardMLのコードが微妙らしく、移植の際には以下のように変更しています。

if i < w div 2 then lookupTree (w div 2, t1, i - 1)
         ↓
if i - 1 < w div 2 then lookupTree (w div 2, t1, i - 1)

で、これの使い方の例はこんな感じです.

open Printf

module M = SkewBinaryRandomAccessList

let p s i = printf "%s : %d\n" s i

let _ =
  let l = [100; 101; 102; 103; 104; 105; 106; 107; 108; 109] in
  let rl = List.fold_left (fun rl x -> M.cons x rl) M.empty l in
  ignore (p "the head of rl" (M.head rl));
  ignore (p "the 2nd of rl" (M.lookup (2 - 1) rl));
  ignore (p "the 5th of rl" (M.lookup (5 - 1) rl));
  ignore (p "the 10th of rl" (M.lookup (10 - 1) rl));
  let the_tail_of_rl = M.tail rl in
  ignore (p "the 2nd of rl via tail" (M.head the_tail_of_rl));
  let rl_replaced_the_1st_with_99 = M.update (1 - 1) 99 rl in
  ignore (p "the head of updated rl" (M.head rl_replaced_the_1st_with_99));
  let rl_replaced_the_9th_with_999 = M.update (9 - 1) 999 rl in
  ignore (p "the 9th of updated rl" (M.lookup (9 - 1) rl_replaced_the_9th_with_999))

これを実行してみると

komamitsu@potato:~/git/ocaml-skew-binary-random-access-list$ ocamlc -o sample skewBinaryRandomAccessList.cmo sample.ml
komamitsu@potato:~/git/ocaml-skew-binary-random-access-list$ ./sample 
the head of rl : 109
the 2nd of rl : 108
the 5th of rl : 105
the 10th of rl : 100
the 2nd of rl via tail : 108
the head of updated rl : 99
the 9th of updated rl : 999

と、きちんと動作しているようです。

後日、暇があったらListとかと性能比較をしてみたいなぁ、なんて。