How do I optimize these ocaml functions for dynamic interval scheduling?

Question

I have a program that solves the weighted interval scheduling problem using dynamic programming (and believe it or not, it isn't for homework). I've profiled it, and I seem to be spending most of my time filling M with p(...). Here are the functions:

let rec get_highest_nonconflicting prev count start =
  match prev with
      head :: tail -> 
    if head < start then 
      count
    else
      get_highest_nonconflicting tail (count - 1) start
    | [] -> 0;;

let m_array = Array.make (num_genes + 1) 0;;    

let rec fill_m_array ?(count=1) ?(prev=[]) gene_spans  = 
  match gene_spans with
      head :: tail -> m_array.(count) <- 
    get_highest_nonconflicting prev (count - 1) (get_start head);
    fill_m_array tail ~prev:(get_stop (head) :: prev) ~count:(count+1);
    | [] -> ();;

I can't really think of any ways to optimize this, and based on my knowledge of this algorithm, this seems to be the place that is likely to take up the most time. But this is also only my second OCaml program. So is there any way to optimize this?

Answer 1

There isn't anything obviously inefficient with your two functions. Did you expect your implementation to be faster, for instance with reference to an implementation in another language?

I was wondering about the lists passed to get_highest_nonconflicting. If you have reasons to expect that this function is often passed lists that are physically identical to previously passed lists (and this includes the sub-lists passed on recursive calls), a cache there could help.

If you expect lists that are equal but physically different, hash-consing (and then caching) could help.