有什么方法可以优化这个功能并使其更快?
Is there any way to optimize this function and make it faster?
有没有办法优化这个? 运行
花费的时间太长了
let counter2 = ref 0
let rec s2 num =
counter2 := !counter2 + 1;
match num with
| 0 -> 1
| 1 -> 2
| _ -> (((((6*num)-3) * (s2 (num-1))) / (num+1))) - (((num-2)* (s2 (num-2))/(num+1)))
下面是斐波那契数列的高度递归定义:
let rec fib n =
if n < 2 then n
else fib (n - 2) + fib (n - 1)
下面是斐波那契数列的非递归定义。
let nfib n =
let rec helper pprev prev i =
if i = n then
pprev + prev
else
helper prev (pprev + prev) (i + 1)
in
if n < 2 then n
else helper 0 1 2
这是一个计时函数:
let time f x =
let st = Unix.gettimeofday () in
let res = f x in
Printf.printf "%f seconds\n" (Unix.gettimeofday () -. st);
res
以下是 fib
和 nfib
函数的时间:
# time fib 42;;
7.694294 seconds
- : int = 267914296
# time nfib 42;;
0.000002 seconds
- : int = 267914296
有没有办法优化这个? 运行
花费的时间太长了let counter2 = ref 0
let rec s2 num =
counter2 := !counter2 + 1;
match num with
| 0 -> 1
| 1 -> 2
| _ -> (((((6*num)-3) * (s2 (num-1))) / (num+1))) - (((num-2)* (s2 (num-2))/(num+1)))
下面是斐波那契数列的高度递归定义:
let rec fib n =
if n < 2 then n
else fib (n - 2) + fib (n - 1)
下面是斐波那契数列的非递归定义。
let nfib n =
let rec helper pprev prev i =
if i = n then
pprev + prev
else
helper prev (pprev + prev) (i + 1)
in
if n < 2 then n
else helper 0 1 2
这是一个计时函数:
let time f x =
let st = Unix.gettimeofday () in
let res = f x in
Printf.printf "%f seconds\n" (Unix.gettimeofday () -. st);
res
以下是 fib
和 nfib
函数的时间:
# time fib 42;;
7.694294 seconds
- : int = 267914296
# time nfib 42;;
0.000002 seconds
- : int = 267914296