OCaml mergesort和时间

问题描述：

我在ocaml中创建了一个函数(合并排序)，但是当我使用它时，列表会被反转.

I created a function (mergesort) in ocaml but when I use it, the list is inverted.

此外，我想计算系统执行计算所需的时间，我该怎么做?

In addition, I want to calculate the time the system takes to do the calculation, how can I do it?

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]

答

将行if l h1 h2更改为if l h2 h1.比较两个子列表中的head元素的方式为您提供了一个反向列表.

Change the line if l h1 h2 by if l h2 h1. The way of comparing the head elements from the two sublists gives you a inverted list.

此外，当您有多个互相递归的递归函数时，我可以建议您使用以下语法:

Also, I can propose you to use the following syntax when you have multiples recursives functions calling each other :

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

要测量时间函数，可以在这里查看: Ocaml中的运行时间

To measure the time function, you can have a look here : Running time in Ocaml

相关推荐