haskell-ja > Archives

2012/01/23 07:01:46 UTC[1..100]>>=pen

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) より遅くなるか試してもらえませんか。

2012/01/23 07:04:58 UTCmasterq

変換器が召喚されました。空いてるときやってみまっす。

2012/01/23 08:01:33 UTCmasterq

https://github.com/master-q/readPurelyFunctionalDataStructures/blob/master/RedBlackTree/redblack_tree_ex3_10b.ml

バグあるかもしれないけど移植しました。

$ 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)

誤差、、、かな。。。

2012/01/23 08:19:56 UTC[1..100]>>=pen

(a) と同じかちょっと遅いくらいですかね。うーーーん・・・

2012/01/23 11:49:03 UTCshelarcy@twitter

統計的な結果にではなく一回一回の処理での実行時間を出しているみたいですが、OCaml には criterion のように統計的に結果を出してくれるライブラリはないのでしょうか？

2012/01/23 19:01:22 UTC[1..100]>>=pen

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」は外して読んでください。

2012/01/23 19:11:41 UTC[1..100]>>=pen

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

で検証お願いします。

<< 2012/01/22

Back to the chat room

2012/01/24 >>

haskell-ja > Archives > 2012/01/23