OCaml 合并排序和时间

Question

我在 ocaml 中创建了一个函数 (mergesort)，但是当我使用它时，列表是倒置的。

另外，我想计算系统做计算的时间，怎么办？

let rec merge l x y = match (x,y) with 
    | ([],_) -> y
    | (_,[]) -> x
    | (h1::t1, h2::t2) -> 
    if l h1 h2 
        then h1::(merge l t1 y)
        else h2::(merge l x t2);;

let rec split x y z = match x with
     | [] -> (y,z)
     | x::resto -> split resto z (x::y);;

let rec mergesort l x = match x with
    | ([] | _::[]) -> x
    | _ -> let (pri,seg) = split x [] [] 
    in merge l (mergesort l pri) (mergesort l seg);;

mergesort (>) [2;6;1;8];;
- : int list = [8; 6; 2; 1]

Answer 1

将行 if l h1 h2 更改为 if l h2 h1。比较两个子列表中的头元素的方式为您提供了一个倒排列表。

另外，当你有多个相互调用的递归函数时，我可以建议你使用以下语法：

let rec merge cmp x y = match (x,y) with 
  | ([],_) -> y
  | (_,[]) -> x
  | (h1::t1, h2::t2) -> 
    if cmp h2 h1 
    then h1::(merge cmp t1 y)
    else h2::(merge cmp x t2)

and split x y z = match x with
  | [] -> (y,z)
  | x::resto -> split resto z (x::y)

and  mergesort cmp x = match x with
  | ([] | _::[]) -> x
  | _ -> let (pri,seg) = split x [] [] 
     in (merge cmp (mergesort cmp pri) (mergesort cmp seg));;

要测量时间函数，你可以看这里： Running time in Ocaml

Answer 2

要对函数进行基准测试，请参阅 Core_Bench https://blogs.janestreet.com/core_bench-micro-benchmarking-for-ocaml/。

OCaml 合并排序和时间

OCaml mergesort and time

sorting

time

merge

ocaml