performance - 如何优化这些 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。如果您有理由期望此函数通常传递与先前传递的列表在物理上相同的列表（这包括递归调用传递的子列表），那么缓存可能会有所帮助。

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