如何优化这些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. 。如果您有理由期望此功能通常传递到与先前传递的列表上相同的列表（其中包括在递归呼叫上传递的子名单），则可以在那里有帮助。

如果您期望列表相等但在身体上不同，则哈希（Hash）进行（然后是缓存）可能会有所帮助。