如何优化这些 ocaml 函数以实现动态间隔调度？

Question

我有一个程序可以使用动态规划解决加权间隔调度问题 （无论你相信与否，这不是为了家庭作业）。我已经对其进行了分析，并且我似乎花费了大部分时间用 p(...) 填充 M。以下是函数：

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);
    | [] -> ();;

我真的想不出任何方法来优化它，并且根据我对这个算法的了解，这似乎是可能占用最多时间的地方。但这也只是我的第二个 OCaml 程序。那么有没有什么办法可以优化这个呢？

Answer 1

您的两个功能没有任何明显低效的地方。您是否期望您的实现速度更快，例如参考另一种语言的实现？

我想知道传递给 get_highest_nonconflicting 的列表。如果您有理由期望此函数经常传递与之前传递的列表在物理上相同的列表（这包括在递归调用中传递的子列表），那么那里的缓存可能会有所帮助。

如果您期望列表相等但物理上不同，则散列构造（然后是缓存）可能会有所帮助。