#insert x s = T B a' y b'
where
ins E = T R E x E
ins n@(T _ _ v _)
| x < v = insl n
| x > v = insr n
| otherwise = n
insl (T color E v r) = T color (T R E x E) v r
insl n@(T color l@(T _ _ v2 _) v r)
| x < v2 = llbalance color (insl l) v r
| x > v2 = lrbalance color (insr l) v r
| otherwise = n
insr (T color l v E) = T color l v (T R E x E)
insr n@(T color l v r@(T _ _ v2 _))
| x < v2 = rlbalance color l v (insl r)
| x > v2 = rrbalance color l v (insr r)
| otherwise = n
T _ a' y b' = ins s
#というのを試したのですがオリジナルよりはちょっと速いものの ex3.10(a) よりは遅くなってしまいました orz。このコード ocaml でも (a) より遅くなるか試してもらえませんか。
#変換器が召喚されました。空いてるときやってみまっす。
##バグあるかもしれないけど移植しました。
#$ omake check_rand [~/src/readPurelyFunctionalDataStructures/RedBlackTree]
*** omake: reading OMakefiles
*** omake: finished reading OMakefiles (0.01 sec)
- build . <check_rand>
+ ./redblack_tree_test
.
Ran: 1 tests in: 5.76 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test
.
Ran: 1 tests in: 5.93 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test
.
Ran: 1 tests in: 5.76 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10a
.
Ran: 1 tests in: 5.33 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10a
.
Ran: 1 tests in: 5.36 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10a
.
Ran: 1 tests in: 5.40 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10b
.
Ran: 1 tests in: 5.38 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10b
.
Ran: 1 tests in: 5.37 seconds.
OK- build . <check_rand>
+ ./redblack_tree_test_ex3_10b
.
Ran: 1 tests in: 5.39 seconds.
*** omake: done (49.81 sec, 0/0 scans, 1/1 rules, 0/41 digests)
#誤差、、、かな。。。
#(a) と同じかちょっと遅いくらいですかね。うーーーん・・・
#統計的な結果にではなく一回一回の処理での実行時間を出しているみたいですが、OCaml には criterion のように統計的に結果を出してくれるライブラリはないのでしょうか?
#insert x E3 = T3 B E3 x E3
insert x n@(T3 _ l v r)
| x < v = let T3 _ a y b = insl n in T3 B a y b
| x > v = let T3 _ a y b = insr n in T3 B a y b
| otherwise = n
where
insl n@(T3 color l@(T3 _ l2 v2 r2) v r)
| x < v2 = llbalance3 color (insl l) v r
| x > v2 = lrbalance3 color (insr l) v r
| otherwise = n
insl (T3 color _ v r) = T3 color (T3 R E3 x E3) v r
insr n@(T3 color l v r@(T3 _ l2 v2 r2))
| x < v2 = rlbalance3 color l v (insl r)
| x > v2 = rrbalance3 color l v (insr r)
| otherwise = n
insr (T3 color l v _) = T3 color l v (T3 R E3 x E3)
#にしたら (a) よりちょっと速くなったような気がします。
#T3,E3,balance3 に付いている後ろの「3」は外して読んでください。
#insert x E = T B E x E
insert x n@(T _ l v r)
| x < v = let T _ a y b = insl n in T B a y b
| x > v = let T _ a y b = insr n in T B a y b
| otherwise = n
where
insl (T color E v r) = T color (T R E x E) v r
insl n@(T color l@(T _ l2 v2 r2) v r)
| x < v2 = llbalance3 color (insl l) v r
| x > v2 = lrbalance3 color (insr l) v r
| otherwise = n
insr (T color l v E) = T color l v (T R E x E)
insr n@(T color l v r@(T _ l2 v2 r2))
| x < v2 = rlbalance3 color l v (insl r)
| x > v2 = rrbalance3 color l v (insr r)
| otherwise = n
#で検証お願いします。