performance - 如何针对动态间隔调度优化这些 ocaml 函数？

Question

我有一个解决加权 interval scheduling problem using dynamic programming 问题的程序(信不信由你，它不是用来做作业的)。我已经对它进行了概要分析，而且我似乎大部分时间都在用 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 的列表。如果您有理由期望此函数经常传递与先前传递的列表在物理上相同的列表(并且这包括在递归调用中传递的子列表)，那么那里的缓存可能会有所帮助。

如果您希望列表相同但物理上不同，散列构造(然后缓存)可能会有所帮助。