CODEWITHSUNDEEP
functional-programmingocaml
snfornroqsdm
snfornroqsdm

Reputation: 59

Is there any way to optimize this function and make it faster?

is there a way to optimize this? It is taking way too long to run

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

Upvotes: 1

Views: 116

Answers (2)

Chris
Chris

Reputation: 36601

Let's clean this up a bit. This is just your approach, but tidied up by taking advantage of order of operations and binding some names to subexpressions. I've also used incr counter2 rather than counter2 := !counter2 + 1.

let counter2 = ref 0

let rec s2 num = 
  incr counter2;
  match num with
  | 0 -> 1
  | 1 -> 2
  | _ -> 
    let s2' = s2 (num - 1) in
    let s2'' = s2 (num - 2) in
    let num' = num + 1 in
    (6 * num - 3) * s2' / num' - (num-2) * s2'' / num'

Now the efficiency issue with this code is that s2 gets called more than it needs to. If we evaluate s2 4 for instance:

s2 4
  s2 3
    s2 2
      s2 1
      s2 0
    s2 1
  s2 2
    s2 1
    s2 0

For s2 5:

s2 5
  s2 4
    s2 3
      s2 2
        s2 1 
        s2 0
      s2 1
    s2 2
      s2 1
      s2 0
  s2 3
    s2 2
      s2 1
      s2 0
    s2 1

So there are 9 and 15 calls respectively to s2 in those two calls. But how many unique calls are there? 5 and 6, respectively.

If we cache the results of these calculations in something like a map, we can significantly reduce the complexity of the function, since map lookups are in a worst case situation O(log n).

We then just have to pass a map as an argument to the function and have the function either lookup the cached result, or calculate it and cache it, passing that cache along to the next call to avoid repeated calls.

"Hiding" this function inside an s3 function allows us to make the map "invisible" to anyone calling s3 and initialize it with the bindings for 0 and 1.

module M = Map.Make (Int)

let s3 num =
  let counter = ref 0 in
  let rec aux num map =
    incr counter;
    match M.find_opt num map with
    | Some v -> (v, map)
    | None ->
      let (s3', map') = aux (num - 1) map in
      let (s3'', map'') = aux (num - 2) map' in
      let num' = num + 1 in
      let result = (6 * num - 3) * s3' / num' - (num-2) * s3'' / num' in
      (result, M.add num result map'')
  in
  (!counter, fst @@ aux num @@ M.(empty |> add 0 1 |> add 1 2))

If we call s2 10_000, expect to be waiting a very long time. Calling s3 10_000 is almost instant. Of course, this will overflow the int type, but it'll do so quickly.

# s3 10_000;;
- : int * int = (19999, -159516254014960)

Upvotes: 0

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

Here is the highly recursive definition of the Fibonacci sequence:

let rec fib n = 
  if n < 2 then n 
  else fib (n - 2) + fib (n - 1)

Here is the not so recursive definition of the Fibonacci sequence.

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

Here is a function for timing things:

let time f x =
  let st = Unix.gettimeofday () in
  let res = f x in
  Printf.printf "%f seconds\n" (Unix.gettimeofday () -. st);
  res

Here are times for the fib and nfib functions:

# time fib 42;;
7.694294 seconds
- : int = 267914296
# time nfib 42;;
0.000002 seconds
- : int = 267914296

Upvotes: 3

Related Questions